Very simple solution accepted with 12ms in C, well-explained


  • 4

    Let's just hit the road!

    • move the pointer from left to right and the whole direction is from top-left to bottom-right;
    • check each cell while moving;
    • try each possible candidate from '1' to '9' while the checking cell is empty and if it's solvable from now on (recursive method) then just return it;
    • if all possible candidates failed, return false to indicate un-solvable in this condition which means indirectly that we should try another path - typical DFS solution using recursion.

    Bang! End of Story!

    • space complexity O(1) -> nothing need to be recorded here just using constant space;
    • time complexity O(9^k) but since we just are required to find only one viable solution, the cost will be dramatically reduced.

    bool check(char** board, int r, int c, char a) //check it in row, column and the sub three-dimension cube;
    {
        for(int i = 0; i < 9; i++) if(board[r][i]==a || board[i][c]==a) return false;
        int r0=r-r%3, c0=c-c%3; //get the start row and column of the sub cube;
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                if(board[r0+i][c0+j] == a) return false;
        return true;
    }
    bool solver(char** board, int r, int c) //check and try it from left to right and then downwards;
    {
        if(r == 9) return true; //now till the end and nothing wrong so far, so return true;
        if(c == 9) return solver(board, r+1, 0); //till the end of the current row and then downwards;
        if(board[r][c] != '.') return solver(board, r, c+1); //already taken just move to the next;
        for(char a = '1'; a <= '9'; a++) //try each possible candidate;
        {
            if(check(board, r, c, a)) //check its validity;
            {
                board[r][c] = a; //set it then and just move to the next;
                if(solver(board, r, c+1)) return true; //if it's solvable then just return true;
                board[r][c] = '.'; //restore it for easier checking in the next round;
            }
        }
        return false; //nothing works around then return false;
    }
    void solveSudoku(char** board, int rSize, int cSize)
    {
        solver(board, 0, 0); //start from the top-left position to the bottom right end;
    }

  • 2

    A more clean and efficient solution in C++.

    class Solution {
    private:
        bool search(vector<vector<char>>& board, int r, int c, bool rTakens[][9], bool cTakens[][9], bool subTakens[][9])
        {
            if(r == 9) return true;
            if(c == 9) return search(board, r+1, 0, rTakens, cTakens, subTakens);
            if(board[r][c] != '.') return search(board, r, c+1, rTakens, cTakens, subTakens);
            for(char a = '1'; a <= '9'; ++a)
            {
                int num = a -'0', k = r/3*3+c/3;
                if(!(rTakens[r][num] || cTakens[c][num] || subTakens[k][num]))
                {
                    rTakens[r][num] = cTakens[c][num] = subTakens[k][num] = true;
                    board[r][c] = a;
                    if(search(board, r, c+1, rTakens, cTakens, subTakens)) return true;
                    board[r][c] = '.';
                    rTakens[r][num] = cTakens[c][num] = subTakens[k][num] = false;
                }
            }
            return false;
        }
    public:
        void solveSudoku(vector<vector<char>>& board) {
            bool rTakens[9][9]{{false}}, cTakens[9][9]{{false}}, subTakens[9][9]{{false}};
            for(int r = 0; r < 9; ++r){
                for(int c = 0; c < 9; ++c){
                    if(board[r][c] != '.') {
                        int num = board[r][c] -'0', k = r/3*3+c/3;
                        rTakens[r][num] = cTakens[c][num] = subTakens[k][num] = true;
                    }
                }
            }
            search(board, 0, 0, rTakens, cTakens, subTakens);
        }
    };
    

Log in to reply
 

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