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.
暴力深搜
class Solution {
int map[10][10];//预先赋值的数组用来判断第i行第j列是第几个九宫格
bool r[10][10];//r[i][j]表示第i行是否已经有j了，如果有了就为true否则是false
bool c[10][10];//c[i][j]表示第i列是否已经有j了，如果有了就为true否则是false
bool s[10][10];//s[i][j]表示第i个九宫格中是否已经有j了，如果有了就为true否则是false（九宫格排序按从上到下从左到右）
int counts, p[100], q[100];//counts记录的是一共有多少个格子没有填数字，p数组记录他们的行序号，q数组记录他们的列序号
//bool flag;//记录搜索的状态，如果找到答案了就为true，没找到为false
public:
void MakeMap()
{
for(int i = 1; i <= 9; i++)
{
for(int j = 1; j <= 9; j++)
{
if(i <= 3)
{
if(j <= 3)
map[i][j] = 1;
else if(j <= 6)
map[i][j] = 2;
else
map[i][j] = 3;
}
else if(i <= 6)
{
if(j <= 3)
map[i][j] = 4;
else if(j <= 6)
map[i][j] = 5;
else
map[i][j] = 6;
}
else
{
if(j <= 3)
map[i][j] = 7;
else if(j <= 6)
map[i][j] = 8;
else
map[i][j] = 9;
}
}
}
}
void initial(vector<vector<char>> &board){
counts=0;
memset(r,false,sizeof(r));
memset(c,false,sizeof(c));
memset(s,false,sizeof(s));
for(int i = 1; i <= 9; i++)
{
for(int j = 1; j <= 9; j++)
{
if(board[i-1][j-1] != ‘.‘)
{
r[i][board[i-1][j-1]-‘0‘] = true;
c[j][board[i-1][j-1]-‘0‘] = true;
s[map[i][j]][board[i-1][j-1]-‘0‘] = true;
}
else//记录没有填数字的格子
{
counts++;
p[counts] = i;
q[counts] = j;
}
}
}
}
bool DFS(int cur,vector<vector<char>> &board)
{
if(cur == counts + 1)
{
return true;
}
for(int i = 1; i <= 9; i++)//p[cur]表示未填数字的格子的行序号，q[cur]表示未填数字的格子的列序号
{
if(r[p[cur]][i] == false && c[q[cur]][i] == false && s[map[p[cur]][q[cur]]][i] == false)
{
board[p[cur]-1][q[cur]-1] = i + ‘0‘;
r[p[cur]][i] = true;
c[q[cur]][i] = true;
s[map[p[cur]][q[cur]]][i] = true;
if(DFS(cur + 1 , board))return true;
//board[p[cur]-1][q[cur]-1] = ‘.‘;
r[p[cur]][i] = false;
c[q[cur]][i] = false;
s[map[p[cur]][q[cur]]][i] = false;
}
}
}
void solveSudoku(vector<vector<char> > &board) {
MakeMap();//map矩阵的初始化
initial(board);//初始化操作
DFS(1,board);
}
};