/
sudoku.java
140 lines (116 loc) · 3.16 KB
/
sudoku.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
package sudoku;
public class sudoku {
private static int[][] SUDOKU_ORIGINAL={
{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}
};
private static int[][] SUDOKU_SOLUTION={
{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}
};
private static int MAX_VALUE = 9;
private int[][] board;
private int sizeRows;
private int sizeColumns;
public sudoku(int[][] original_board){
sizeRows = original_board.length;
sizeColumns = original_board[0].length;
this.board = new int[sizeRows][sizeColumns];
for (int row=0; row<sizeRows; row++){
for (int column=0; column<sizeColumns; column++){
this.board[row][column] = original_board[row][column];
}
}
}
public static void print_sudoku(int[][] board){
for (int row=0 ; row<board.length ; row++){
for (int column=0 ; column<board.length ; column++){
System.out.print(board[row][column] + " ");
}
System.out.println();
}
}
public int get_rows(){
return sizeRows;
}
public int get_columns(){
return sizeColumns;
}
public boolean isValidRow(int row, int column, int value){
for (int i=0; i<sizeRows; i++){
if (value == board[row][i] && i != column){
return false;
}
}
return true;
}
public boolean isValidColumn(int row, int column, int value){
for (int i=0; i<sizeColumns; i++){
if (value == board[i][column] && i != row){
return false;
}
}
return true;
}
public boolean isValidGrid(int row, int column, int value){
int startGridRow=(row / 3) * 3;
int startGridColumn=(column / 3) * 3;
for (int i=startGridRow; i<startGridRow+3; i++){
for (int j=startGridColumn; j<startGridColumn+3; j++){
if (value == board[i][j] && i != row && j != column){
return false;
}
}
}
return true;
}
public boolean isValidNumber(int row, int column, int value){
return isValidGrid(row, column, value) && isValidRow(row, column, value) && isValidColumn(row, column, value);
}
public boolean solve(){
for (int r = 0; r < sizeRows; r++){
for (int c = 0; c < sizeColumns; c++){
if (board[r][c] == 0){
for (int i = 1; i<=MAX_VALUE; i++){
if (isValidNumber(r, c, i)){
board[r][c] = i;
if (solve()){
return true;
} else {
board[r][c] = 0;
}
}
}
return false;
}
}
}
return true;
}
public static void main(String[] args) {
sudoku game = new sudoku (SUDOKU_ORIGINAL);
if (game.solve()){
System.out.println("Sudoku solved!!!");
System.out.println("Default solution");
sudoku.print_sudoku(SUDOKU_SOLUTION);
System.out.println("My solution");
sudoku.print_sudoku(game.board);
} else {
System.out.println("The sudoku can't be solved");
}
}
}