-
Notifications
You must be signed in to change notification settings - Fork 0
/
SudokuSolver.java
98 lines (87 loc) · 3.01 KB
/
SudokuSolver.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
package Sudoku;
public class SudokuSolver {
public static boolean isSafe(char[][] board, int row, int col, int num){
//row & column
for(int i=0;i< board.length;i++){
if(board[i][col]==(char) (num+'0')){
return false;//coz num is equal to the value already present in the row
}
if(board[row][i]==(char) (num+'0')){
return false;//coz num is equal to the value already present in the col
}
}
//grid
int sr=(row/3)*3;
int sc=(col/3)*3;
for(int i=sr;i<sr+3;i++){
for(int j=sc;j<sc+3;j++){
if(board[i][j]==(char) (num+'0')){
return false;
}
}
}
return true;
}
public static boolean helper(char[][] board, int row, int col){
if(row== board.length){
return true;
}
int nrow=0;
int ncol=0;
if(col!= board.length-1){
nrow=row;
ncol=col+1;
}else{
nrow=row+1;
ncol=0;
}
if(board[row][col]!='.') {
if (helper(board, nrow, ncol)) {
return true;
}
}
else {
for(int i=1;i<=9;i++){
if(isSafe(board,row,col,i)){
board[row][col]=(char) (i+'0');
if(helper(board,nrow,ncol)){
return true;
}
else {
board[row][col]='.';
}
}
}
}
return false;//when nothing is true
}
public static void solveSudoku(char[][] board){
helper(board,0,0);
}
public static void main(String[] args) {
char[][] board = {
{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
};
System.out.println("Sudoku board before solving:");
printBoard(board);
SudokuSolver.solveSudoku(board);
System.out.println("Sudoku board after solving:");
printBoard(board);
}
public static void printBoard(char[][] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}