Sudoku: Difference between revisions
Content deleted Content added
m →{{header|Groovy}}: formatting |
New D entry that solves far more Sudokus |
||
Line 1,496: | Line 1,496: | ||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|C++}} |
|||
<lang d>import std.stdio: writeln; |
|||
import std.string |
<lang d>import std.stdio, std.range, std.string, std.algorithm, std.array; |
||
string sudokuSolver(in string problem) |
|||
alias ubyte Digit; |
|||
in { |
|||
alias bool[Digit] TAval; |
|||
enum int side = 9; // dupe |
|||
alias Digit[][] TPuzzle; |
|||
assert(problem.walkLength == side ^^ 2); |
|||
assert(problem == problem.removechars("^0-9")); |
|||
} body { |
|||
enum int side = 9; |
|||
uint[side ^^ 2] grid = array(map!q{ a - '0' }(problem)); |
|||
bool checkValidity(in int val, in int x, in int y) nothrow { |
|||
enum Digit EMPTY = 0; |
|||
foreach (i; 0 .. side) |
|||
if (grid[y*side + i] == val || grid[i*side + x] == val) |
|||
return false; |
|||
immutable int startX = (x / 3) * 3; |
|||
// these three functions assume that the number has not already been found |
|||
immutable int startY = (y / 3) * 3; |
|||
pure nothrow TAval availableCol(in TPuzzle puzzle, |
|||
foreach (i; startY .. startY + 3) |
|||
in int row, in int col) { |
|||
foreach (j; startX .. startX + 3) |
|||
static pure nothrow TAval generateFull() { |
|||
if (grid[i * side + j] == val) |
|||
TAval resultSet; |
|||
return false; |
|||
return true; |
|||
return resultSet; |
|||
} |
} |
||
void placeNumber(in int pos) { |
|||
TAval available = generateFull(); |
|||
if (pos == side ^^ 2) |
|||
throw new Exception("Finished!"); |
|||
if (puzzle[i][col] != EMPTY) |
|||
if (grid[pos] > 0) { |
|||
placeNumber(pos + 1); |
|||
return available; |
|||
return; |
|||
} |
|||
} |
|||
foreach (n; 1 .. side+1) |
|||
pure nothrow TAval availableRow(in TPuzzle puzzle, |
|||
if (checkValidity(n, pos % side, pos / side)) { |
|||
grid[pos] = n; |
|||
placeNumber(pos + 1); |
|||
foreach (ele; puzzle[row]) |
|||
grid[pos] = 0; |
|||
} |
|||
} |
|||
return available; |
|||
} |
|||
try { |
|||
pure nothrow TAval availableBox(in TPuzzle puzzle, |
|||
placeNumber(0); |
|||
in int row, in int col, |
|||
return ""; // Unsolvable |
|||
TAval available) { |
|||
} catch (Exception ex) |
|||
// get a base index for the boxes |
|||
return array(map!q{ cast(char)(a + '0') }(grid[])).idup; |
|||
const int bx = (row / 3) * 3; |
|||
const int by = (col / 3) * 3; |
|||
foreach (i; 0 .. 3) |
|||
foreach (j; 0 .. 3) |
|||
if (puzzle[bx + i][by + j] != EMPTY) |
|||
available.remove(puzzle[bx + i][by + j]); |
|||
return available; |
|||
} |
} |
||
void main() { |
|||
auto data = "394..267. |
|||
...3..4.. |
|||
5..69..2. |
|||
.45...9.. |
|||
6.......7 |
|||
..7...58. |
|||
.1..67..8 |
|||
..9..8... |
|||
.264..735"; |
|||
string formatSudoku(in string sudo) |
|||
TPuzzle puzzle = new TPuzzle(9, 9); |
|||
in { |
|||
foreach (r, row; data.split()) |
|||
enum int side = 9; // dupe |
|||
assert(sudo.walkLength == side ^^ 2); |
|||
puzzle[r][c] = el == '.' ? EMPTY : cast(Digit)(el - '0'); |
|||
assert(sudo == sudo.removechars("^0-9")); |
|||
} body { |
|||
enum int side = 9; |
|||
string result; |
|||
foreach (i; 0 .. side) { |
|||
foreach (j; 0 .. side) { |
|||
result ~= sudo[i * side + j]; |
|||
result ~= ' '; |
|||
if (j == 2 || j == 5) |
|||
result ~= "| "; |
|||
} |
|||
const remaining = availableBox(puzzle, i, j, |
|||
result ~= "\n"; |
|||
availableRow(puzzle, i, j, |
|||
if (i == 2 || i == 5) |
|||
availableCol(puzzle, i, j))); |
|||
result ~= "------+-------+------\n"; |
|||
if (remaining.length == 1) |
|||
ele = remaining.keys[0]; |
|||
else |
|||
done = false; |
|||
} |
|||
if (done) |
|||
break; |
|||
} |
} |
||
return result; |
|||
// write out completed puzzle |
|||
} |
|||
writeln("Completed puzzle:"); |
|||
foreach (row; puzzle) |
|||
writeln(row); |
|||
void main() { |
|||
const problem = "850002400" ~ |
|||
"720000009" ~ |
|||
"004000000" ~ |
|||
"000107002" ~ |
|||
"305000900" ~ |
|||
"040000000" ~ |
|||
"000080070" ~ |
|||
"017000000" ~ |
|||
"000036040"; |
|||
writeln(formatSudoku(problem)); |
|||
const solution = sudokuSolver(problem); |
|||
if (solution.empty) |
|||
writeln("Unsolvable!"); |
|||
else |
|||
writeln(formatSudoku(solution)); |
|||
}</lang> |
}</lang> |
||
Output: |
Output: |
||
<pre>8 5 0 | 0 0 2 | 4 0 0 |
|||
<pre>Completed puzzle: |
|||
7 2 0 | 0 0 0 | 0 0 9 |
|||
0 0 4 | 0 0 0 | 0 0 0 |
|||
------+-------+------ |
|||
[5, 7, 1, 6, 9, 4, 8, 2, 3] |
|||
0 0 0 | 1 0 7 | 0 0 2 |
|||
3 0 5 | 0 0 0 | 9 0 0 |
|||
0 4 0 | 0 0 0 | 0 0 0 |
|||
------+-------+------ |
|||
[4, 1, 3, 5, 6, 7, 2, 9, 8] |
|||
0 0 0 | 0 8 0 | 0 7 0 |
|||
0 1 7 | 0 0 0 | 0 0 0 |
|||
0 0 0 | 0 3 6 | 0 4 0 |
|||
Many sudokus can't be solved by this program, like: |
|||
<pre>..53..... |
|||
8 5 9 | 6 1 2 | 4 3 7 |
|||
8......2. |
|||
7 2 3 | 8 5 4 | 1 6 9 |
|||
.7..1.5.. |
|||
1 6 4 | 3 7 9 | 5 2 8 |
|||
4....53.. |
|||
------+-------+------ |
|||
.1..7...6 |
|||
9 8 6 | 1 4 7 | 3 5 2 |
|||
..32...8. |
|||
3 7 5 | 2 6 8 | 9 1 4 |
|||
.6.5....9 |
|||
2 4 1 | 5 9 3 | 7 8 6 |
|||
..4....3. |
|||
------+-------+------ |
|||
.....97..</pre> |
|||
4 3 2 | 9 8 1 | 6 7 5 |
|||
6 1 7 | 4 2 5 | 8 9 3 |
|||
5 9 8 | 7 3 6 | 2 4 1 </pre> |
|||
=={{header|Delphi}}== |
=={{header|Delphi}}== |
||
Example taken from C++ |
Example taken from C++ |