Sudoku: Difference between revisions

Content added Content deleted
Line 1,826: Line 1,826:
}</lang>
}</lang>


=== "Smart" Recursive Backtrack Solution===
=== Best First Search "Smart" Backtrack Solution===
<!-- By Martin Freedman, 20/11/2021 -->
<!-- By Martin Freedman, 20/11/2021 -->
<lang csharp>using System.Linq;
<lang csharp>using System.Linq;
Line 1,834: Line 1,834:
using System.Runtime.CompilerServices;
using System.Runtime.CompilerServices;


namespace Sudoku {
namespace SodukoBestFirstSearch {
internal static class Sudoku {
internal static class SudokuBFS {
[MethodImpl(MethodImplOptions.AggressiveInlining)]
[MethodImpl(MethodImplOptions.AggressiveInlining)]
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 IEnumerable<int> GetBox(this int[][] grid, int row, int col) =>
private static IEnumerable<int> GetBox(int[][] grid, int row, int col) =>
from r in Range(RowCol(row), 3)
from r in Range(RowCol(row), 3) from c in Range(RowCol(col), 3) select grid[r][c];
from c in Range(RowCol(col), 3)
⚫
select grid[r][c];


private static readonly int[] range = Range(1, 9).ToArray();
private static readonly int[] range = Range(1, 9).ToArray();
private static bool Solve(this int[][] grid, List<(int, int)> cells, int idx) {
private static bool Solve(this int[][] grid, IEnumerable<(IEnumerable<int> constraints, int row, int col)> cells) {
if (idx == 81)
if (!cells.Any())
return true;
return true;


var (r, c) = cells[idx];
var (constraints, row, col) = cells.First();
foreach (var i in range.Except(grid.Hints(r,c))) {
foreach (var i in range.Except(constraints)) {
grid[r][c] = i;
grid[row][col] = i;
if (grid.Solve(cells, idx + 1))
if (grid.Solve(grid.SortedCells()))
return true;
return true;
}
}
grid[r][c] = 0;
grid[row][col] = 0;
return false;
return false;
}
}
Line 1,862: Line 1,860:
private static readonly int[] domain = Range(0, 9).ToArray();
private static readonly int[] domain = Range(0, 9).ToArray();


private static IEnumerable<int> Hints(this int[][] grid, int row, int col) =>
private static IEnumerable<int> Constraints(this int[][] grid, int row, int col) =>
grid[row]
grid[row]
.Union(domain.Select(r => grid[r][col]))
.Union(domain.Select(r => grid[r][col]))
.Union(grid.GetBox(row, col))
.Union(GetBox(grid, row, col))
.Except(Unmarked);
.Except(Unmarked);


private static IEnumerable<(int, int)> SortedCells(this int[][] grid) =>
private static IEnumerable<(IEnumerable<int> constraints,int row, int col)> SortedCells(this int[][] grid) =>
from row in domain
from row in domain
from col in domain
from col in domain
let cell = (count: grid[row][col] > 0 ? 10 : grid.Hints(row, col).Count(), cell: (row, col))
where grid[row][col] == 0
orderby cell.count descending
let cell = (constraints: grid.Constraints(row, col), row, col)
select cell.cell;
orderby cell.constraints.Count() descending
⚫
select cell;


private static int[][] Parse(string input) =>
private static int[][] Parse(string input) =>
Line 1,887: Line 1,886:
public static int[][] Run(string input) {
public static int[][] Run(string input) {
var grid = Parse(input);
var grid = Parse(input);
var hits = input.Where(c => c != '0').Count();
return grid.Solve(grid.SortedCells()) ? grid : new int[][] { Array.Empty<int>() };
var sorted = grid.SortedCells().ToList();
return grid.Solve(sorted, hits) ? grid : new int[][] { Array.Empty<int>() };
}
}
}
}
Retrieved from "https://rosettacode.org/wiki/Sudoku"