Java Sudoku Solver
COLLECTED BY
Organization:
Alexa Crawls
Starting in 1996,
Alexa Internet
has been donating their crawl data to the Internet Archive. Flowing in every day, these data are added to the
Wayback Machine
after an embargo period.
this data is currently not publicly accessible.
The Wayback Machine - https://web.archive.org/web/20060613170544/http://www.colloquial.com:80/games/sudoku/java_sudoku.html
Java Sudoku Solver
by
Bob Carpenter
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.java
The 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>The algorithm employed is similar to the standard backtracking
* <a href="http://en.wikipedia.org/wiki/Eight_queens_puzzle">eight
* queens algorithm</a>.
*
* <p>See <a href="http://en.wikipedia.org/wiki/Sudoku">Wikipedia:
* Sudoku</a> for more information on Sudoku.
*
* @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 rowOffset = (i / 3)*3;
int colOffset = (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(" -----------------------");
}
}
Compiling and Running
Sudoku.java
The 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
$