Sudoku: Difference between revisions

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


=== Functional Recursive Backtrack Solution===
=== "Smart" Recursive Backtrack Solution===
<!-- By Martin Freedman, 20/11/2021 -->
<!-- By Martin Freedman, 20/11/2021 -->
Still needs profiling/hot path tuning:
<lang csharp>using System.Linq;
<lang csharp>using System.Linq;
using static System.Linq.Enumerable;
using static System.Linq.Enumerable;
using System.Collections.Generic;
using System.Collections.Generic;
using System;
using System;
using System.Runtime.CompilerServices;


namespace Sudoku {
namespace Sudoku {
internal static class Sudoku {
internal static class Sudoku {
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static bool Unique(this IEnumerable<int> values) => values.Distinct().Count() == values.Count();
private static bool IsUnequal(this IEnumerable<int> values) => values.Where(c => c != 0).Unique();
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 r,int c)> GetBoxIndices(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)
from c in Range(RowCol(col), 3)
select grid[r][c];
select (r,c);


private static bool Constraints(this int[][] grid, int row, int col) =>
private static readonly Dictionary<(int r, int c), List<(int r, int c)>> Boxes =
grid[row].IsUnequal() &&
(from row in Range(0, 3).Select(i => i * 3)
Range(0, 9).Select(r => grid[r][col]).IsUnequal() &&
from col in Range(0, 3).Select(i => i * 3)
GetBox(grid, row, col).IsUnequal();
select ((row, col), GetBoxIndices(row, col)))
.ToDictionary(kvp => kvp.Item1, kvp => kvp.Item2.ToList());


private static IEnumerable<int> Hints(this int[][] grid, int row, int col) =>
private static IEnumerable<int> GetBox(int[][] grid, int row, int col) =>
grid[row].Distinct()
Boxes[(RowCol(row), RowCol(col))].Select(p=>grid[p.r][p.c]);

⚫
.Union(Range(0, 9).Select(r => grid[r][col]).Distinct())
.Union(GetBox(grid, row, col).Distinct())
private static readonly int[] Domain = Range(1, 9).ToArray();

⚫
.Where(c => c != 0);
⚫
private static bool Solve(this int[][] grid, List<(int, int)> cells, int idx) {
⚫
⚫
private static IEnumerable<(int, int)> SortedCells(this int[][] grid) =>
⚫
from row in Range(0, 9)
⚫
from col in Range(0, 9)
⚫
let cell = (count: Hints(grid, row, col).Count(), cell: (row, col))
⚫
orderby cell.count descending
⚫
select cell.cell;
⚫
private static bool Solve(this int[][] grid, List<(int,int)> cells, int idx) {
if (idx == 81)
if (idx == 81)
return true;
return true;


var (r, c) = cells[idx];
var (r, c) = cells[idx];
if (grid[r][c] != 0)
foreach (var i in Domain.Except(grid.Hints(r,c))) {
return grid.Solve(cells,idx+1);
grid[r][c] = i;
⚫
if (grid.Solve(cells, idx + 1))

foreach (var i in Range(1, 9)) {
return true;
grid[r][c] = i;
⚫
if (grid.Constraints(r, c) && grid.Solve(cells,idx+1))
return true;
}
}
grid[r][c] = 0;
grid[r][c] = 0;
return false;
return false;
}
}

private static readonly int[] Unmarked = new[] { 0 };

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

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


private static int[][] Parse(string input) =>
private static int[][] Parse(string input) =>
input
input
.Select((c, i) => (index: i, val: int.Parse(c.ToString())))
.Select((c, i) => (index: i, val: int.Parse(c.ToString())))
.GroupBy(id => id.index / 9).Select(grp => grp.Select(id => id.val).ToArray())
.GroupBy(id => id.index / 9)
.Select(grp => grp.Select(id => id.val).ToArray())
.ToArray();
.ToArray();


Line 1,890: Line 1,897:
public static int[][] Run(string input) {
public static int[][] Run(string input) {
var grid = Parse(input);
var grid = Parse(input);
return grid.Solve(grid.SortedCells().ToList(), 0) ? grid : new int[][]{ Array.Empty<int>() };
var hits = input.Where(c => c != '0').Count();
var sorted = grid.SortedCells().ToList();
return grid.Solve(sorted, hits) ? grid : new int[][] { Array.Empty<int>() };
}
}
}
}
Line 1,900: Line 1,909:
static class Program {
static class Program {
static void Main(string[] args) {
static void Main(string[] args) {
//https://staffhome.ecm.uwa.edu.au/~00013890/sudoku17 format
var puzzle = "000028000800010000000000700000600403200004000100700000030400500000000010060000000";
var puzzle = "000028000800010000000000700000600403200004000100700000030400500000000010060000000";
WriteLine(Sudoku.Run(puzzle).AsString());
WriteLine(Sudoku.Run(puzzle).AsString());
Line 1,906: Line 1,916:
}
}
}</lang>
}</lang>
Output
Output
<pre>
<pre>
617328945
617328945
Retrieved from "https://rosettacode.org/wiki/Sudoku"