深度搜索解决数独游戏

x33g5p2x  于2022-08-17 转载在 其他  
字(2.4k)|赞(0)|评价(0)|浏览(358)

一 问题描述

数独是一项非常简单的任务。如下图所示,一张 9 行 9 列的表被分成 9 个 33 的小方格。在一些单元格中写上十进制数字 1~9,其他单元格为空。目标是用 1 ~9 的数字填充空单元格,每个单元格一个数字,这样在每行、每列和每个被标记为 33 的子正方形内,所有 1~9 的数字都会出现。编写一个程序来解决给定的数独任务。


 

二 输入和输出

1 输入

对于每个测试用例,后面都跟 9 行,对于表的行。在每行上都给出 9 个十进制数字,对于这一行中的单元格。如果单元格为空,则用 0  表示。

2 输出

对于每个测试用例,程序都应该与输入数据相同的格式打印解决方案。空单元格必须按照规则填充。如果解决方案不是唯一,那么程序可以打印其中任何一个。

三 输入和输出样例

1 输入样例

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

2 输出样例

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

四 分析

该问题为数独游戏,为典型的九空格问题,可以采用回溯法搜索。把一个 9 行 9 列的网格再细分为 9 个 3*3 的子网格,要求在每行、每列、每个子网格内都使用一次 1~9 的一个数字,即在每行、每列、每个子网格内都不允许出现相同的数字。

0 表示空白位置,其他均为已填入的数字。要求填完九空格并输出(如果有多种结果,则只需出其中一种)。如果给定的九宫格无法按照要求填出来,则输出原来所输入的未填的九宫格。

用 3 个数组标记每行、每列、每个子网格已用的数字。

row[i][x]:用于标记第 i 行中的数字 x 是否出现。

row[j][y]:用于标记第 j 列中的数字 y 是否出现。

grid[k][z]:标记第 k 个 3*3 子网格中的数字 z 是否出现。

row 和 col 的标记比较好处理。行 i、列 j 对应的子网格编号 k=3((i-1)/3)+(j-1)/3+1,如下图所示。

五 算法设计

1 预处理输入数据。

2 从左上角(1,1)开始按行搜索,如果行 i=10,则说明找到答案,返回 1。

3 如果 map[i][j] 已填数字,则判断如果 列 j=9,则说明处理到当前行的最后一列,继续下一行第 1 列的搜索,即 dfs(i+1,1),否则在当前行的下一列搜索 dfs(i,j+1)。如果搜索成功,则返回1,否则返回 0。

4 如果 map[i][j] 未填数字,则计算当前位置(i,j)所属的子网格 k=3((i-1)/3)+(j-1)/3+1。枚举数字 1~9 填空,如果当前行、当前列、当前子网均未填写数字,则填写该数字并标记该数字已出现。如果判断列 j =9,则说明处理到当前行的最后一列,继续下一行第 1 列的搜索,即 dfs(i+1,1),否则在当前行的下一列搜索,即 dfs(i,j+1)。如果搜索失败,否则返回 1。

六 代码

package com.platform.modules.alg.alglib.poj2676;

public class Poj2676 {
    public String output = "";
    int map[][] = new int[10][10];
    // row[i][x] 标记在第 i 行中数字 x 是否已出现
    boolean row[][] = new boolean[10][10];
    // col[j][y] 标记在第 j 列中数字 y 是否已出现
    boolean col[][] = new boolean[10][10];
    // grid[k][z] 标记在第 k 个 3*3 子格中数字z是否已出现
    boolean grid[][] = new boolean[10][10];

    boolean dfs(int i, int j) {
        if (i == 10)
            return true;
        boolean flag;
        if (map[i][j] > 0) {
            if (j == 9)
                flag = dfs(i + 1, 1);
            else
                flag = dfs(i, j + 1);
            return flag ? true : false;
        } else {
            int k = 3 * ((i - 1) / 3) + (j - 1) / 3 + 1;
            for (int x = 1; x <= 9; x++) {//枚举数字1~9填空
                if (!row[i][x] && !col[j][x] && !grid[k][x]) {
                    map[i][j] = x;
                    row[i][x] = true;
                    col[j][x] = true;
                    grid[k][x] = true;
                    if (j == 9)
                        flag = dfs(i + 1, 1);
                    else
                        flag = dfs(i, j + 1);
                    if (!flag) { //回溯,继续枚举
                        map[i][j] = 0;
                        row[i][x] = false;
                        col[j][x] = false;
                        grid[k][x] = false;
                    } else
                        return true;
                }
            }
        }
        return false;
    }

    public String cal(String input) {
        String[] line = input.split("\n");

        char ch;
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                ch = line[i-1].charAt(j-1);
                map[i][j] = ch - '0';
                if (map[i][j] > 0) {
                    int k = 3 * ((i - 1) / 3) + (j - 1) / 3 + 1;
                    row[i][map[i][j]] = true;
                    col[j][map[i][j]] = true;
                    grid[k][map[i][j]] = true;
                }
            }
        }

        dfs(1, 1);
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++)
                output += map[i][j];
            output += "\n";
        }
        return output;
    }
}

七 测试

相关文章