C++ using back track, 4ms


  • 0
    S
    class Solution {
    public:
    int N = 81;
    void solveSudoku(vector<vector<char>>& board) {
        solve(board);
    }
    
    bool solve(vector<vector<char> >& sudo) {
        int board[N];							// board
        int spaces[N];							// space have to be fill
        int nspaces = 0;						// the num of space at begin
        int available[N];						// which num is available in one square
    
        // initial
        memset(board, 0, N * sizeof(int));
        memset(spaces, 0, N * sizeof(int));
        memset(available, 255, N * sizeof(int));
    
    
        for (int i = 0;i < N;++i)
        {
    	    if (sudo[i/9][i%9] == '.')
    	    {
    		    board[i] = 0;
    		    spaces[nspaces++] = i;
    	    }
    	    else
    	    {
    		    board[i] = sudo[i/9][i%9] - '0';
    	    }
        }
        // find the answer
        if (nspaces == 0)
    	    return true;
    	int node = 0, min = 9; // node: which square's possible choices is least, min is the num of choices
    	// artites: every square's possilbe choices, init 9, neighbors: every square which neigbhor has been fill
        for (int i = 0, neighbors = 0, artites = 9;i < N;++i, neighbors = 0, artites = 9)
        {
    	    if (board[i] == 0)
    	    {
    		    // at the same row
    		    for (int j = i/9*9;j < (i/9 + 1)*9;++j)
    		    {
    			    if (board[j] && !(neighbors >> board[j] & 1))
    			    {
    				    neighbors |= 1 << board[j];
    				    --artites;
    				    available[i] &= ~(1 << board[j]);
    			    }
    		    }
    		    // at the same column
    		    for (int j = i%9;j < N;j += 9)
    		    {
    			    if (board[j] && !(neighbors >> board[j] & 1))
    			    {
    				    neighbors |= 1 << board[j];
    				    --artites;
    				    available[i] &= ~(1 << board[j]);
    			    }
    		    }
    		    // at the same 3*3 square
    		    for (int j = 0, m = i/27*27 + i%9/3*3;j < 3;++j)
    		    {
    			    for (int n = 0;n < 3;++n)
    			    {
    				    if (board[j*9 + m + n] && !(neighbors >> board[j*9 + m + n] & 1))
    				    {
    					    neighbors |= 1 << board[j*9 + m + n];
    					    --artites;
    					    available[i] &= ~(1 << board[j*9 + m + n]);
    				    }
    			    }
    		    }
    		    if (artites < min)
    		    {
    			    min = artites;
    			    node = i;
    		    }
    	    }
        }
        // illegal
        if (min == 0)
    		return false;
        // select every possible choice fill in the square
        for (int i = 1;i < 10;++i)
        {
    	    if ((available[node] >> i) & 1)
    	    {
    		    sudo[node/9][node%9] = i + '0';
    		    if (solve(sudo))
    			    return true;
    			else
    			    sudo[node/9][node%9] = '.';
    	    }
        }
        return false;
    }
    

    };


Log in to reply
 

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