如果我们用穷举的办法,即每个格子都填1~9最后比较结果,那么时间复杂度会达到O(N^N*N),可能算到下个世纪甚至半条命出三都算不完。所以我们不妨换个思路,先把这个大问题拆解为若干小问题,即每个棋盘上的数字都满足以下条件:
1、数字在所在行和所在列只出现一次
2、数字在所在小块也只出现一次
所得到的结果就是正解。
那么如何实现它呢,我们可以用深度遍历的方式遍历每个待填写的方格,向其中填入满足条件的数字,如果当某个格子无论填多少都会重复时,则说明前面有方格填写有误,那么就向前回溯修改后继续向前深度遍历,重复这个步骤,直到整个棋盘每个方块都填上了满足条件的数字,就输出棋盘正解。
源码如下:
#include<iostream>
#include<cstdio>
using namespace std;
int arr[10][10] = {0};
int len{0};
void findAnswer(int idx){
for(;idx<len*len;idx++){
if(arr[idx/len][idx%len]==72){
bool flag = true;
for(int num = 1;num <= len;num++){ //深度回溯
flag = true;
for(int i = 0;i < len;i++)
if(arr[i][idx%len]==num)flag = false;
if(flag==false)continue; //如果所在列出现过这个数字,则跳过循环,检查下一个数字
for(int i = 0;i < len;i++)
if(arr[idx/len][i]==num)flag = false;
if(flag==false)continue; //如果所在行出现过这个数字,则跳过循环,检查下一个数字
int lent = len==9?3:2; //每小块宽度
for(int i = 0;i < len;i++){
for(int j = 0;j < len;j++)
//如果在所在小块内出现过这个数字,则跳过循环,检查下一个数字
if(i/lent==(idx/len)/lent&&j/lent==(idx%len)/lent&&arr[i][j] == num)
flag = false;
}
if(flag==false)continue;
arr[idx/len][idx%len] = num;
findAnswer(idx+1);
}
arr[idx/len][idx%len] = 72; //回溯前把脏数据还原为'x'
return;
}
}
cout << "\n解法:" << endl;
//打印结果
for(int i = 0;i < len;i++){
for(int j = 0;j < len;j++)
cout << arr[i][j] << " ";
cout << endl;
}
}
int main(){
char num;
cout << " 请输入数独棋盘大小(例:4,6,9):" << endl;
cin >> len;cin.get();
for(int i = 0;i < len;i++){
for(int j = 0;j < len;j++)
arr[i][j] = cin.get()-'0';
cin.get();
}
findAnswer(0);
return 0;
}
解决思路其实和八皇后问题很相似,不过因为要填的格子较多且相对位置自由,所以要稍复杂点。
这个算法算普通难度的数独秒出结果,算国手难度大概在三秒左右。
测试数据:
4
3xx4
42x1
x342
24x3
6
x61453
4x5216
3461x5
152364
5x4631
6x354x
9
xx971325x
x3x8x2x6x
xx85x43xx
xx395712x
x142xx73x
52x3xx98x
7514xx6xx
xxxx7x8xx
x8613xxxx