Sudoku: Difference between revisions
Content deleted Content added
m →{{header|Tailspin}}: handle autotyping of tagged identifiers |
Changed my →“Amb” Solution: to better and shorter →Recursive Backtrack Solution |
||
Line 1,825: | Line 1,825: | ||
} |
} |
||
}</lang> |
}</lang> |
||
=== |
=== Recursive Backtrack Solution=== |
||
This uses the second version of the [https://rosettacode.org/wiki/Amb#C.23 Amb C# class] in the Amb challenge |
|||
{{works with|C sharp|C#|7.1}} |
{{works with|C sharp|C#|7.1}} |
||
<!-- By Martin Freedman, |
<!-- By Martin Freedman, 20/11/2021 --> |
||
<lang csharp>using System.Linq; |
<lang csharp>using System.Linq; |
||
using static System.Linq.Enumerable; |
using static System.Linq.Enumerable; |
||
using static System.Console; |
using static System.Console; |
||
using |
using System.Collections.Generic; |
||
namespace Sudoku |
namespace Sudoku { |
||
static class Program { |
|||
{ |
|||
private static bool Unique(IEnumerable<int> values) => values.Distinct().Count() == values.Count(); |
|||
static class Program |
|||
private static bool IsUnequal(IEnumerable<int> values) => Unique(values.Where(c => c != 0)); |
|||
{ |
|||
static void Main(string[] args) |
|||
private static int RowCol(int rc) => rc <= 2 ? 0 : rc <= 5 ? 3 : 6; |
|||
{ |
|||
private static IEnumerable<int> GetBox(int[][] grid, int row, int col) => |
|||
from r in Range(RowCol(row), 3) |
|||
from c in Range(RowCol(col), 3) |
|||
select grid[r][c]; |
|||
private static bool Constraints(int[][] grid, int row, int col) => |
|||
IsUnequal(Range(0, 9).Select(c => grid[row][c])) && |
|||
IsUnequal(Range(0, 9).Select(r => grid[r][col])) && |
|||
IsUnequal(GetBox(grid, row, col)); |
|||
private static (int, int) NextEmptyCell(int[][] grid, int r, int c) { |
|||
while (r < 9 && grid[r][c] != 0) { |
|||
c = ++c % 9; |
|||
r = c == 0 ? r + 1 : r; |
|||
} |
|||
return (r, c); |
|||
} |
|||
private static (bool, int[][]) Solve(int[][] grid, int row, int col) { |
|||
var (r, c) = NextEmptyCell(grid, row, col); |
|||
if (r == 9) //success |
|||
return (true, grid); |
|||
for (var i = 1; i <= 9; i++) { |
|||
grid[r][c] = i; |
|||
if (!Constraints(grid, r, c)) |
|||
continue; |
|||
var (success, g) = Solve(grid, r, c); |
|||
if (!success) |
|||
continue; |
|||
else |
|||
return (true, g); |
|||
} |
|||
grid[r][c] = 0; //backtrack |
|||
return (false, grid); |
|||
} |
|||
static void Main(string[] args) { |
|||
var challenge = new string[]{ "970 340 060", |
var challenge = new string[]{ "970 340 060", |
||
"861 750 000", |
"861 750 000", |
||
Line 1,850: | Line 1,889: | ||
"040 007 300" }; |
"040 007 300" }; |
||
var |
var input = challenge |
||
.Select(r => r.Where(c => c != ' ').Select(c => (int)c - '0').ToArray()) |
.Select(r => r.Where(c => c != ' ').Select(c => (int)c - '0').ToArray()) |
||
.ToArray(); |
.ToArray(); |
||
var |
var (success, result) = Solve(input, 0, 0); |
||
if (success) |
|||
for (var r = 0; r < 9; r++) { |
|||
for (var c = 0; c < 9; c++) { |
|||
Write($"{result[r][c]}"); |
|||
void IsUnequal(IValue<int>[] values) => amb.Require(()=> values.Select(v => v.Value).Distinct().Count() == 9); |
|||
IValue<int>[] GetBox(IValue<int>[][] sudoku, int Ra, int Rb, int Ca, int Cb) |
|||
{ |
|||
var slice = new IValue<int>[9]; |
|||
int i = 0; |
|||
for (int row = Ra; row <= Rb; row++) |
|||
for (int col = Ca; col <= Cb; col++) |
|||
slice[i++] = sudoku[row][col]; |
|||
return slice; |
|||
} |
|||
// rows |
|||
foreach (var r in Range(0,9)) |
|||
{ |
|||
matrix[r] = new IValue<int>[9]; |
|||
var exclude = Solve[r].Where(i => i > 0).Prepend(0).ToArray(); // dont forget 0! |
|||
foreach (var c in Range(0,9)) |
|||
{ |
|||
// int cell and cell constraints |
|||
matrix[r][c] = amb.Choose<int>(domain); |
|||
if (Solve[r][c] > 0) |
|||
amb.Require(() => matrix[r][c].Value == Solve[r][c]); |
|||
else |
|||
amb.Require(() => !exclude.Contains(matrix[r][c].Value)); |
|||
// boxes |
|||
if ((r ==2 || r==5 || r==8) && (c==2 || c==5 || c==8)) |
|||
IsUnequal(GetBox(matrix, r -2, r, c -2, c)); |
|||
} |
|||
IsUnequal(Range(0,9).Select(i=>matrix[r][i]).ToArray()); |
|||
} |
|||
//cols |
|||
foreach (var c in Range(0, 9)) |
|||
{ |
|||
IsUnequal(Range(0, 9).Select(j => matrix[j][c]).ToArray()); |
|||
} |
|||
if (amb.Disambiguate()) |
|||
{ |
|||
for (var r = 0; r < 9; r++) |
|||
{ |
|||
for (var c = 0; c < 9; c++) |
|||
{ |
|||
Write($"{matrix[r][c].Value}"); |
|||
} |
} |
||
Write("\n"); |
Write("\n"); |
||
} |
} |
||
} |
|||
else |
else |
||
WriteLine("No Solution"); |
|||
ReadLine(); |
|||
} |
|||
Read(); |
|||
} |
} |
||
} |
} |
||
Line 1,928: | Line 1,919: | ||
146897325 |
146897325 |
||
</pre> |
</pre> |
||
===“Automatic” Solution=== |
===“Automatic” Solution=== |