複製內容到剪貼板
代碼:
import java.io.*;
public class sudoku {
static void SolvePuzzle() {
GetAns();
}
static boolean GetAns() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (puzzle[i][j] <= 0) {
next_value:for (int value = 1; value <= 9; value++) {
// On the same column, make sure no any row already used it
// On the same row, make sure no any column already used it
for (int k = 0; k < 9; k++) {
if ( (puzzle[k][j] == value) || (puzzle[i][k] == value)) {
continue next_value;
}
}
// On the 3x3 box, make sure no other cell already used it
int p = (i / 3) * 3;
int q = (j / 3) * 3;
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
if (puzzle[p + x][q + y] == value) {
continue next_value;
}
}
}
puzzle[i][j] = (byte) value;
if (GetAns()) {
return true;
}
else {
puzzle[i][j] = 0;
}
}
return false;
}
}
}
return true;
}
public static void main(String[] args) {
String datafile = "sudoku.txt";
if (args.length > 1) {
datafile = args[0];
}
System.out.println("Read puzzle file:" + datafile);
ReadPuzzle(datafile);
PrintPuzzle();
// Solve the puzzle
long starttime = System.currentTimeMillis();
SolvePuzzle();
long endtime = System.currentTimeMillis();
System.out.println("\nSolve puzzle in " + (endtime - starttime) +
" microseconds.");
PrintPuzzle();
boolean success = CheckRule();
if (success) {
System.out.println("Good Job!");
}
else {
System.out.println("Oops! test failed, try again.");
}
}
static void ReadPuzzle(String file) {
try {
BufferedReader in = new BufferedReader(new FileReader(file));
String str;
for (int r = 0; r < 9; r++) {
try {
str = in.readLine();
}
catch (IOException e1) {
str = "";
}
for (int c = 0; c < 9; c++) {
puzzle[r][c] = 0;
if (str.length() > c) {
puzzle[r][c] = (byte) (str.charAt(c) - '0');
}
}
}
}
catch (FileNotFoundException e) {
e.printStackTrace();
return;
}
}
static void PrintPuzzle() {
int row, col;
System.out.println(" |123456789");
System.out.println("-+---------");
for (row = 0; row < 9; row++) {
System.out.print(row + 1);
System.out.print("|");
for (col = 0; col < 9; col++) {
byte b = puzzle[row][col];
if (b < 1 || b > 9) {
System.out.print('-');
}
else {
System.out.print(puzzle[row][col]);
}
}
System.out.println("");
}
System.out.println("-+---------");
}
static boolean CheckRule() {
int[] row_score = {
0, 0, 0, 0, 0, 0, 0, 0, 0};
int[] col_score = {
0, 0, 0, 0, 0, 0, 0, 0, 0};
int[] box_score = {
0, 0, 0, 0, 0, 0, 0, 0, 0};
int r, c, box_r, box_c;
int score = 0;
for (r = 0; r < 9; r++) {
for (c = 0; c < 9; c++) {
// check row
byte b = puzzle[r][c];
if (b < 1 || b > 9) {
System.out.println("(" + (r + 1) + "," + (c + 1) + ") unknown data.");
return false;
}
b--;
if (row_score[b] != score) {
System.out.println("Row " + (r + 1) + " test failed.");
return false;
}
else {
row_score[b]++;
}
// check column
b = puzzle[c][r];
if (b < 1 || b > 9) {
System.out.println("(" + (r + 1) + "," + (c + 1) + ") unknown data.");
return false;
}
b--;
if (col_score[b] != score) {
System.out.println("Column " + (r + 1) + " test failed.");
return false;
}
else {
col_score[b]++;
}
// check 3*3 box
box_r = (r / 3) * 3 + (c / 3);
box_c = (r % 3) * 3 + (c % 3);
b = puzzle[box_r][box_c];
if (b < 1 || b > 9) {
System.out.println("(" + (box_r + 1) + "," + (box_c + 1) +
") unknown data.");
return false;
}
b--;
if (box_score[b] != score) {
System.out.println("Box test failed at (" + (box_r + 1) + "," +
(box_c + 1) + ").");
return false;
}
else {
box_score[b]++;
}
}
score++;
}
return true;
}
static byte[][] puzzle = {
{
1, 2, 3, 4, 5, 6, 7, 8, 9}
, {
1, 2, 3, 4, 5, 6, 7, 8, 9}
, {
1, 2, 3, 4, 5, 6, 7, 8, 9}
, {
1, 2, 3, 4, 5, 6, 7, 8, 9}
, {
1, 2, 3, 4, 5, 6, 7, 8, 9}
, {
1, 2, 3, 4, 5, 6, 7, 8, 9}
, {
1, 2, 3, 4, 5, 6, 7, 8, 9}
, {
1, 2, 3, 4, 5, 6, 7, 8, 9}
, {
1, 2, 3, 4, 5, 6, 7, 8, 9}
};
}
