JAva解数独
10722 ワード
まず解く数独を入力し,多次元配列を用いて値を保存し,数字が記入されていない箇所を0に初期化し,次いで再帰的な方法で数独を解く.
直接コード:
未処理:
8 0 0 | 0 0 0 | 0 0 0 0 0 3 | 6 0 0 | 0 0 0 0 7 0 | 0 9 0 | 2 0 0 -----------------------0 5 0 | 0 0 7 | 0 0 0 0 0 0 | 0 4 5 | 7 0 0 0 0 0 | 1 0 0 | 0 3 0 -----------------------0 0 1 | 0 0 0 | 0 6 8 0 0 8 | 5 0 0 | 0 1 0 0 9 0 | 0 0 0 | 4 0 0
処理後:
8 1 2 | 7 5 3 | 6 4 9 9 4 3 | 6 8 2 | 1 7 5 6 7 5 | 4 9 1 | 2 8 3 -----------------------1 5 4 | 2 3 7 | 8 9 6 3 6 9 | 8 4 5 | 7 2 1 2 8 7 | 1 6 9 | 5 3 4 -----------------------5 2 1 | 9 7 4 | 3 6 8 4 3 8 | 5 2 6 | 9 1 7 7 9 6 | 3 1 8 | 4 5 2
直接コード:
/**
*
* @author walker
*
*/
public class Sudoku {
private int[][] sudoku;
public Sudoku(int[][] sudoku) {
this.sudoku = sudoku;
}
/**
*
*
* @param sudoku
*/
public void print(int[][] sudoku) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(sudoku[i][j] + " ");
if (j == 2 || j == 5) {
System.out.print(" | ");
}
}
System.out.println();
if (i == 2 || i == 5) {
System.out.println("-----------------------");
}
}
}
private boolean work(int row, int col) {
int i, j, x, x1, y, y1;
// ,
if (col > 8) {
row++;
col = 0;
}
// ,
if (row > 8) {
return true;
}
// 0, ,
if (sudoku[row][col] != 0) {
return work(row, col + 1);
}
//
for (i = 1; i < 10; i++) {
//
for (j = 0; j < 9; j++) {
if (sudoku[row][j] == i)
break;
}
if (j < 9) { // ,
continue;
}
//
for (j = 0; j < 9; j++) {
if (sudoku[j][col] == i)
break;
}
if (j < 9) { // ,
continue;
}
// 3*3
j = 0;
x1 = row / 3 * 3 + 3;
y1 = col / 3 * 3 + 3;
for (x = row / 3 * 3; x < x1; x++) {
if (j == 1)
break;
for (y = col / 3 * 3; y < y1; y++) {
if (sudoku[x][y] == i) {
j = 1;
break;
}
}
}
// ,
if (j == 1) {
continue;
}
sudoku[row][col] = i;//
//
if (work(row, col + 1)) {
return true; // ,
}
// , ,
sudoku[row][col] = 0;
}
sudoku[row][col] = 0;
//
return false;
}
public void start() {
print(sudoku);
work(0, 0);
System.out.println("
-----------------------
");
print(sudoku);
}
/**
* @param args
*/
public static void main(String[] args) {
int[][] sudokuArray = {
{ 8, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 3, 6, 0, 0, 0, 0, 0 },
{ 0, 7, 0, 0, 9, 0, 2, 0, 0 },
{ 0, 5, 0, 0, 0, 7, 0, 0, 0 },
{ 0, 0, 0, 0, 4, 5, 7, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 3, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 6, 8 },
{ 0, 0, 8, 5, 0, 0, 0, 1, 0 },
{ 0, 9, 0, 0, 0, 0, 4, 0, 0 } };
Sudoku sudoku = new Sudoku(sudokuArray);
sudoku.start();
}
}
未処理:
8 0 0 | 0 0 0 | 0 0 0 0 0 3 | 6 0 0 | 0 0 0 0 7 0 | 0 9 0 | 2 0 0 -----------------------0 5 0 | 0 0 7 | 0 0 0 0 0 0 | 0 4 5 | 7 0 0 0 0 0 | 1 0 0 | 0 3 0 -----------------------0 0 1 | 0 0 0 | 0 6 8 0 0 8 | 5 0 0 | 0 1 0 0 9 0 | 0 0 0 | 4 0 0
処理後:
8 1 2 | 7 5 3 | 6 4 9 9 4 3 | 6 8 2 | 1 7 5 6 7 5 | 4 9 1 | 2 8 3 -----------------------1 5 4 | 2 3 7 | 8 9 6 3 6 9 | 8 4 5 | 7 2 1 2 8 7 | 1 6 9 | 5 3 4 -----------------------5 2 1 | 9 7 4 | 3 6 8 4 3 8 | 5 2 6 | 9 1 7 7 9 6 | 3 1 8 | 4 5 2