My c++ solution with massive bit operations


  • 0
    L

    '__builtin_ffs' is compiler intrinsic to find the first '1' bit of the input integer

    class Solution
    {
    public:
    	void solveSudoku( vector<vector<char> > &board )
    	{
        	struct { short o; short v; } b[81] = { 0 };
        
        	short r[9], c[9], s[9];
        	for( int i = 0; i < 9; ++i )
        		r[i] = c[i] = s[i] = 0x01ff;
        
            // get valid digits for each row, column and square
        	for( int i = 0; i < 81; ++i )
        	{
        		int x = i % 9, y = i / 9;
        		int z = x / 3 * 3 + y / 3;
        		short a = board[y][x];
        		if( a != '.' )
        		{
        			b[i].o = -1;
        			a = ~(1 << (a - '1'));
        			r[y] &= a, c[x] &= a, s[z] &= a;
        		}
        	}
        
            // get valid digits for each cell
        	for( int i = 0; i < 81; ++i )
        	{
        		if( b[i].o != -1 )
        		{
        			int x = i % 9, y = i / 9;
        			int z = x / 3 * 3 + y / 3;
        			b[i].o = b[i].v = r[y] & c[x] & s[z];
        		}
        	}
        
            // search possible solutions
        	for( int i = 0; i < 81; ++i )
        	{
        		if( b[i].o == -1 )
        			continue;
        
        		int x = i % 9, y = i / 9;
        		int z = x / 3 * 3 + y / 3;
        		int v = b[i].v & r[y] & c[x] & s[z];
        		if( v == 0 ) // failed? go backward
        		{
        			for( --i; i >= 0; --i )
        			{
        				if( b[i].o == -1 )
        					continue;
        				x = i % 9, y = i / 9;
        				z = x / 3 * 3 + y / 3;
        				short a = (short)(1 << (__builtin_ffs( b[i].v ) - 1));
        				r[y] |= a, c[x] |= a, s[z] |= a;
        				if( (v = b[i].v & ~a) != 0 )
        					break;
        				b[i].v = b[i].o;
        			}
        		}
        
        		b[i].v = v;
        		short a = ~(short)(1 << (__builtin_ffs( b[i].v ) - 1));
        		r[y] &= a, c[x] &= a, s[z] &= a;
        	}
        
            // fill the solution back
        	for( int i = 0; i < 81; ++i )
        	{
        		if( b[i].o != -1 )
        		{
        			int x = i % 9, y = i / 9;
        			board[y][x] = __builtin_ffs( b[i].v ) - 1 + '1';
        		}
        	}
    	}
    };

Log in to reply
 

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