首页 > 代码库 > #计算机#数独
#计算机#数独
数独是一项益智小游戏，规则简单易懂，但内容千变万化。这次我想要研究的是用java编程实现解数独和数独题目的生成。首先要弄清数独的游戏规则：在一个9×9的方格中分布着1-9的数字和空格，玩家在空格中填写适当的数字，使得每行、每列、9个3×3的方格中数字1-9均只出现一次。
对于解数独初步构思的时候我产生了两种想法：
第一种想法利用计算机强大的运算能力，遍历当前空格所有可以填入的数字，向后递归，当某个空格不能填入数字，而空格数不为零时返回上一步。如果某一步只能填入一个确定的数字，可以把这一步优先填好，或者在后续重复经过时直接跳过，来进行优化。
第二种想法是贴近我在填数独时的思路，以3×3的方格为单位，当出现在一行或者一列上的3个方格中有两个出现同一数字，那么第3个数字的行或者列就可以唯一确定。
首先解数独，产生一个可以作为数独完整解的矩阵：
package sudoku;
import java.util.Random;
public class sudoku {
/** 存储数字的数组 */
private static int[][] n = new int[9][9];
/** 生成随机数字的源数组，随机数字从该数组中产生 */
private static int[] num = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
public static int[][] generateShuDu(){
// 生成数字
for (int i = 0; i < 9; i++) {
// 尝试填充的数字次数
int time = 0;
// 填充数字
for (int j = 0; j < 9; j++) {
// 产生数字
n[i][j] = generateNum(time);
// 如果返回值为0，则代表卡住，退回处理
// 退回处理的原则是：如果不是第一列，则先倒退到前一列，否则倒退到前一行的最后一列
if (n[i][j] == 0) {
// 不是第一列，则倒退一列
if (j > 0) {
j -= 2;
continue;
} else {// 是第一列，则倒退到上一行的最后一列
i--;
j = 8;
continue;
}
}
// 填充成功
if (isCorret(i, j)) {
// 初始化time，为下一次填充做准备
time = 0;
} else { // 继续填充
// 次数增加1
time++;
// 继续填充当前格
j--;
}
}
}
return n;
}
/**
* 是否满足行、列和3X3区域不重复的要求
*
* @param row
* 行号
* @param col
* 列号
* @return true代表符合要求
*/
private static boolean isCorret(int row, int col) {
return (checkRow(row) & checkLine(col) & checkNine(row, col));
}
/**
* 检查行是否符合要求
*
* @param row
* 检查的行号
* @return true代表符合要求
*/
private static boolean checkRow(int row) {
for (int j = 0; j < 8; j++) {
if (n[row][j] == 0) {
continue;
}
for (int k = j + 1; k < 9; k++) {
if (n[row][j] == n[row][k]) {
return false;
}
}
}
return true;
}
/**
* 检查列是否符合要求
*
* @param col
* 检查的列号
* @return true代表符合要求
*/
private static boolean checkLine(int col) {
for (int j = 0; j < 8; j++) {
if (n[j][col] == 0) {
continue;
}
for (int k = j + 1; k < 9; k++) {
if (n[j][col] == n[k][col]) {
return false;
}
}
}
return true;
}
/**
* 检查3X3区域是否符合要求
*
* @param row
* 检查的行号
* @param col
* 检查的列号
* @return true代表符合要求
*/
private static boolean checkNine(int row, int col) {
// 获得左上角的坐标
int j = row / 3 * 3;
int k = col / 3 * 3;
// 循环比较
for (int i = 0; i < 8; i++) {
if (n[j + i / 3][k + i % 3] == 0) {
continue;
}
for (int m = i + 1; m < 9; m++) {
if (n[j + i / 3][k + i % 3] == n[j + m / 3][k + m % 3]) {
return false;
}
}
}
return true;
}
/**
* 产生1-9之间的随机数字 规则：生成的随机数字放置在数组8-time下标的位置，随着time的增加，已经尝试过的数字将不会在取到
* 说明：即第一次次是从所有数字中随机，第二次时从前八个数字中随机，依次类推， 这样既保证随机，也不会再重复取已经不符合要求的数字，提高程序的效率
* 这个规则是本算法的核心
*
* @param time
* 填充的次数，0代表第一次填充
* @return
*/
private static Random r=new Random();
private static int generateNum(int time) {
// 第一次尝试时，初始化随机数字源数组
if (time == 0) {
for (int i = 0; i < 9; i++) {
num[i] = i + 1;
}
}
// 第10次填充，表明该位置已经卡住，则返回0，由主程序处理退回
if (time == 9) {
return 0;
}
// 不是第一次填充
// 生成随机数字，该数字是数组的下标，取数组num中该下标对应的数字为随机数字
// int ranNum = (int) (Math.random() * (9 - time));//j2se
int ranNum=r.nextInt(9 - time);//j2me
// 把数字放置在数组倒数第time个位置，
int temp = num[8 - time];
num[8 - time] = num[ranNum];
num[ranNum] = temp;
// 返回数字
return num[8 - time];
}
public static void main(String[] args) {
int[][] shuDu=generateShuDu();
// 输出结果
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(shuDu[i][j] + " ");
}
System.out.println();
}
}
}
每次运行都会产生一个数独的完整解，某次运行结果如下：
8 4 1 6 7 5 2 9 3
3 9 6 2 8 1 7 5 4
5 7 2 4 9 3 1 6 8
6 5 8 3 1 9 4 2 7
9 3 7 8 4 2 5 1 6
1 2 4 5 6 7 3 8 9
2 6 3 9 5 4 8 7 1
4 1 9 7 2 8 6 3 5
7 8 5 1 3 6 9 4 2
在这个结果的基础上去掉某些位上的数字，产生一个数独题目。初始数字的数量能够决定题目的难度，至少有17个数字才能保证数独有唯一解。但是在我观察分析题目的时候，并没有发现在去掉完整解中的数字时有什么限制条件，暂且先假定去掉一定数量的任意数字可以形成一个有唯一解的数独题目。在这种情况下只需要产生随机数来挖空这个完整解，就得到了数独题目。
要产生随机数，可以使用Java api中java.lang包中的Math类.Math类以静态方法的方式提供常用的数学方法，其中Math.random()方法是一个可以产生[0.0,1.0]区间内的一个双精度浮点数的方法
如：产生一个100以内的整数：int x=(int)(Math.random()*100);
又如：产生一个1-50之间的随机数：int x=1+(int)(Math.random()*50)；
#计算机#数独