Sudoku: Difference between revisions

Content added Content deleted
Line 1,837: Line 1,837:
internal readonly record struct Square (int Row, int Col);
internal readonly record struct Square (int Row, int Col);
internal record Constraints (IEnumerable<int> ConstrainedRange, Square Square);
internal record Constraints (IEnumerable<int> ConstrainedRange, Square Square);
internal class Cache : Dictionary<Square, IEnumerable<Constraints>> { };
internal class Cache : Dictionary<Square, Constraints> { };
internal record CacheGrid (int[][] Grid, Cache Cache);
internal record CacheGrid (int[][] Grid, Cache Cache);


Line 1,846: Line 1,846:
private static int RowCol(int rc) => rc <= 2 ? 0 : rc <= 5 ? 3 : 6;
private static int RowCol(int rc) => rc <= 2 ? 0 : rc <= 5 ? 3 : 6;


private static bool Solve(this CacheGrid cg, IEnumerable<Constraints> constraints, int finished) {
private static bool Solve(this CacheGrid cg, Constraints constraints, int finished) {
foreach (var sc in constraints) {
var (row, col) = constraints.Square;
var (row, col) = sc.Square;
foreach (var i in constraints.ConstrainedRange) {
foreach (var i in sc.ConstrainedRange) {
cg.Grid[row][col] = i;
cg.Grid[row][col] = i;
if (cg.Cache.Count == finished || cg.Solve(cg.Next(constraints.Square), finished))
if (cg.Cache.Count == finished || cg.Solve(cg.Next(sc.Square), finished))
return true;
return true;
}
⚫
cg.Grid[row][col] = 0;
return false;
}
}
⚫
cg.Grid[row][col] = 0;
return false;
return false;
}
}
Line 1,877: Line 1,874:
range.Where(val => grid.Valid(row, col, val));
range.Where(val => grid.Valid(row, col, val));


private static IEnumerable<Constraints> Next(this CacheGrid cg, Square square) =>
private static Constraints Next(this CacheGrid cg, Square square) =>
cg.Cache.ContainsKey(square)
cg.Cache.ContainsKey(square)
? cg.Cache[square]
? cg.Cache[square]
: cg.Cache[square]=cg.Grid.SortedCells();
: cg.Cache[square]=cg.Grid.SortedCells();


private static IEnumerable<Constraints> SortedCells(this int[][] grid) =>
private static Constraints SortedCells(this int[][] grid) =>
(from row in domain
(from row in domain
from col in domain
from col in domain
where grid[row][col] == 0
where grid[row][col] == 0
let cell = new Constraints(grid.Constraints(row, col), new Square(row, col))
let cell = new Constraints(grid.Constraints(row, col), new Square(row, col))
group cell by cell.ConstrainedRange.Count() into groupedCells
orderby cell.ConstrainedRange.Count() ascending
orderby groupedCells.Key ascending
select cell).First();
select groupedCells).First();


private static CacheGrid Parse(string input) =>
private static CacheGrid Parse(string input) =>
Line 1,947: Line 1,943:
}</lang>
}</lang>
Output
Output
<pre>
<pre>693784512
693784512
487512936
487512936
125963874
125963874
Line 1,957: Line 1,952:
856129743
856129743
274836159
274836159
000000010400000000020000000000050407008000300001090000300400200050100000000806000: 165 ms
000000010400000000020000000000050407008000300001090000300400200050100000000806000: 336 ms
Doing 100 puzzles
Doing 100 puzzles
....................................................................................................
....................................................................................................
Puzzles:100, Total:6131 ms, Average:61.31 ms</pre>
Puzzles:100, Total:5316 ms, Average:53.16 ms</pre>


===“Automatic” Solution===
===“Automatic” Solution===
Retrieved from "https://rosettacode.org/wiki/Sudoku"