用代码实现解数独

如果我们用穷举的办法,即每个格子都填1~9最后比较结果,那么时间复杂度会达到O(N^N*N),可能算到下个世纪甚至半条命出三都算不完。所以我们不妨换个思路,先把这个大问题拆解为若干小问题,即每个棋盘上的数字都满足以下条件:
1、数字在所在行和所在列只出现一次
2、数字在所在小块也只出现一次
所得到的结果就是正解。
数独棋盘.jpg

那么如何实现它呢,我们可以用深度遍历的方式遍历每个待填写的方格,向其中填入满足条件的数字,如果当某个格子无论填多少都会重复时,则说明前面有方格填写有误,那么就向前回溯修改后继续向前深度遍历,重复这个步骤,直到整个棋盘每个方块都填上了满足条件的数字,就输出棋盘正解。
源码如下:

#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

本文作者:六月丶

本文链接:https://hctra.cn/index.php/archives/66/

版权声明:如无特别声明,本文即为六月'blog原创,仅代表个人观点,如要转载请务必注明文章出处。
最后修改:2019 年 09 月 27 日 09 : 04 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论