# C++ template for Valid Sudoku & Sudoku Solver

• Problem 36 ---- Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

``````class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
bool c1[9][9]={false}, c2[9][9]={false}, c3[9][9]={false};
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
if(board[i][j]!='.'){
int temp=board[i][j]-'1';
int index=(i/3)*3+j/3;
if(c1[i][temp] || c2[j][temp] || c3[index][temp])  return false;
c1[i][temp]=c2[j][temp]=c3[index][temp]=true;
}
}
}
return true;
}
};
``````

We can use bitmap to record the existing information like this to save memory ...

``````   bool isValidSudoku(vector<vector<char>>& board) {
vector<short> col(9, 0);
vector<short> block(9, 0);
vector<short> row(9, 0);
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int idx = 1 << (board[i][j] - '0');
if (row[i] & idx || col[j] & idx || block[i/3 * 3 + j / 3] & idx)
return false;
row[i] |= idx;
col[j] |= idx;
block[i/3 * 3 + j/3] |= idx;
}
}
return true;
}
``````

37 ---- Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character '.'. You may assume that there will be only one unique solution.

``````class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {
solve(board);
return;
}

bool solve(vector<vector<char>>& board) {
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
if(board[i][j]=='.'){
for(int k=0; k<9; k++){
board[i][j]='1'+k;
/*** check all the position util return true ***/
if(isValid(board, i, j)){
if(solve(board))    return true;
}
board[i][j]='.';
}
/*** can not find solution for the first '.' position ***/
return false;
}
}
}
return true;
}

bool isValid(const vector<vector<char>> &board, int x, int y){
int i, j;
/*** check column y ***/
for(i=0; i<9; i++){
if(i!=x && board[i][y]==board[x][y])  return false;
}
/*** check row x ***/
for(j=0; j<9; j++){
if(j!=y && board[x][j]==board[x][y])  return false;
}
/*** check the cute ***/
for(i=3*(x/3); i<3*(x/3+1); i++){
for(j=3*(y/3); j<3*(y/3+1); j++){
if((i!=x || j!=y) && board[i][j]==board[x][y])
return false;
}
}
return true;
}
};
``````

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