Bacetrack C++ sollution with bit ops AC in 36ms


  • 1
    H
    class Solution {public:
    unordered_map<int,int> int2bit;
    unordered_map<int,int> bit2int;
    bool solveSudoku(int n, vector<pair<int,int> >& blank, vector<vector<char> > &board, vector<int>&row, vector<int>&col, vector<int>&cell)     {
    	if(n==blank.size())
    	{
    		return true;
    	}
    	int i=blank[n].first;
    	int j=blank[n].second;
    	int idx=(i/3)*3+j/3;
    	int pos=row[i]&col[j]&cell[idx];
    	while(pos)
    	{
    	    int p=pos&(-pos);
    	    pos=pos-p;
    	    board[i][j]='0'+bit2int[p];
    	    row[i]&=~p;
    		col[j]&=~p;
    		cell[idx]&=~p;
    		if(solveSudoku(n+1,blank,board,row,col,cell))
    		{
    		    
    		    return true;
    		}
    		row[i]|=p;
    		col[j]|=p;
    		cell[idx]|=p;
    	}
    	return false;
    }
    void solveSudoku(vector<vector<char> > &board) {
        
        for(int k=1;k<=9;k++)
        {
            int2bit[k]=1<<(k-1);
            bit2int[1<<(k-1)]=k;
        }
        int limit=(1<<9)-1;
        vector<int> row(9,limit);
        vector<int> col(9,limit);
        vector<int> cell(9,limit);
        vector<pair<int,int> > blank;
    	for(int i=0;i<9;i++)
    	{
    		for(int j=0;j<9;j++)
    		{
    			if(board[i][j]!='.')
    			{
    				int k=int2bit[board[i][j]-'0'];
    				row[i]&=~k;
    				col[j]&=~k;
    				int idx=(i/3)*3+j/3;
    				cell[idx]&=~k;
    			}
    			else
    			{
    				blank.push_back(pair<int,int>(i,j));
    			}
    		}
    	}
    	solveSudoku(0,blank,board,row,col,cell);
    }};

Log in to reply
 

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