# My c++ solution with massive bit operations

• '__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';
}
}
}
};``````

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