题解 P1784 【数独】

· · 题解

欢迎回来

欢迎回到TNT BOOM大讲堂！

今天我们来讲 P1784数独 这道题

首先明白数独是什么？

懂得跳过

数独（shù dú）是源自18世纪瑞士的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复 。

数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。

好的，明白了以后，我们想一想，计算机如何实现填数独???

首先，我们先明确，这道题是dfs,所以我们得先写出dfs函数，但是在这个过程中，我遇到了一个困难，就是如何判断某个数字在某一宫里的关系，我想到了一个方法，就是定义一个数组m，来存放每一宫的关系。

不好画图，直接那程序写出来了：

int m[10][10] =
{
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9}
};

通过这样的方法，我们就有办法知道某一宫的关系了！

话不多说，上AC代码：

详细的看注释。

#include<cstdio>
//#include<cstdlib>
using namespace std;

int a[11][11]; //用来存九宫数独的数字 
bool flag1[11][11], flag2[11][11], flag3[11][11];

// flag1[i][j]代表第i行,值为j的数是否使用
// flag2[i][j]代表第i列,值为j的数是否使用
// flag3[i][j]代表第i宫,值为j的数是否使用

int m[10][10] =
{
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
    {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
    {0, 7, 7, 7, 8, 8, 8, 9, 9, 9}
}; //用来帮助我们定位第几宫；
//将第i宫数字初始化为i，我们就可以根据m的下标直接定位是第几宫 

void dfs(int x, int y)
{
    if(x == 10 && y == 1) //x表示行，y表示列，10行1列表示数独已经填满 
    {
        for(int i = 1; i <= 9; i++) //数独填满，输出即可 
        {
            for(int j = 1; j <= 9; j++)
                printf("%d ", a[i][j]);
            puts("");
        }
        //puts(""),system("pause");
        return;
    }
    int x_new = x, y_new = y + 1; //(x_new,y_new)表示(x,y)的下一个格子的位置 
    if(y_new == 10) //若列数不满十,则行数不变列数加1;若列数满十,则行数加1,列数变为1 
    {
        x_new++;
        y_new = 1;
    }
    if(a[x][y]) //若(x,y)原来有数字 
        dfs(x_new, y_new); //递归枚举下一个格子 
    else //若(x,y)原来没有数字，枚举所有可能：填充1-9
    {
        for(int i = 1; i <= 9; i++)
        {//若第x行 or 第y列 or 第m[x][y]宫 出现值为i的数字，则跳过 
            if(flag1[x][i] || flag2[y][i] || flag3[m[x][y]][i])
                continue;
            a[x][y] = i; //x行y列m[x][y]宫都没有出现数字i，则a[x][y]可以填i 
            flag1[x][i] = flag2[y][i] = flag3[m[x][y]][i] = true;
            // a[x][y]可以填i后，x行y列m[x][y]宫都出现了数字i，赋值为true 
            dfs(x_new, y_new); //递归枚举下一个格子 
            flag1[x][i] = flag2[y][i] = flag3[m[x][y]][i] = false; 
            //下一次递归还要用这些标记，所以每次用完要清零 
            a[x][y] = 0; // 可删来让学生查错，回溯
        }
    }
}

int main()
{
    for(int i = 1; i <= 9; i++)
        for(int j = 1; j <= 9; j++)
        {
            scanf("%d", &a[i][j]);
            if(a[i][j] == 0) continue;
//输入的同时根据输入的结果将flag1、flag2、flag3三个数字初始化 
            flag1[i][a[i][j]] = true; 
            flag2[j][a[i][j]] = true;
            flag3[m[i][j]][a[i][j]] = true;
        }
    dfs(1, 1);

    return 0;
}

好了，本期TNT BOOM 大讲堂就说到这里了。

Bye Bye!