深搜:数独问题的解决,优化与进阶

首先是最简单的数独问题:题目链接(数独的规则是每行每列,每个3 × 3的九宫格内数字1~9均恰好出现一次,如果还有疑惑可以自行百度)

当然我们把题目再简化一点,每次的测试样例只有一个数独,按9*9无换行的形式输入测试样例,输入输出如下:

103000509      
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

输入为9×9的数据。一共9行,每行有9个数字。数字为0表示对应的数字盘为空。

输出:对于每个测试用例,程序应以与输入数据相同的格式打印解决方案(9×9)。空单元格必须根据规则进行填充。如果解决方案不是唯一的,则程序可以打印其中任何一种。

接下来尝试用深搜来解决问题,当然我们只是单纯的深搜,先不做其他优化:

1.我们先将数独输入,定义一个char类型的全局变量数组s[10][10],通过二重循环cin读入数据,可以在main函数开头加上cin.tie(0)进行优化,然后我们定义三个bool类型的辅助判断二维数组,就命名为vx[10][10],vy[10][10]和vv[10][10],这三个二维数组作为全局变量。我们先展示一下代码,再解释这三个辅助数组的含义:

#include<bits/stdc++.h>
using namespace std;
char s[10][10];
bool vx[10][10],vy[10][10],vv[10][10];
bool f;
int main()
{
    cin.tie(0);
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
        {
            cin>>s[i][j];
        }
    for(int i=1;i<9;i++)
        for(int j=0;j<9;j++)
        {
            if(s[i][j]!='0'){
              vx[i][s[i][j]-'0']=true;
              vy[j][s[i][j]-'0']=true;
              vv[i/3*3+j/3][s[i][j]-'0']=true;  
            }
        }
    dfs(0,0); 
    return 0;
}

2.可以看到我们读入数据后又做了一个二重循环,用到了三个辅助判断的二维数组,这三个数组中vx用来记录每一行哪些数不可以填,vy用来记录每一列哪些数不可以填,vv用来记录每个九宫格哪些数不可以填,实际上vv数组将数独分成了按自左向右,自上向下的0-8个小的九宫格。因为全局变量的二维bool数组开始全为false,我们将其改为true后代表某行某列某个小九宫格的数是不能再用的。(注:f这个全局变量用在dfs函数里)

3.好,前面都是一些准备工作,我们接下来做dfs深度优先搜索,还是先看一下dfs这个被调用的深搜函数的代码:

void dfs(int x,int y)
{
    if(f)   return;
    if(x==9) 
    {
        f=true;
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
            {
                if(j!=8)
                {
                    cout<<s[i][j];
                }
                else
                {
                    cout<<s[i][j]<<endl;
                } 
            }
        return;
    }
    if(y==9)   //如果到了行末,换行搜索
    {
        dfs(x+1,0);
      	return;
    }
    if(s[x][y]!='0')  //如果该空已经有了数字,不用填,向下一个空格搜索  
    {
        dfs(x,y+1);
      	return;
    }
    for(int i=1;i<=9;i++)
    {
        if(!vx[x][i]&&!vy[y][i]&&!vv[x/3*3+y/3][i]){
            s[x][y]='0'+i;
            vx[x][i]=true;
            vy[y][i]=true;
            vv[x/3*3+y/3][i]=true;
            dfs(x,y+1);
            vx[x][i]=false;
            vy[y][i]=false;
            vv[x/3*3+y/3][i]=false;
            s[x][y]='0';
        }
    }
}

深搜是自上往下,自左往右的方式开始搜索,首先如果搜到第九行了,(注意我们数据是存在0-8行)我们这个数独明显被解决了,将全局变量f改为true,直接输出数据,判断f,然后退出dfs函数。然后具体搜索的逻辑也很简单了,如果搜到了某一行的末尾,我们就换行搜索,如果某空格已经填过了,向下一个空格搜索,如果某个空格可填,从1-9开始,依次尝试,之前的三个辅助判断数组用于判断某个数字能否填入该空格,填入后修改辅助数组和空格内容继续搜索下一个空格,然后注意如果后续走不通的话你还是要回来的,所以将改动的内容再改回去,这样整个搜索函数就完成了。最后看一下整体的源代码:

#include<bits/stdc++.h>
using namespace std;
char s[10][10];
bool vx[10][10],vy[10][10],vv[10][10];
bool f;
void dfs(int x,int y)
{
    if(f)   return;
    if(x==9) 
    {
        f=true;
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
            {
                if(j!=8)
                {
                    cout<<s[i][j];
                }
                else
                {
                    cout<<s[i][j]<<endl;
                } 
            }
        return;
    }
    if(y==9)   
    {
        dfs(x+1,0);
      	return;
    }
    if(s[x][y]!='0')    
    {
        dfs(x,y+1);
      	return;
    }
    for(int i=1;i<=9;i++)
    {
        if(!vx[x][i]&&!vy[y][i]&&!vv[x/3*3+y/3][i]){
            s[x][y]='0'+i;
            vx[x][i]=true;
            vy[y][i]=true;
            vv[x/3*3+y/3][i]=true;
            dfs(x,y+1);
            vx[x][i]=false;
            vy[y][i]=false;
            vv[x/3*3+y/3][i]=false;
            s[x][y]='0';
        }
    }
}
int main()
{
    cin.tie(0);
    for(int i=0;i<9;i++)
        for(int j=0;j<9;j++)
        {
            cin>>s[i][j];
        }
    for(int i=1;i<9;i++)
        for(int j=0;j<9;j++)
        {
            if(s[i][j]!='0'){
              vx[i][s[i][j]-'0']=true;
              vy[j][s[i][j]-'0']=true;
              vv[i/3*3+j/3][s[i][j]-'0']=true;  
            }
        }
    dfs(0,0); 
    return 0;
}

代码已经编译并测试通过了,你可以自己尝试在电脑上复制代码后输入一组测试数据试一下。

但是代码运行时间还是超时了,这个题是算法竞赛上的题目,时间限制很高,要压缩到1s以内,所以还要做优化。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇