Java数独游戏
chengqiuming 人气:0一、问题描述
数独是一项非常简单的任务。如下图所示，一张 9 行 9 列的表被分成 9 个 3*3 的小方格。在一些单元格中写上十进制数字 1~9，其他单元格为空。目标是用 1 ~9 的数字填充空单元格，每个单元格一个数字，这样在每行、每列和每个被标记为 3*3 的子正方形内，所有 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;
}
}
七、测试
加载全部内容