Anonymous user
Sudoku: Difference between revisions
m
→Best First Search "Smart" Backtrack Solution
Line 1,834:
using System.Runtime.CompilerServices;
namespace
internal
internal record Constraints (IEnumerable<int> ConstrainedRange, Square Square);
[MethodImpl(MethodImplOptions.AggressiveInlining)]▼
internal class Cache : Dictionary<Square, IEnumerable<Constraints>> { };
private static int RowCol(int rc) => rc <= 2 ? 0 : rc <= 5 ? 3 : 6; ▼
internal record CacheGrid (int[][] Grid, Cache Cache);
private static IEnumerable<int> GetBox(int[][] grid, int row, int col) =>▼
internal static class SudokuFastMemoBFS {
private static readonly int[] range = Range(1, 9).ToArray();▼
if (!cells.Any())▼
return true;▼
▲ [MethodImpl(MethodImplOptions.AggressiveInlining)]
var (constraints, row, col) = cells.First();▼
foreach (var i in range.Except(constraints)) {▼
grid[row][col] = i;▼
private static bool Solve(this CacheGrid cg, IEnumerable<Constraints> constraints, int finished) {
if (grid.Solve(grid.SortedCells()))▼
foreach (var sc in constraints) {
cg.Grid[row][col] = i;
if (cg.Cache.Count == finished || cg.Solve(cg.Next(sc.Square), finished))
return true;
return false;
}
▲ grid[row][col] = 0;
return false;
}
private static readonly int[] domain = Range(0, 9).ToArray();
▲ private static readonly int[] range = Range(1, 9).ToArray();
for (var i = 0; i < 9; i++)
if (grid[row][i] == val || grid[i][col] == val)
return false;
for (var r = RowCol(row); r < RowCol(row) + 3; r++)
for (var c = RowCol(col); c < RowCol(col) + 3; c++)
return false;
}
private static IEnumerable<int> Constraints(this int[][] grid, int row, int col) =>
range.Where(val => grid
private static IEnumerable<Constraints> Next(this CacheGrid cg, Square square) =>
cg.
? cg.Cache[square]
: cg.Cache[square]=cg.Grid.SortedCells();
private static IEnumerable<
(from row in domain
from col in domain
where grid[row][col] == 0
let cell =
select groupedCells).First();
private static
input
.Select((c, i) => (index: i, val: int.Parse(c.ToString())))
.GroupBy(id => id.index / 9)
.Select(grp => grp.Select(id => id.val).ToArray())
.ToArray()
.Fwd(grid => new CacheGrid(grid, new Cache()));
public static string AsString(this int[][] grid) =>
string.Join('\n', grid.Select(row => string.Concat(row)));
public static int[][] Run(string input) {
var
return cg.Solve(cg.Grid.SortedCells(), 80 - marked) ? cg.Grid : new int[][] { Array.Empty<int>() };
}
}
| |||