three flavors are provided.
//first flavor
class Solution {
public:
typedef vector<vector<char> > BOARDTYPE;
void solveSudoku(BOARDTYPE &board) {
solveSudokuRe(board, 0, 0);
}
bool solveSudokuRe(BOARDTYPE &board, int row, int col) {
if(col>=9)
return solveSudokuRe(board,row+1,0);
if(row==9)
return true;
if(board[row][col]=='.'){
for(int i=0;i<9;i++){
board[row][col]='1'+i;
if(isValid(board,row,col))
if(solveSudokuRe(board,row,col+1))
return true;
board[row][col]='.';
}
}
else{
return solveSudokuRe(board,row,col+1);
}
return false;
}
bool isValid(BOARDTYPE &board, int row, int col){
for(int k=0;k<9;k++){
if((k!=row&&board[k][col]==board[row][col])||(k!=col&&board[row][k]==board[row][col]))
return false;
}
for(int i=row/3*3;i<row/3*3+3;i++)
for(int j=col/3*3;j<col/3*3+3;j++)
if(!(i==row&&j==col)&&board[i][j]==board[row][col])
return false;
return true;
}
//another flavor of isValid function
bool isValid2(BOARDTYPE &board, int row, int col){
for(int k=0;k<9;k++){
if((k!=row&&board[k][col]==board[row][col])||(k!=col&&board[row][k]==board[row][col]))
return false;
}
for(int k=0;k<9;k++){
int i=row/3*3+k/3;
int j=col/3*3+k%3;
if(!(i==row&&j==col)&&board[i][j]==board[row][col])
return false;
}
return true;
}
};
//second flavor
class Solution {
public:
typedef vector<vector<char> > BOARDTYPE;
void solveSudoku(BOARDTYPE &board) {
solveSudokuRe(board, 0, 0);
}
bool solveSudokuRe(BOARDTYPE &board, int row, int col) {
getNextEmpty(board, row, col);
if (row == 9) return true;
vector<bool> avail(9, true);
getAvailable(board, avail, row, col);
for (int i = 0; i < 9; ++i)
{
if (!avail[i]) continue;
board[row][col] = i + '1';
if (solveSudokuRe(board, row, col)) return true;
}
board[row][col] = '.';
return false;
}
void getNextEmpty(BOARDTYPE &board, int &row, int &col) {
do {
if (board[row][col] == '.') return;
row = (col == 8) ? row + 1 : row;
col = (col + 1) % 9;
} while (row < 9);
}
void getAvailable(BOARDTYPE &board, vector<bool> &avail, int row, int col) {
for (int i = 0; i < 9; ++i) {
if (board[row][i] != '.') avail[board[row][i]-'1'] = false;
if (board[i][col] != '.') avail[board[i][col]-'1'] = false;
int box_i = row/3*3 + i/3, box_j = col/3*3 + i%3;
if (board[box_i][box_j] != '.') avail[board[box_i][box_j]-'1'] = false;
}
}
};
//third one, a little slower than the two above.
class Solution {
public:
bool isValid(vector<vector<char> > &board, int x, int y)
{
int i, j;
for (i = 0; i < 9; i++)
if (i != x && board[i][y] == board[x][y])
return false;
for (j = 0; j < 9; j++)
if (j != y && board[x][j] == board[x][y])
return false;
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;
}
bool solveSudoku(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 = 1; k <= 9; ++k)
{
board[i][j] = '0' + k;
if (isValid(board, i, j) && solveSudoku(board))
return true;
board[i][j] = '.';
}
return false;
}
}
return true;
}
};
No comments:
Post a Comment