SudokuSolver/Solver.java at main · sayan3429/SudokuSolver · GitHub

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
140
141
public class Solver {
    public static boolean checkRow(SudokuSolver test, int i, int j){
        for (int col=0; col<9; col++){
            if (col == j) continue;
            if(test.sudoku[i][col] == test.sudoku[i][j] && test.sudoku[i][col] != 0){
                return false;
            }
        }
        return true;
    }
    public static boolean checkColumn(SudokuSolver test, int i, int j){
        for (int row=0; row<9; row++){
            if (row == i) continue;
            if(test.sudoku[row][j] == test.sudoku[i][j] && test.sudoku[row][j] != 0){
                return false;
            }
        }
        return true;
    }
    public static int[] getBox(int i, int j){
        if (i == 0 || i == 1 || i == 2){
            if (j == 0 || j == 1 || j == 2){
                return new int[] {0,0};
            }
            else if(j == 3 || j == 4 || j == 5){
                return new int[] {0, 3};
            }
            else{
                return new int[] {0, 6};
            }
        }
        else if (i == 3 || i == 4 || i == 5){
            if (j == 0 || j == 1 || j == 2){
                return new int[] {3,0};
            }
            else if(j == 3 || j == 4 || j == 5){
                return new int[] {3, 3};
            }
            else{
                return new int[] {3, 6};
            }
        }else{
            if (j == 0 || j == 1 || j == 2){
                return new int[] {6,0};
            }
            else if(j == 3 || j == 4 || j == 5){
                return new int[] {6, 3};
            }
            else{
                return new int[] {6, 6};
            }
        }
    }
    public static boolean checkBox(SudokuSolver test, int i, int j){
        int[] startingPt = getBox(i, j);
        for(int row = startingPt[0]; row < startingPt[0] + 3; row++){
            for(int col = startingPt[1]; col < startingPt[1] + 3; col++){
                if (row == i && col == j) continue;
                if(test.sudoku[row][col] == test.sudoku[i][j] && test.sudoku[row][col] != 0){
                    return false;
                }
            }
        }
        return true;
    }
    public static boolean isValidcheck(SudokuSolver test){
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if (checkRow(test, i, j) && checkColumn(test, i, j) && checkBox(test, i, j)){
                    continue;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
    public static boolean isEmpty(int cell){
        if (cell >= 1 && cell <= 9) return false;
        return true;
    }
    public static void solve(SudokuSolver test, int i, int j) {
        if (i == 8 && j == 9) {
            test.show();
            return;
        }
        if(j >= 9 && i < 8){
            solve(test, i+1,  0);
            return;
        }
        if(isEmpty(test.sudoku[i][j])){
            for(int val = 1; val <= 9; val++){
                test.sudoku[i][j] = val;
                if (checkRow(test, i, j) && checkColumn(test, i, j) && checkBox(test, i, j)) {
                    solve(test, i, j+1);
                }
                test.sudoku[i][j] = 0;
            }
        } else {
            solve(test, i, j+1);
        }
    }
    public static void updateResult(int[][] result, int[][] solution) {
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                solution[i][j] = result[i][j];
            }
        }
    }
    public static boolean solveAndGetFirstSolution(SudokuSolver test, int i, int j, int[][] solution) {
        if (i == 8 && j == 9) {
            updateResult(test.sudoku, solution);
            return true;
        }
        if(j >= 9 && i < 8){
            if (solveAndGetFirstSolution(test, i+1,  0, solution)) {
                return true;
            }
            return false;
        }
        if(isEmpty(test.sudoku[i][j])){
            for(int val = 1; val <= 9; val++){
                test.sudoku[i][j] = val;
                if (checkRow(test, i, j) && checkColumn(test, i, j) && checkBox(test, i, j)) {
                    if (solveAndGetFirstSolution(test, i, j+1, solution)) {
                        return true;
                    }
                }
                test.sudoku[i][j] = 0;
            }
        } else {
            if (solveAndGetFirstSolution(test, i, j+1, solution)) {
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        new GUI_ss();
    }
}