编写一个程序,通过填充空格来解决数独问题。
数独的解法需 遵循如下规则:
- 数字
1-9
在每一行只能出现一次。 - 数字
1-9
在每一列只能出现一次。 - 数字
1-9
在每一个以粗实线分隔的3x3
宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 '.'
表示。
大致思路:
枚举整个方格图形,对于每个空格的位置再枚举数字1-9,并判断是否符合数独的条件,如果符合则将该空格位置放入该数。当某个空格位置枚举数字1-9时都不满足数独条件,则说明该数独无解。当枚举到某个值而不满足数独条件时,则要进行回溯处理。当遍历完整个二维数组时,则填充出了满足数独条件的数独。
例如:从数字1-4中选择两个数分别填入红色格子和蓝色格子,使得出现的数字不重复。
回溯解题过程:
1.选择一个数填入红色格子
可见当选的数不满足条件时会进行回溯处理,最终红色格子填入2和4符合条件。所以要分别在此基础上选择一个数填入蓝色格子。
2.选一个数填入蓝色格子
最终只有两种填入方案符合条件。
回溯全过程图:
奉上本题代码:
int ROW,COL;//两个值可以直接改为9
bool IsValid(char**board,int row,int col,char k)//是否符合条件
{
//行
for(int i=0;i<COL;i++)
{
if(board[row][i]==k)
return false;
}
//列
for(int j=0;j<ROW;j++)
{
if(board[j][col]==k)
return false;
}
//9宫格
int startrow=row/3*3;
int startcol=col/3*3;//九宫格的起始坐标
for(int i=startrow;i<startrow+3;i++)
{
for(int j=startcol;j<startcol+3;j++)
{
if(board[i][j]==k)
return false;
}
}
return true;
}
bool bacjktracking(char**board)
{
for(int i=0;i<ROW;i++)
{
for(int j=0;j<COL;j++)
{
if(board[i][j]=='.')//只能填入空格
{
for(char s='1';s<='9';s++)
{
if(IsValid(board,i,j,s))
{
board[i][j]=s;
if(bacjktracking(board))//填入某个数符合条件
return true;
board[i][j]='.';
}
}
return false;//当某个格子填入任何数都不符合条件则,数独无解
}
}
}
return true;
}
void solveSudoku(char** board, int boardSize, int* boardColSize){
ROW=boardSize;
COL=*boardColSize;
bool ans=bacjktracking(board);
}