# Straight forward, clean c++ solution using backtracking

• There are plenty of good solutions out there. Mine might not as fancy as others, but should be clean and straightforward

``````void solveSudoku(vector<vector<char>>& board)
{
if(board.empty() || board[0].empty())
return;

int rows = board.size();
int cols = board[0].size();
int boxSize = 3;
solve(board, 0, 0, rows, cols, boxSize);
}

bool solve(vector<vector<char>>& board, int cy, int cx, int rows, int cols, int boxSize)
{
if(cy>=rows || cx>=cols)
return true;

// skipping the non empty cells
if(board[cy][cx] != '.')
{
if(cx == cols-1)
return solve(board, cy+1, 0, rows, cols, boxSize);
else
return solve(board, cy, cx+1, rows, cols, boxSize);
}

// trying different numbers
for(int i='1'; i<='9'; i++)
{
bool b = false;
char c = (char)i;
if(placeAt(board, cy, cx, c, rows, cols, boxSize))
{
board[cy][cx] = c;
if(cx == cols-1)
b = solve(board, cy+1, 0, rows, cols, boxSize);
else
b = solve(board, cy, cx+1, rows, cols, boxSize);
if(b)
return true;
board[cy][cx] = '.';
}
}
return false;
}

bool placeAt(vector<vector<char>>& board, int cy, int cx, char c, int rows, int cols, int boxSize)
{
// checking rows
for(int x=0; x<cols; x++)
{
if(board[cy][x] == c)
return false;
}

// checking columns
for(int y=0; y<rows; y++)
{
if(board[y][cx] == c)
return false;
}

// checking the box
int startY = cy / boxSize;
int startX = cx / boxSize;

for(int y= startY*boxSize; y<(startY+1)*boxSize; y++)
{
for(int x= startX*boxSize; x<(startX+1)*boxSize; x++)
{
if(board[y][x] == c)
return false;
}
}
return true;
}``````

``````vector<unsigned int> rMasks;    // for each col
vector<unsigned int> cMasks;    // for each row
vector<unsigned int> bMasks;    // for each boxes

void solveSudoku(vector<vector<char>>& board)
{
if(board.empty() || board[0].empty())
return;

int rows = board.size();
int cols = board[0].size();
int boxSize = 3;

for(int y=0; y<rows; y++)
{
for(int x=0; x<cols; x++)
{
char c = board[y][x];
if(c != '.')
{
int cnum = c-'0';
}
}
}

solve(board, 0, 0, rows, cols, boxSize);
}

bool solve(vector<vector<char>>& board, int cy, int cx, int rows, int cols, int boxSize)
{
if(cy>=rows || cx>=cols)
return true;

// skipping the non empty cells
if(board[cy][cx] != '.')
{
if(cx == cols-1)
return solve(board, cy+1, 0, rows, cols, boxSize);
else
return solve(board, cy, cx+1, rows, cols, boxSize);
}

// trying different numbers
for(int i='1'; i<='9'; i++)
{
bool b = false;
char c = (char)i;
int cnum = c-'0';
if(placeAt(board, cy, cx, c, rows, cols, boxSize))
{
board[cy][cx] = c;

if(cx == cols-1)
b = solve(board, cy+1, 0, rows, cols, boxSize);
else
b = solve(board, cy, cx+1, rows, cols, boxSize);
if(b)
return true;

board[cy][cx] = '.';
}
}
return false;
}

bool placeAt(vector<vector<char>>& board, int cy, int cx, char c, int rows, int cols, int boxSize)
{
int cnum = c-'0';

// checking rows
return false;

// checking cols
return false;

// checking the box
int idx = computeBMaskIndex(cy, cx, boxSize);
return false;

return true;
}

{
}

void setMaskBit(vector<unsigned int> & mask, int y, int x, int bs, int bit)
{
}

{
}

void clearMaskBit(vector<unsigned int> & mask, int y, int x, int bs, int bit)
{