Use half hour to solve this problem, 8ms beat 94%, 50 line codes


  • 0
    F
      boolean[][] rowVisited = new boolean[9][9];
        boolean[][] colVisited = new boolean[9][9];
        boolean[][] crossVisited = new boolean[9][9];
        public void solveSudoku(char[][] board) {
            if (board == null || board.length != 9 || board[0].length != 9) return;
            // define three hashtable, row visited, col visited, subBox visited
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    int index = board[i][j]-'0';
                    if (index >= 1 && index <= 9) {
                        rowVisited[i][index-1] = true;
                        colVisited[index-1][j] = true;
                        int crossNumber = (i/3)*3 + j/3;
                        crossVisited[crossNumber][index-1] = true;
                    }
                }
            }
            
            Dfs(board, 0);
        }
        
        private boolean Dfs(char[][] board, int length) {
            if (length == 81) return true;
            int row = length/9;
            int col = length%9;
            if (board[row][col] >= '1' && board[row][col] <= '9') return Dfs(board, length+1);
            
            for (int number = 1; number <= 9; number++) {
                // row validate
                if (rowVisited[row][number-1]) continue;
                // col validate
                if (colVisited[number-1][col]) continue;
                // cross validate
                int crossNumber = (row/3)*3 + col/3; 
                if (crossVisited[crossNumber][number-1]) continue;
                
                board[row][col] = (char)(number+'0');
                rowVisited[row][number-1] = true;
                colVisited[number-1][col] = true;
                crossVisited[crossNumber][number-1] = true;
                
                boolean res = Dfs(board, length+1);
                if (res) return true;
                board[row][col] = '.';
                rowVisited[row][number-1] = false;
                colVisited[number-1][col] = false;
                crossVisited[crossNumber][number-1] = false;
            }
            
            return false;
        }

Log in to reply
 

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