採用されているアルゴリズムは、8 クイーン パズルを解くために使用される標準的なバックトラッキングに似ています。
これは Bob Carpenter ( http://www.colloquial.com/carp )によって提供されたクラスです。
このコード例は、数独ゲームのバックトラック解決とまったく同じ問題を解決するのに役立ちました。少し調査した後、プログラムに合わせて再コーディングすることができました。
このコードのロジックを理解するのに問題がある場合は、メッセージを返信してください。
次のコードは、彼のソース コードから直接コピーして貼り付けたものです。
/**
* 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 Sudoku2 {
/**
* 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(" -----------------------");
}
}