Rosetta Code

Sudoku: Difference between revisions

Page Discussion

Sudoku (view source)

Revision as of 13:19, 29 November 2021

196 bytes removed ,  2 years ago
m
→‎Best First Search "Smart" Backtrack Solution
Line 1,837:
internal readonly record struct Square (int Row, int Col);
internal record Constraints (IEnumerable<int> ConstrainedRange, Square Square);
internal class Cache : Dictionary<Square, IEnumerable<Constraints>> { };
internal record CacheGrid (int[][] Grid, Cache Cache);
 
Line 1,846:
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) {
foreachvar (varrow, sccol) in= constraints) { .Square;
foreach (var i in var (row, colconstraints.ConstrainedRange) = sc.Square;{
foreachcg.Grid[row][col] (var= i in sc.ConstrainedRange) {;
if (cg.Cache.Count == finished || cg.Grid[row][col] =Solve(cg.Next(constraints.Square), i;finished))
ifreturn true; (cg.Cache.Count == finished || cg.Solve(cg.Next(sc.Square), finished))
return true;
}
cg.Grid[row][col] = 0;▼
return false;
}
▲ cg.Grid[row][col] = 0;
return false;
}
Line 1,877 ⟶ 1,874:
range.Where(val => grid.Valid(row, col, val));
 
private static IEnumerable<Constraints> Next(this CacheGrid cg, Square square) =>
cg.Cache.ContainsKey(square)
? cg.Cache[square]
: cg.Cache[square]=cg.Grid.SortedCells();
 
private static IEnumerable<Constraints> SortedCells(this int[][] grid) =>
(from row in domain
from col in domain
where grid[row][col] == 0
let cell = new Constraints(grid.Constraints(row, col), new Square(row, col))
group cell byorderby cell.ConstrainedRange.Count() into groupedCellsascending
orderbyselect groupedCellscell).Key ascendingFirst();
select groupedCells).First();
 
private static CacheGrid Parse(string input) =>
Line 1,947 ⟶ 1,943:
}</lang>
Output
<pre>693784512
693784512
487512936
125963874
Line 1,957 ⟶ 1,952:
856129743
274836159
000000010400000000020000000000050407008000300001090000300400200050100000000806000: 165336 ms
Doing 100 puzzles
....................................................................................................
Puzzles:100, Total:61315316 ms, Average:6153.3116 ms</pre>
 
===“Automatic” Solution===
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/121394"