Sudoku: Difference between revisions

← Older edit Newer edit →

Content deleted Content added

Inline

@@ Line 1,496: / Line 1,496: @@
 =={{header|D}}==
+{{trans|C++}}
-<lang d>import std.stdio: writeln;
-import std.string: split;
+<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;
-        foreach (Digit i; 1 .. 10)
+                    return false;
-            resultSet[i] = true;
+        return true;
-        return resultSet;
     }
+    void placeNumber(in int pos) {
-    TAval available = generateFull();
-    foreach (i; 0 .. 9)
+        if (pos == side ^^ 2)
+            throw new Exception("Finished!");
-        if (puzzle[i][col] != EMPTY)
-            available.remove(puzzle[i][col]);
+        if (grid[pos] > 0) {
+            placeNumber(pos + 1);
-    return available;
+            return;
-}
+        }
+        foreach (n; 1 .. side+1)
-pure nothrow TAval availableRow(in TPuzzle puzzle,
-                                in int row, in int col,
+            if (checkValidity(n, pos % side, pos / side)) {
-                                TAval available) {
+                grid[pos] = n;
+                placeNumber(pos + 1);
-    foreach (ele; puzzle[row])
-        if (ele != EMPTY)
+                grid[pos] = 0;
-            available.remove(ele);
+            }
+    }
-    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..
-..69..2.
-                 .45...9..
-.......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())
-        foreach (c, el; row)
+    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;
-    while (true) {
+    foreach (i; 0 .. side) {
-        bool done = true;
+        foreach (j; 0 .. side) {
-        foreach (i, row; puzzle)
+            result ~= sudo[i * side + j];
-            foreach (j, ref ele; row)
+            result ~= ' ';
-                if (ele == EMPTY) {
+            if (j == 2 || j == 5)
-                    // poke at the elements that are _
+                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>
 Output:
+<pre>8 5 0 | 0 0 2 | 4 0 0
-<pre>Completed puzzle:
-[3, 9, 4, 8, 5, 2, 6, 7, 1]
+2 0 | 0 0 0 | 0 0 9
-[2, 6, 8, 3, 7, 1, 4, 5, 9]
+0 4 | 0 0 0 | 0 0 0
+------+-------+------
-[5, 7, 1, 6, 9, 4, 8, 2, 3]
-[1, 4, 5, 7, 8, 3, 9, 6, 2]
+0 0 | 1 0 7 | 0 0 2
-[6, 8, 2, 9, 4, 5, 3, 1, 7]
+0 5 | 0 0 0 | 9 0 0
-[9, 3, 7, 1, 2, 6, 5, 8, 4]
+4 0 | 0 0 0 | 0 0 0
+------+-------+------
-[4, 1, 3, 5, 6, 7, 2, 9, 8]
-[7, 5, 9, 2, 3, 8, 1, 4, 6]
+0 0 | 0 8 0 | 0 7 0
-[8, 2, 6, 4, 1, 9, 7, 3, 5]</pre>
+1 7 | 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.....
+5 9 | 6 1 2 | 4 3 7
-......2.
+2 3 | 8 5 4 | 1 6 9
-.7..1.5..
+6 4 | 3 7 9 | 5 2 8
-....53..
+------+-------+------
-.1..7...6
+8 6 | 1 4 7 | 3 5 2
-..32...8.
+7 5 | 2 6 8 | 9 1 4
-.6.5....9
+4 1 | 5 9 3 | 7 8 6
-..4....3.
+------+-------+------
-.....97..</pre>
+3 2 | 9 8 1 | 6 7 5
+1 7 | 4 2 5 | 8 9 3
+9 8 | 7 3 6 | 2 4 1 </pre>
 =={{header|Delphi}}==
 Example taken from C++