Why is my JAVA solution always can't reach the last line?


  • 0
    L

    I use hash table to keep track of the numbers we have used in each row, each col, each 3*3 square
    And every time I see a '.', I enter the next recursion

    But I always fail at the last row, seems like my program don't even enter last row, the output is :

    Input: ["..9748...","7........",".2.1.9...","..7...24.",".64.1.59.",".98...3..","...8.3.2.","........6","...2759.."]

    Output: ["519748632","783652419","426139875","357986241","264317598","198524367","975863124","832491756","...2759.3"]

    Expected: ["519748632","783652419","426139875","357986241","264317598","198524367","975863124","832491756","641275983"]

    Can you guys help to see what is the problem of my code?
    Thanks a lot!

    My code is:

    public class Solution {

    public void solveSudoku(char[][] board) {
        HashSet<Integer>[] rows = new HashSet[9];
        for(int i=0; i<9; i++) rows[i] = new HashSet<Integer>();
        
        HashSet<Integer>[] cols = new HashSet[9];
        for(int i=0; i<9; i++) cols[i] = new HashSet<Integer>();
        
        HashSet<Integer>[] squares = new HashSet[9];
        for(int i=0; i<9; i++) squares[i] = new HashSet<Integer>();
        
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++){
                if(Character.isDigit(board[i][j])){
                    rows[i].add(board[i][j]-'0');
                    cols[j].add(board[i][j]-'0');
                    squares[(i/3)*3+(j/3)].add(board[i][j] - '0');
                }
            }
        }
        
        helper(board,rows, cols, squares, 0, 0);
        
    }
    
    public boolean helper(char[][] board, HashSet<Integer>[] rows, HashSet<Integer>[] cols, HashSet<Integer>[] squares, int row, int col){
        if(row >= 9) return true;
        for(int i=row; i<9; i++){
            for(int j=col; j<9; j++){
                if(Character.isDigit(board[i][j])){
                    continue;
                }
                else{
                    for(int k=1; k<=9; k++){
                        if(rows[i].contains(k) || cols[j].contains(k) || squares[(i/3)*3+(j/3)].contains(k)) continue;
                        else{
                            rows[i].add(k);
                            cols[j].add(k);
                            squares[(i/3)*3+(j/3)].add(k);
                            board[i][j] = (char)('0'+k);
                            int nextrow;
                            int nextcol;
                            if(j>=8){
                                nextrow = i+1;
                                nextcol = 0;
                            }
                            else{
                                nextrow = i;
                                nextcol = j+1;
                            }
                            if(helper(board, rows, cols, squares, nextrow, nextcol)) return true;
                            rows[i].remove(k);
                            cols[j].remove(k);
                            squares[(i/3)*3+(j/3)].remove(k);
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    

    }


Log in to reply
 

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