Valid Sudoku
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
A partially filled sudoku which is valid.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
暴力解法，一行一行的看，一列一列的看，一个一个方格的看，
代码如下：
class Solution {
public:
bool isValidCell(vector<vector<char> > &board, int a, int b) {
vector<bool> flag(, false);
int idx;
for (int i = ; i < ; ++i) {
for (int j = ; j < ; ++j) {
idx = board[a + i][b + j] - '';
if (idx > && idx <= && !flag[idx])
flag[idx] = true;
else if (idx > && idx <= && flag[idx])
return false;
}
}
return true;
}
bool isValidRow(vector<vector<char> > &board, int a) {
vector<bool> flag(, false);
int idx;
for (int j = ; j < ; ++j) {
idx = board[a][j] - '';
if (idx > && idx <= && !flag[idx])
flag[idx] = true;
else if (idx > && idx <= && flag[idx])
return false;
}
return true;
}
bool isValidCol(vector<vector<char> > &board, int b) {
vector<bool> flag(, false);
int idx;
for (int i = ; i < ; ++i) {
idx = board[i][b] - '';
if (idx > && idx <= && !flag[idx])
flag[idx] = true;
else if (idx > && idx <= && flag[idx])
return false;
}
return true;
}
bool isValidSudoku(vector<vector<char> > &board) {
for (int i = ; i < ; ++i) {
for (int j = ; j < ; ++j) {
if (!isValidCell(board, * i, * j))
return false;
}
}
for (int i = ; i < ; ++i) {
if (!isValidRow(board, i))
return false;
}
for (int j = ; j < ; ++j) {
if (!isValidCol(board, j))
return false;
}
return true;
}
};
一种简介的解法(还没认真看，可能牵扯到一些数学)：
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
vector<vector<bool>> rows(, vector<bool>(,false));
vector<vector<bool>> cols(, vector<bool>(,false));
vector<vector<bool>> blocks(, vector<bool>(,false));
for(int i = ; i < ; i++)
for(int j = ; j < ; j++)
{
if(board[i][j] == '.')continue;
int num = board[i][j] - '';
if(rows[i][num] || cols[j][num] || blocks[i - i% + j/][num])
return false;
rows[i][num] = cols[j][num] = blocks[i - i% + j/][num] = true;
}
return true;
}
};
Sudoku Solver
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.
A sudoku puzzle...
...and its solution numbers marked in red.
很多题乍一看很难，是因为思路不清晰，只要思路清晰了，还是很简单的。
思路:
首先，每一行每一列的数字不能重合，其次把81个格子分成9个小格子，每一个格子里面的数字不能重合。
转：http://www.cnblogs.com/ganganloveu/p/3828401.html
这题跟N-Queens是一个套路，回溯法尝试所有解。
需要注意的区别是：
本题找到解的处理是return true，因此返回值为bool
N-Queen找到解的处理是保存解，因此返回值为void
对于每个空位'.'，遍历1~9，check合理之后往下一个位置递归。
由于这里路径尝试本质上是有序的，即1~9逐个尝试，因此无需额外设置状态位记录已经尝试过的方向。
注意：只有正确达到最终81位置（即成功填充）的填充结果才可以返回，若不然，将会得到错误的填充。
因此辅助函数solve需要设为bool而不是void
class Solution {
public:
void solveSudoku(vector<vector<char> > &board) {
solve(board, );
}
bool solve(vector<vector<char> > &board, int position)
{
if(position == )
return true;
int row = position / ;
int col = position % ;
if(board[row][col] == '.')
{
for(int i = ; i <= ; i ++)
{//try each digit
board[row][col] = i + '';
if(check(board, position))
if(solve(board, position + ))
//only return valid filling
return true;
board[row][col] = '.';
}
}
else
{
if(solve(board, position + ))
//only return valid filling
return true;
}
return false;
}
bool check(vector<vector<char> > &board, int position)
{
int row = position / ;
int col = position % ;
int gid;
if(row >= && row <= )
{
if(col >= && col <= )
gid = ;
else if(col >= && col <= )
gid = ;
else
gid = ;
}
else if(row >= && row <= )
{
if(col >= && col <= )
gid = ;
else if(col >= && col <= )
gid = ;
else
gid = ;
}
else
{
if(col >= && col <= )
gid = ;
else if(col >= && col <= )
gid = ;
else
gid = ;
}
//check row, col, subgrid
for(int i = ; i < ; i ++)
{
//check row
if(i != col && board[row][i] == board[row][col])
return false;
//check col
if(i != row && board[i][col] == board[row][col])
return false;
//check subgrid
int r = gid/*+i/;
int c = gid%*+i%;
if((r != row || c != col) && board[r][c] == board[row][col])
return false;
}
return true;
}
};