Rosetta Code

Sudoku: Difference between revisions

Page Discussion

Sudoku (view source)

Revision as of 17:24, 20 November 2021

206 bytes removed ,  2 years ago
Changed my →‎“Amb” Solution: to better and shorter →‎Recursive Backtrack Solution
m (→‎{{header|Tailspin}}: handle autotyping of tagged identifiers)
Line 1,825:
}
}</lang>
===“Amb” 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}}
<!-- By Martin Freedman, 920/0211/20182021 -->
<lang csharp>using System.Linq;
using static System.Linq.Enumerable;
using static System.Console;
using AmbSystem.Collections.Generic;
 
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",
"861 750 000",
Line 1,850 ⟶ 1,889:
"040 007 300" };
 
var Solveinput = challenge
.Select(r => r.Where(c => c != ' ').Select(c => (int)c - '0').ToArray())
.ToArray();
 
var amb(success, result) = new Amb.AmbSolve(input, 0, 0);
 
varif matrix = new IValue<int>[9][];(success)
var domain = new []{0,for 1,(var 2,r 3,= 4,0; 5,r 6, 7, 8,< 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");
}
}
else
{ WriteLine("No Solution");
WriteLineReadLine("Amb is angry!");
}
Read();
}
}
Line 1,928 ⟶ 1,919:
146897325
</pre>
 
 
===“Automatic” Solution===
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/121353"