一 问题描述

数独是一项非常简单的任务。如下图所示，一张 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;
    }
}

七 测试