# Yet another 0ms C++ solution

• This is an extension of my previous 2ms solution posted earlier.

It is much faster than pure DFS/Backtracking, since it primarily relies on reactive constraint propagation and uses backtracking only as a fallback. This aspect of the algorithm remains unchanged. See the link above for more detailed description.

The new version posted here, uses the same algorithm, but optimized with the help of moderately-crazy bithacks and modulo-n arithmetic tricks to speedup some things.

``````class Solution {
// Table which allows compute the value of the cell
// uses the fact that (1<<i)%11 is unique for i = [0..8] and never produces 0
struct SudokuSolver {
// Using mask for each cell which constraints values which can be in the cell
// Yeap, it is more storage, comparing to rows/cols/sqrs approach
// but it allows to do super-fast reactive constraint propagation
array<array<uint16_t,9>,9> board;
SudokuSolver()
{
// Initializing the board with mask, which permits all numbers
for (int i=0; i<9; i++)
for (int j=0; j<9; j++)
board[i][j] = 0x1ff;
}

// adds value v [1..9] to the board, return false if it violates constraints
bool add(int i, int j, int v)
{
return set(i, j, 1<<(v-1));
}

// set a value mask to the cell (i,j) and reactively updates constraints
bool set(int i, int j, uint16_t mask)
{
int16_t prev = board[i][j];
if (prev == mask) return true;
}

// propagates constraints as a result of setting i,j to mask
bool propagate(int i, int j, uint16_t mask)
{
for (int k=0; k<9; k++) {
int ii = (i/3)*3 + (k/3);
int jj = (j/3)*3 + (k%3);
if ((i != ii || j != jj) && !addConstraint(ii, jj, mask)) return false;
}
return true;
}

// prohibits putting value in mask to the cell (i,j)
{
if (newMask == 0) return false;
// good news - we have only one possibility for the cell (i,j)
}
}
return true;
}

// list of cell coordinates with >1 possibilities for values
vector<pair<int,int>> v;
void solve()
{
// finding all ambiguous cells
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
}
}
// note: it is also a good idea to sort v by the hamming weight, but
// without sorting it is still super-fast
// running backtracking as is
backtrack(0);
}

// backtracking
bool backtrack(int k) {
if (k == v.size()) return true;
int i = v[k].first;
int j = v[k].second;
// the board state is so compact and backtracking depth is so shallow, so
// it is cheaper to make a snapshot of the state vs. doing classical
// undo at each move
auto snapshot = board;
for (uint16_t cand = 1; cand<=0x1ff; cand = cand <<1) {
if (set(i, j, cand) && backtrack(k+1)) return true;
board = snapshot;
}
return false;
}
else {
return backtrack(k + 1);
}
}

};

public:
void solveSudoku(vector<vector<char>>& board) {
SudokuSolver solver;
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
char c = board[i][j];
if (c != '.' && !solver.add(i,j,c-'0')) return;
}
}
// At this point 9 of 10 sudokus published in magazines will be solved by constraint propagation
// only 'hard' sudokus will require some (limited) backtracking
solver.solve();
for (int i=0; i<9; i++)
for (int j=0; j<9; j++)