搜索进阶——数独问题

1.问题描述：

2.问题分析：

这道题目是比较经典的搜索问题，当你学会怎么解八皇后问题的时候，就慢慢的进入了搜索之道，这一道题目比较难的点就是33的格子内填充的数不能重复。行和列不重复很简单，怎么判定重复与否，我们将数独棋盘分为9个33的棋盘并且将其编号：

可以发现规律每一个编号的33的格子为当前的x,y
x / 3 * 3 + y / 3
我们可以在主函数里通过设置判断行，列，33格子是否使用，visx[9][9]代表的是该行所用的数，比如visx[0][1]代表的是第0行已经存在数字1了，第0行则不能填充数字1了.visy[9][9]代表的是该列所用的数,比如visy[0][1]代表的是第0列已经存在数字1了，不能够放数字一了,vis3[9][9]代表的是33的格子中存放的数，比如vis3[0][1]代表在0编号中的33的格子已经放了1了则在其余8个格子不能够放1了。

for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (map[i][j] != '*') {
                visx[i][map[i][j] - '0'] = true; //因为是字符数组，所以转换为整数需要-'0'
                visy[j][map[i][j] - '0'] = true;
                vis3[i / 3 * 3 + j / 3][map[i][j] - '0'] = true;
            }
        }
    }

然后我们写dfs函数，从行开始搜，当行为9时，说明找到一组正解，我们通过一个bool变量记录，return掉，当列为9时我们搜索下一行也就是dfs(x + 1,0).这里剪枝了一下，当map[x][y] != '*'的时候说明有数了，就不用继续填充了，需要注意的是每次填充后，我们之后需要取消标记，找寻其他的解。

3.源码：

#include <iostream>
#include <cstdio>
using namespace std;

char map[9][9];  //数独棋盘
bool visx[9][9],visy[9][9],vis3[9][9];//visx表示为行的某个数是否使用，visy表示列的某个数是否使用，vis3表示3*3的小格子
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) {
                    printf("%c ",map[i][j]);
                } else {
                    printf("%c\n",map[i][j]);
                }
            }
        }
    }
    if (y == 9) {
        dfs(x + 1,0);
        return;
    }
    if (map[x][y] != '*') {
        dfs(x,y + 1);
        return;
    }
    for (int i = 1; i <= 9; i++) {
        if (!visx[x][i] && !visy[y][i] && !vis3[x / 3 * 3 + y / 3][i]) {
            map[x][y] = i + '0';
            visx[x][i] = true;
            visy[y][i] = true;
            vis3[x / 3 * 3 + y / 3][i] = true;
            dfs(x, y + 1);
            visx[x][i] = false;
            visy[y][i] = false;
            vis3[x / 3 * 3 + y / 3][i] = false;
            map[x][y] = '*';
        }
    }
}

int main() {
    for (int i = 0; i < 9; i++) {
       for (int j = 0; j < 9; j++) {
           scanf(" %c",&map[i][j]);
       }
    }
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (map[i][j] != '*') {
                visx[i][map[i][j] - '0'] = true;
                visy[j][map[i][j] - '0'] = true;
                vis3[i / 3 * 3 + j / 3][map[i][j] - '0'] = true;
            }
        }
    }
    dfs(0,0);
    return 0;
}

欢迎关注Blog:
www.lyxueit.com
大家一起学习交流。