My simple Java solution using backtracking, beating 96.02% of java submissions


  • 0
    E
    public class Solution {
                private boolean[][] vis1;
                private boolean[][] vis2;
                private boolean[][] vis3;
                private boolean isFound;
                
                public void backTracking(char[][] board, int x, int y) {
                    if(x == 9) {
                        isFound = true;
                        return;
                    }
                    int z = x / 3 * 3 + y / 3;
                    if(board[x][y] == '.') {
                        for(int i = 1; i <= 9; ++i) {
                            int num = i - 1;
                            if(vis1[x][num] == false && vis2[y][num] == false && vis3[z][num] == false) {
                                char ch = (char)(i + '0');
                                board[x][y] = ch;
                                vis1[x][num] = true;
                                vis2[y][num] = true;
                                vis3[z][num] = true;
                                if(y == 8)
                                    backTracking(board, x + 1, 0);
                                else
                                    backTracking(board, x, y + 1);
                                if(isFound == true)
                                    break;
                                board[x][y] = '.';
                                vis1[x][num] = false;
                                vis2[y][num] = false;
                                vis3[z][num] = false;
                            }
                        }
                    } else {
                        int num = board[x][y] - '0' - 1;
                        vis1[x][num] = true;
                        vis2[y][num] = true;
                        vis3[z][num] = true;
                        if(y == 8)
                            backTracking(board, x + 1, 0);
                        else
                            backTracking(board, x, y + 1);
                    }
                }
                
                public void solveSudoku(char[][] board) {
                    vis1 = new boolean[9][9];
                    vis2 = new boolean[9][9];
                    vis3 = new boolean[9][9];
                    isFound = false;
                    for(int i = 0; i < 9; ++i) {
                        for(int j = 0; j < 9; ++j) {
                            if(board[i][j] != '.') {
                                int num = board[i][j] - '0' - 1;
                                int k = i / 3 * 3 + j / 3;
                                vis1[i][num] = true;
                                vis2[j][num] = true;
                                vis3[k][num] = true;
                            }
                        }
                    }
                    backTracking(board, 0, 0);
                }
            }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.