This page contains a complete Java implementation of a Sudoku puzzle solver. The implementation is similar to the standard backtracking approach to the eight queens puzzle. It solves newspaper puzzles in the blink of an eye.
Download: Sudoku.java (license: Apache 2.0)
Sudoku.javaThe file Sudoku.java is reproduced below; the documentation
explains how it works.
/**
* The <code>Sudoku</code> class povides a static <code>main</code>
* method allowing it to be called from the command line to print the
* solution to a specified Sudoku problem.
*
* <p>The following is an example of a Sudoku problem:
*
* <pre>
* -----------------------
* | 8 | 4 2 | 6 |
* | 3 4 | | 9 1 |
* | 9 6 | | 8 4 |
* -----------------------
* | | 2 1 6 | |
* | | | |
* | | 3 5 7 | |
* -----------------------
* | 8 4 | | 7 5 |
* | 2 6 | | 1 3 |
* | 9 | 7 1 | 4 |
* -----------------------
* </pre>
*
* The goal is to fill in the missing numbers so that
* every row, column and box contains each of the numbers
* <code>1-9</code>. Here is the solution to the
* problem above:
*
* <pre>
* -----------------------
* | 1 8 7 | 4 9 2 | 5 6 3 |
* | 5 3 4 | 6 7 8 | 9 1 2 |
* | 9 6 2 | 1 3 5 | 7 8 4 |
* -----------------------
* | 4 5 8 | 2 1 6 | 3 9 7 |
* | 2 7 3 | 8 4 9 | 6 5 1 |
* | 6 1 9 | 3 5 7 | 4 2 8 |
* -----------------------
* | 8 4 1 | 9 6 3 | 2 7 5 |
* | 7 2 6 | 5 8 4 | 1 3 9 |
* | 3 9 5 | 7 2 1 | 8 4 6 |
* -----------------------
* </pre>
*
* Note that the first row <code>187492563</code> contains
* each number exactly once, as does the first column
* <code>159426873</code>, the upper-left box
* <code>187534962</code>, and every other row, column
* and box.
*
* <p>The {@link #main(String[])} method encodes a problem as an array
* of strings, with one string encoding each constraint in the problem
* in row-column-value format. Here is the problem again with
* the indices indicated:
*
* <pre>
* 0 1 2 3 4 5 6 7 8
* -----------------------
* 0 | 8 | 4 2 | 6 |
* 1 | 3 4 | | 9 1 |
* 2 | 9 6 | | 8 4 |
* -----------------------
* 3 | | 2 1 6 | |
* 4 | | | |
* 5 | | 3 5 7 | |
* -----------------------
* 6 | 8 4 | | 7 5 |
* 7 | 2 6 | | 1 3 |
* 8 | 9 | 7 1 | 4 |
* -----------------------
* </pre>
*
* The <code>8</code> in the upper left box of the puzzle is encoded
* as <code>018</code> (<code>0</code> for the row, <code>1</code> for
* the column, and <code>8</code> for the value). The <code>4</code>
* in the lower right box is encoded as <code>874</code>.
*
* <p>The full command-line invocation for the above puzzle is:
*
* <pre>
* % java -cp . Sudoku 018 034 052 076 \
* 113 124 169 171 \
* 209 216 278 284 \
* 332 341 356 \
* 533 545 557 \
* 608 614 677 685 \
* 712 726 761 773 \
* 819 837 851 874 \
* </pre>
*
* <p>See <a href="http://en.wikipedia.org/wiki/Sudoku">Wikipedia:
* Sudoku</a> for more information on Sudoku.
*
* <p>The algorithm employed is similar to the standard backtracking
* <a href="http://en.wikipedia.org/wiki/Eight_queens_puzzle">eight
* queens algorithm</a>.
*
* @version 1.0
* @author <a href="http://www.colloquial.com/carp">Bob Carpenter</a>
*/
public class Sudoku {
/**
* Print the specified Sudoku problem and its solution. The
* problem is encoded as specified in the class documentation
* above.
*
* @param args The command-line arguments encoding the problem.
*/
public static void main(String[] args) {
int[][] matrix = parseProblem(args);
writeMatrix(matrix);
if (solve(0,0,matrix)) // solves in place
writeMatrix(matrix);
else
System.out.println("NONE");
}
static boolean solve(int i, int j, int[][] cells) {
if (i == 9) {
i = 0;
if (++j == 9)
return true;
}
if (cells[i][j] != 0) // skip filled cells
return solve(i+1,j,cells);
for (int val = 1; val <= 9; ++val) {
if (legal(i,j,val,cells)) {
cells[i][j] = val;
if (solve(i+1,j,cells))
return true;
}
}
cells[i][j] = 0; // reset on backtrack
return false;
}
static boolean legal(int i, int j, int val, int[][] cells) {
for (int k = 0; k < 9; ++k) // row
if (val == cells[k][j])
return false;
for (int k = 0; k < 9; ++k) // col
if (val == cells[i][k])
return false;
int boxRowOffset = (i / 3)*3;
int boxColOffset = (j / 3)*3;
for (int k = 0; k < 3; ++k) // box
for (int m = 0; m < 3; ++m)
if (val == cells[boxRowOffset+k][boxColOffset+m])
return false;
return true; // no violations, so it's legal
}
static int[][] parseProblem(String[] args) {
int[][] problem = new int[9][9]; // default 0 vals
for (int n = 0; n < args.length; ++n) {
int i = Integer.parseInt(args[n].substring(0,1));
int j = Integer.parseInt(args[n].substring(1,2));
int val = Integer.parseInt(args[n].substring(2,3));
problem[i][j] = val;
}
return problem;
}
static void writeMatrix(int[][] solution) {
for (int i = 0; i < 9; ++i) {
if (i % 3 == 0)
System.out.println(" -----------------------");
for (int j = 0; j < 9; ++j) {
if (j % 3 == 0) System.out.print("| ");
System.out.print(solution[i][j] == 0
? " "
: Integer.toString(solution[i][j]));
System.out.print(' ');
}
System.out.println("|");
}
System.out.println(" -----------------------");
}
}
Sudoku.javaThe following session provides an example of how to compile and run the code (assuming you have the Java developer's kit installed).
Bob Carpenter@ry /cygdrive/c/mycvs/carp $ cd sudoku/ Bob Carpenter@ry /cygdrive/c/mycvs/carp/sudoku $ ls -l Sudoku.java -rwxr-xr-x 1 Bob Carpenter None 5285 Apr 27 23:59 Sudoku.java Bob Carpenter@ry /cygdrive/c/mycvs/carp/sudoku $ javac Sudoku.java Bob Carpenter@ry /cygdrive/c/mycvs/carp/sudoku $ ls -l Sudoku.class -rwxr-xr-x 1 Bob Carpenter None 1600 Apr 28 00:01 Sudoku.class Bob Carpenter@ry /cygdrive/c/mycvs/carp/sudoku $ java -cp . Sudoku 014 023 037 069 088 \ 125 143 211 263 306 342 357 404 427 461 483 \ 535 544 589 622 673 745 764 805 824 851 862 876 ----------------------- | 4 3 | 7 | 9 8 | | 5 | 3 | | | 1 | | 3 | ----------------------- | 6 | 2 7 | | | 4 7 | | 1 3 | | | 5 4 | 9 | ----------------------- | 2 | | 3 | | | 5 | 4 | | 5 4 | 1 | 2 6 | ----------------------- ----------------------- | 2 4 3 | 7 1 6 | 9 5 8 | | 9 8 5 | 2 3 4 | 7 1 6 | | 7 1 6 | 8 9 5 | 3 4 2 | ----------------------- | 6 3 9 | 1 2 7 | 5 8 4 | | 4 5 7 | 9 6 8 | 1 2 3 | | 8 2 1 | 5 4 3 | 6 7 9 | ----------------------- | 1 6 2 | 4 7 9 | 8 3 5 | | 3 7 8 | 6 5 2 | 4 9 1 | | 5 9 4 | 3 8 1 | 2 6 7 | ----------------------- Bob Carpenter@ry /cygdrive/c/mycvs/carp/sudoku $