Simple yet still accepted as best C++, but there is still a problem confusing me


  • 0

    The exact question is posted at stackoverflow.

    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; //level checking;
            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) //try different cases;
            {
                int num = a -'0', k = r/3*3+c/3;
                if(!(rTakens[r][num] || cTakens[c][num] || subTakens[k][num])) //filter out the invalid;
                {
                    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] = '.'; //restore to its original state;
                    rTakens[r][num] = cTakens[c][num] = subTakens[k][num] = false;
                }
            }
            return false;
        }
    public:
        //AC - 4ms - best submission;
        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) //initialize the takens;
                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); //time to search and fill up the board;
        }
    };

  • 1
    B

    I don't quite understand your solution, but I guess if you don't reset the point to '.', at the end of loop it will remain as '9', if '1' to '9' all fail? Backtracking is usually used when you pass arguments as references into a function. If you pass as copy, usually that is no necessary

    my 2 cents


  • 0

    The problem description specifically points it out that there will be a unique solution, so the case (all candidates failed) won't happen, and if the previous candidate failed it also will be replaced by the followers which will not affect the final result. Anyway thanks for your sharing.


  • 0

    @LHearen Why do you think not all candidates for a cell can fail? Isn't that what happens most of the time? Let's say the first cell needs to be 2. You try 1 first, and while you're doing that, everything you try on the remaining cells will fail.


  • 0

    Thank you so much, man. You nailed the point here! Thank you!


  • 0
    D
    class Solution {
    public:
        void solveSudoku ( vector<vector<char>>& board )
        {
            // initialize
            print(board); 
            vector<set<int>> solver;
            vector<pair<int, int>> solved;
            set<int> unsolved;
            set<int> si {1,2,3,4,5,6,7,8,9};
            for ( unsigned i=0; i<9; i++ )
                for ( unsigned j=0; j<9; j++ )
                {
                    if ( board[i][j]=='.' ) 
                    {
                        solver.push_back(si);
                        unsolved.insert(i*9+j);
                    }
                    else 
                    {
                        solver.push_back({board[i][j]});
                        solved.push_back({i*9+j, board[i][j]});
                    } 
                }
    
            for ( int i=0; i<solved.size(); i++ ) 
            {
                eraseDuplicate( solved[i].second, solver, solved[i].first, solved, unsolved );
                board[solved[i].first/9][solved[i].first%9] = solved[i].second;
            }
    

    // print( board );

            // Recursively find a solution
            if ( judgeAndSeek( solver, unsolved, board ) )
                print( board );
            
        }
            
    private:
        bool judgeAndSeek( vector<set<int>> solver, set<int> unsolved, vector<vector<char>>& board )
        {
            if ( unsolved.empty() ) return true;
            for ( auto x=solver[*unsolved.begin()].begin(); x!=solver[*unsolved.begin()].end(); x++ )
            {
                vector<set<int>> solver2 {solver};
                set<int> unsolved2 {unsolved};
                int p {*unsolved2.begin()};
                unsolved2.erase(p);
    
                solver2[p].clear();
                solver2[p].insert(*x);
                vector<pair<int, int>> solved2 {{p, *x}};
    
                //cout << unsolved2.size() << endl;
                
                int j {0};
                while ( j<solved2.size() && 
                    eraseDuplicate( solved2[j].second, solver2, solved2[j].first, solved2, unsolved2 ) )
                    ++j;
    
                if ( j==solved2.size() && judgeAndSeek(solver2, unsolved2, board) )
                {
                    for ( int i=0; i!=solved2.size(); i++ )
                        board[solved2[i].first/9][solved2[i].first%9] = solved2[i].second;
                    return true;
                }
            }
            return false;
        }
    
    
        bool eraseDuplicate( const int v, vector<set<int>>& solver, const int p, vector<pair<int, int>>& solved, set<int>& unsolved )
        {
            //cout << "here: " << v << " " << p << endl;
            for ( int k=0; k<9; ++k ) {
                if (k!=p%9) solver[p/9*9+k].erase(v);
                if (k!=p/9 ) solver[p%9+k*9].erase(v);
                if ( solver[p/9*9+k].empty() || solver[p%9+k*9].empty() )
                    return false;
    
                if ( solver[p/9*9+k].size()==1 && unsolved.find(p/9*9+k)!=unsolved.end() ) {
                    unsolved.erase(p/9*9+k);
                    solved.push_back({p/9*9+k, *solver[p/9*9+k].begin()});
                }
                if ( solver[p%9+k*9].size()==1 && unsolved.find(p%9+k*9)!=unsolved.end() ) {
                    unsolved.erase(p%9+k*9);
                    solved.push_back({p%9+k*9, *solver[p%9+k*9].begin()});
                }
            }
            for ( int i=1; i<3; i++ )
                for ( int j=1; j<3; j++ ) {
                    int ij = (p/9/3*3+(p/9+i)%3)*9 + p%9/3*3+(p%9+j)%3;
                    solver[ij].erase(v);
                    if ( solver[ij].empty() ) return false;
    
                    if ( solver[ij].size()==1 && unsolved.find(ij)!=unsolved.end() ) {
                        unsolved.erase(ij);
                        solved.push_back({ij, *solver[ij].begin()});
                    }
                }
            return true;
        }
    
        void print( const vector<vector<char>>& board )
        {
            for ( const auto & x : board )
            {
                for ( auto y : x )
                    if ( y!='.' ) cout << int(y);
                    else cout << ' ';
                cout << endl;
            }
        }
    
        void printS( const vector<set<int>>& solver )
        {
            for ( const auto & x : solver )
            {
                for ( auto y : x )
                    cout << y;
                cout << endl;
            }
        }
    
        bool checkUnique( const int& i, vector<int>& solved, vector<set<int>>& solver, vector<vector<char>>& board ) 
        {
    
            for ( auto x : solver[i] ) {
                // check row
                int jr {0};
                for ( int k=0; k<9; k++ ) if ( solver[i/9*9+k].find(x)!=solver[i/9*9+k].end() ) ++jr;
                if ( jr==1 ) 
                {
                    solver[i].clear();
                    solver[i].insert(x);
                    board[i/9][i%9] = x;
                    solved.push_back(i);
                    return true;
                }
                // check column
                int jc {0};
                for ( int k=0; k<9; k++ ) if ( solver[i%9+k*9].find(x)!=solver[i%9+k*9].end() ) ++jc;
                if ( jc==1 ) 
                {
                    solver[i].clear();
                    solver[i].insert(x);
                    board[i/9][i%9] = x;
                    solved.push_back(i);
                    return true;
                }
                // check subcube
                int js {0};
                for ( int k=0; k<3; k++ ) 
                    for ( int l=0; l<3; l++ ) 
                    {
                        int kl = (i/9/3*3+k)*9 + i%9/3*3+l;
                        if ( solver[kl].find(x)!=solver[kl].end() ) ++js;
                    }
                if ( js==1 ) 
                {
                    solver[i].clear();
                    solver[i].insert(x);
                    board[i/9][i%9] = x;
                    solved.push_back(i);
                    return true;
                }
                cout << "i=" << i << ", x=" << x << jr << jc << js << endl;
            }
            return false;
        }
    

    }; code here


  • 0
    D

    Hi, my solution is similar with yours. However, the online judge can’t output the number in “board” directly, unless add ‘(int)’ to every element in “board”. Could anyone tell how to make the cast? Thank you!


  • 0
    D

    Well, i found why, it's about the ascii value. Add "+ '0'" when assign element of "board". :-p


Log in to reply
 

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