share my 4ms, 20 lines simple cpp using DFS


  • 1
    Z
    void solveSudoku(vector<vector<char>>& board) {
            int box[10][10]={0},row[10][10]={0},col[10][10]={0};
            for(int i=0;i<9;i++)
                for(int  j=0;j<9;j++)
                    if(board[i][j]!='.')
                        row[i][board[i][j]-'0']=col[j][board[i][j]-'0']=box[i/3*3+j/3][board[i][j]-'0']=1;
            dfs(0,box,row,col,board);
        }
        bool dfs(int pos,int box[][10],int row[][10],int col[][10],vector<vector<char>> &board){
            if(pos==81)return true;
            int x=pos/9,y=pos%9;
            if(board[x][y]!='.')return dfs(pos+1,box,row,col,board);
            for(int i=1;i<=9;i++)
                if(!row[x][i]&&!col[y][i]&&!box[x/3*3+y/3][i]){
                    row[x][i]=col[y][i]=box[x/3*3+y/3][i]=1;
                    board[x][y]='0'+i;
                    if(dfs(pos+1,box,row,col,board))return true;
                    row[x][i]=col[y][i]=box[x/3*3+y/3][i]=0;
                    board[x][y]='.';
                }
            return false;
        }
    

Log in to reply
 

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