Is calculate each line & column & square runs FASTER than using HashSet?


  • 0
    B

    I wrote two codes to sovle this problem.

    • The first way is using 27 Sets to save the available digits of
      each line, each column and each square. 420ms used.
    • The second way is using only ONE set to save the available
      digits of the current line that we are traversing now, and calculate the column and the square. 340ms used.

    I thought the first way should runs faster than the second way, but the result shows that the second way runs faster.

    Here are the codes.

    First one: 420ms

    public void solveSudoku(char[][] board) {
        init(board);
        fill(board,0,0);
    }
    private HashSet<Character> V[]=new HashSet[9];
    private HashSet<Character> H[]=new HashSet[9];
    private HashSet<Character> S[]=new HashSet[9];
    private boolean fill(char[][] board,int line,int column) {
        if (line==9){
            return true;
        }
        if (board[line][column]!='.'){
            return fill(board,line+(column+1)/9,(column+1)%9);
        }
        HashSet<Character> availableSet=findAvailable(line,column);
        for (char c:availableSet){
            board[line][column]=c;
            V[line].remove(c);
            H[column].remove(c);
            S[(line/3)*3+column/3].remove(c);
            if (fill(board,line+(column+1)/9,(column+1)%9)){
                return true;
            }
            V[line].add(c);
            H[column].add(c);
            S[(line/3)*3+column/3].add(c);
            board[line][column]='.';
        }
        return false;
    }
    private HashSet<Character> findAvailable(int line,int column){
        HashSet<Character> availableSet=new HashSet<Character>();
        for (char c:V[line]){
            availableSet.add(c);
        }
        availableSet.retainAll(H[column]);
        availableSet.retainAll(S[(line/3)*3+column/3]);
        return availableSet;
    }
    private void init(char[][] board){
        for (int i=0;i<9;i++){
            V[i]=new HashSet<Character>(){{add('1');add('2');add('3');add('4');add('5');add('6');add('7');add('8');add('9');}};
            H[i]=new HashSet<Character>(){{add('1');add('2');add('3');add('4');add('5');add('6');add('7');add('8');add('9');}};
            S[i]=new HashSet<Character>(){{add('1');add('2');add('3');add('4');add('5');add('6');add('7');add('8');add('9');}};
        }
        for (int i=0;i<9;i++){
            for (int j=0;j<9;j++){
                V[i].remove(board[i][j]);
                H[j].remove(board[i][j]);
                S[(i/3)*3+(j/3)].remove(board[i][j]);
            }
        }
    }
    

    Second one: 340ms

    public class Solution {
        public void solveSudoku(char[][] board) {
            fill(board,0,0,new HashSet<Character>());
        }
        private boolean fill(char[][] board,int line,int column,HashSet<Character> availableDigit){
            if (line==9)
                return true;
            if (column==0){
                availableDigit=new HashSet<Character>(){{add('1');add('2');add('3');add('4');add('5');add('6');add('7');add('8');add('9');}};
                for (int iterator=0;iterator<9;iterator++){
                    if (board[line][iterator]!='.'){
                        availableDigit.remove(board[line][iterator]);
                    }
                }
            }
            if (board[line][column]!='.'){
                //availableDigit.remove(board[line][column]);
                boolean filled=fill(board,line+(column+1)/9,(column+1)%9,availableDigit);
                if (filled){
                    return true;
                }
                else return false;
            }
            HashSet<Character> newDigits=realAvailable(availableDigit,board,line,column);
            for (char c:newDigits){
                board[line][column]=c;
                availableDigit.remove(c);
                boolean filled=fill(board,line+(column+1)/9,(column+1)%9,availableDigit);
                if (filled){
                    return true;
                }
                availableDigit.add(c);
                board[line][column]='.';
            }
            return false;
        }
        private HashSet<Character> realAvailable(HashSet<Character> available,char[][] board,int line,int column){
            HashSet<Character> newDigits=new HashSet<Character>();
            for (char c:available){
                newDigits.add(c);
            }
            for (int i=0;i<9;i++){
                newDigits.remove(board[i][column]);
            }
            int dockLine=(line/3)*3;
            int dockColumn=(column/3)*3;
            for (int i=dockLine;i<dockLine+3;i++){
                for (int j=dockColumn;j<dockColumn+3;j++){
                    if (board[i][j]!='.'){
                        newDigits.remove(board[i][j]);
                    }
                }
            }
            return newDigits;
        }
    }

Log in to reply
 

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