C++ Non-recursive solution, start from cell with least ambiguity


  • 0
    A

    Not a fan of recusive function as stack space is also space. In fact, I've never used recursive function in any leetcode solutions.
    We can more aggressively prune the search space while building the bitmap in the first loop, but considering each search only takes at most 1 SHIFT + 3 AND + 2 OR operations, I just didn't deem it worthy.

    class Solution {
    public:
        struct ans {
            uint w;
            uint i;
            uint j;
            int v;
            friend bool operator < (ans& a1, ans& a2) {return a1.w > a2.w;}
        };
        void solveSudoku(vector<vector<char>>& board) {
            int n, k;
            uint h[9]={0}, v[9]={0}, x[9]={0};
            vector<ans> a;
            for (uint i=0; i<9; i++) {
                for (uint j=0; j<9; j++) {
                    char c = board[i][j] - '0';
                    if (c == '.' - '0') {
                        a.push_back({0, i, j, 0});
                        continue;
                    }
                    h[i] |= 1<<c;
                    h[i] += 0x10000;
                    v[j] |= 1<<c;
                    v[j] += 0x10000;
                    uint y = i/3*3+j/3;
                    x[y] |= 1<<c;
                    x[y] += 0x10000;
                }
            }
            for (n=a.size(), k=0; k<n; k++) {
                a[k].w = h[a[k].i]>>16 + v[a[k].j]>>16 + x[a[k].i/3*3+a[k].j/3]>>16;
            }
            sort(a.begin(), a.end());
            for (k=0; k<n; k++) {
                uint i = a[k].i, j = a[k].j, y = i/3*3+j/3;
                char c = a[k].v;
                if (c < 0) {
                    c = -c;
                    h[i] ^= 1<<c;
                    v[j] ^= 1<<c;
                    x[y] ^= 1<<c;
                }
                while (++c <= 9 && ((1<<c)&h[i] || (1<<c)&v[j] || (1<<c)&x[y]));
                if (c <= 9) {
                    a[k].v = c;
                    h[i] |= 1<<c;
                    v[j] |= 1<<c;
                    x[y] |= 1<<c;               
                } else {
                    a[k].v = 0;
                    a[--k].v *= -1;
                    k--;
                }
            }
            for (k=0; k<n; k++) board[a[k].i][a[k].j] = a[k].v + '0';
        }
    };
    

Log in to reply
 

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