# A simple DFS solution

• class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
return true;
}
void solveSudoku(vector<vector<char> > &board) {
util(board, 0);
}
bool util(vector<vector<char>>& board, int pos)
{
if (pos >= 81)
return true;
int i = pos / 9;
int j = pos % 9;
if (board[i][j] != '.')
return util(board, pos + 1);
else
{
for (char c = '1'; c <= '9'; c++)
{
if (!isInRow(board, i,c) && !isInCol(board, j, c) && !isInRec(board, i, j, c))
{
board[i][j] = c;
if (util(board, pos + 1))
return true;
else
board[i][j] = '.';
}
}
return false;
}
}

bool isInRow(vector<vector<char>>& board, int i, char c)
{
vector<char>& row = board[i];
for (int k = 0; k < 9; k++)
{
if (row[k] == c)
return true;
}
return false;
}
bool isInCol(vector<vector<char>>& board,int j, char c)
{
for (int k = 0; k < 9; k++)
{
if (board[k][j] == c)
return true;
}
return false;
}
bool isInRec(vector<vector<char>>& board, int i, int j, char c)
{
int bigrow = i / 3, bigcol = j / 3;
for (int m = 3 * bigrow; m < 3 * (bigrow + 1); m++)
{
for (int n = 3 * bigcol; n < 3 * (bigcol + 1); n++)
if (board[m][n] == c)
return true;
}
return false;
}
};

• my solution use 3 hash table to save the filled numbers, this leads more efficiency

void solveSudoku(vector<vector<char> > &board) {
if (board.size() != 9 || board[0].size() != 9)
{
return;
}

int rowhash[9][9] = {{0}}, colhash[9][9] = {{0}}, blockhash[9][3][3] = {{{0}}};
for ( int i = 0; i < 9; i++)
{
for ( int j = 0; j < 9; j++)
{
if (board[i][j] != '.')
{
int num = board[i][j] - '1';
rowhash[num][i] = 1;
colhash[num][j] = 1;
blockhash[num][i/3][j/3] = 1;
}
}
}

solveSudoku_DFS(board, 0, rowhash, colhash, blockhash);
}
bool solveSudoku_DFS(vector<vector<char> > &board, int pos, int rowhash[9][9], int colhash[9][9], int blockhash[9][3][3])
{
if ( pos >= 81)
{
return true;
}
int i = pos / 9, j = pos % 9;

if (board[i][j] != '.')
{
return solveSudoku_DFS(board, pos+1, rowhash, colhash, blockhash);
}
else
{
for ( int num = 0; num < 9; num++)
{
if (rowhash[num][i] != 1 && colhash[num][j] != 1 && blockhash[num][i/3][j/3] != 1)
{
board[i][j] = '1' + num;
rowhash[num][i] = 1;
colhash[num][j] = 1;
blockhash[num][i/3][j/3] = 1;
if (solveSudoku_DFS(board, pos+1, rowhash, colhash, blockhash))
{
return true;
}
else
{
board[i][j] = '.';
rowhash[num][i] = 0;
colhash[num][j] = 0;
blockhash[num][i/3][j/3] = 0;
}
}
}

return false;
}
}

• I wish I could upvote your comment

• I can not find the votes button in editing page of my comment

• isn't the sudoku problem exactly the same as 8-queen, with just a different verification method ?

void solveSudoku(vector<vector<char>>& board) {
solve(board, 0);
}
bool solve(vector<vector<char>>& board, int ind){
if(ind==81) return true;
int i=ind/9, j=ind%9;
if(board[i][j]!='.') return solve(board, ind+1);
else{
for(char f = '1'; f <= '9'; f++)
{
if(isValidFill(board, i, j, f))
{
board[i][j]= f;
if(solve(board, ind+1)) return true;
board[i][j]='.';
}
}
return false;
}
}
bool isValidFill(vector<vector<char>>& board, int i, int j, char fill) {
for(int k=0; k<9; k++)
{
if(board[i][k]==fill) return false; //check the row
if(board[k][j]==fill) return false; //check the column
int r= i/3*3+j/3;   //select the block
if(board[r/3*3+k/3][r%3*3+k%3]==fill) return false; //check the block
}
return true;
}

• really smart.thanks for it.

• Following the same idea with hashtable, but using bit vector to save on space

class Solution {

vector<int> rowhash{vector<int>(9,0)};   // bit vector 000000000, each 1<<j represent whether index i+1 is already in row j
vector<int> colhash{vector<int>(9,0)};
vector<int> blockhash{vector<int>(9,0)};     // bit vector 000000000, each 1<<j represent whether index i+1 is already in superblock j
int sz = 9;
public:
void solveSudoku(vector<vector<char>>& board) {
if (board.size() != sz || board[0].size() != sz) return;

for (int i=0; i<sz; i++) {
for (int j=0; j<sz; j++) {
if (board[i][j] != '.') {
int num = board[i][j]-'1';
rowhash[num] |= (1<<i);
colhash[num] |= (1<<j);
int r = i/3*3+j/3;  // select the superblock that (i,j) reside
blockhash[num] |= (1<<r);
}
}
}

solveSudoku(board, 0);  // 9x9 board has 0->80 positions
}

// DFS solution, recurse all the way down, if false, then backtrack
bool solveSudoku(vector<vector<char>>& board, int pos) {
if (pos == 81) return true; // filled the entire board
int i = pos/9;
int j = pos%9;
int r = i/3*3+j/3;  // select the superblock that (i,j) reside

if (board[i][j] != '.') return solveSudoku(board, pos+1);

for (char c = '1'; c <= '9'; c++) {
int num = c-'1';
if (!(rowhash[num]&(1<<i)) && !(colhash[num]&(1<<j)) && !(blockhash[num]&(1<<r))) { // checks if board is valid
board[i][j] = c;
rowhash[num] |= (1<<i); // mark that num is in row i
colhash[num] |= (1<<j); // mark that num is in col j
blockhash[num] |= (1<<r);   // mark that num is in superblock r

if (solveSudoku(board,pos+1)) return true;  // DFS

board[i][j] = '.'; // backtrack
rowhash[num] &= ~(1<<i);
colhash[num] &= ~(1<<j);
blockhash[num] &= ~(1<<r);
}
}

return false;
}
};

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