`
MouseLearnJava
  • 浏览: 458934 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

Swing数独游戏(一):终盘生成之矩阵转换法

阅读更多

数独(すうどく,Sudoku)是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫内的数字均含1-9,不重复。

参考:http://baike.baidu.com/link?url=ePXUCvpBaRKBkEA3pVfOkg3m-NBozO6a4GDS0N3E5_gK1nnJCDzd5O-YL1w7c5S3

最近手机上安装了数独游戏,算是重拾该游戏了。为了更加了解游戏生成的原理,自己在闲暇时间做了一个Swing版的数独游戏,将会写几篇博文记录一些内容。 内容大致如下:

  • Swing数独游戏(一):终盘生成之矩阵转换法
  • Swing数独游戏(二):终盘生成之随机法
  • Swing数独游戏(三):“挖洞”法
  • Swing数独游戏(四):关键功能及实现。
  • ... ...



数独游戏一般产生的过程包括两个过程:

1. 生成一个终盘 (9 x 9)。
2. 然后根据难易程度,在终盘上挖掉不同数目的数字。

这样,就能确定那些格子是有数据且不可编辑以及哪些没有数据且可编辑的。

比如,我实现的一个Swing数独游戏界面:




产生数独终盘(9x9 的二维数组)的方法主要有两种:矩阵转换法或者随机法.

本篇博文将介绍使用矩阵转换的方法生成终盘,具体步骤如下:

1. 指定一个数独矩阵作为矩阵转换的种子矩阵

为了完成矩阵的转换,我们需要有可用的数独数组作为种子数组才行。

做法可以如下:
1. 先给定几个可用数独数组作为备选种子矩阵。
2. 产生一个随机数,随机选中其中的一个作为种子矩阵。

可以写一个产生种子矩阵的工具类,如:
package my.sudoku.utils;

import java.util.Random;

public final class SeedSudokuMatrixFactory {

	private static final Random random = new Random();

	private static final int seedSudokuArrays[][][] = {
			{ { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, { 4, 5, 6, 7, 8, 9, 1, 2, 3 },
					{ 7, 8, 9, 1, 2, 3, 4, 5, 6 },
					{ 2, 1, 4, 3, 6, 5, 8, 9, 7 },
					{ 3, 6, 5, 8, 9, 7, 2, 1, 4 },
					{ 8, 9, 7, 2, 1, 4, 3, 6, 5 },
					{ 5, 3, 1, 6, 4, 2, 9, 7, 8 },
					{ 6, 4, 2, 9, 7, 8, 5, 3, 1 },
					{ 9, 7, 8, 5, 3, 1, 6, 4, 2 } },
			{ { 3, 9, 4, 5, 1, 7, 6, 2, 8 }, { 5, 1, 7, 6, 2, 8, 3, 9, 4 },
					{ 6, 2, 8, 3, 9, 4, 5, 1, 7 },
					{ 9, 3, 5, 4, 7, 1, 2, 8, 6 },
					{ 4, 7, 1, 2, 8, 6, 9, 3, 5 },
					{ 2, 8, 6, 9, 3, 5, 4, 7, 1 },
					{ 1, 4, 3, 7, 5, 9, 8, 6, 2 },
					{ 7, 5, 9, 8, 6, 2, 1, 4, 3 },
					{ 8, 6, 2, 1, 4, 3, 7, 5, 9 } },
			{ { 7, 6, 1, 9, 8, 4, 2, 3, 5 }, { 9, 8, 4, 2, 3, 5, 7, 6, 1 },
					{ 2, 3, 5, 7, 6, 1, 9, 8, 4 },
					{ 6, 7, 9, 1, 4, 8, 3, 5, 2 },
					{ 1, 4, 8, 3, 5, 2, 6, 7, 9 },
					{ 3, 5, 2, 6, 7, 9, 1, 4, 8 },
					{ 8, 1, 7, 4, 9, 6, 5, 2, 3 },
					{ 4, 9, 6, 5, 2, 3, 8, 1, 7 },
					{ 5, 2, 3, 8, 1, 7, 4, 9, 6 } },
			{ { 7, 1, 5, 4, 3, 6, 2, 9, 8 }, { 4, 3, 6, 2, 9, 8, 7, 1, 5 },
					{ 2, 9, 8, 7, 1, 5, 4, 3, 6 },
					{ 1, 7, 4, 5, 6, 3, 9, 8, 2 },
					{ 5, 6, 3, 9, 8, 2, 1, 7, 4 },
					{ 9, 8, 2, 1, 7, 4, 5, 6, 3 },
					{ 3, 5, 7, 6, 4, 1, 8, 2, 9 },
					{ 6, 4, 1, 8, 2, 9, 3, 5, 7 },
					{ 8, 2, 9, 3, 5, 7, 6, 4, 1 } } };
	
	private SeedSudokuMatrixFactory()
	{}

	/**
	 * 随机获取一个预先定义好的数独数组
	 */
	public static int[][] retrieveSeedSudokuArrayByRandom() {
		int randomInt = random.nextInt(seedSudokuArrays.length);

		return seedSudokuArrays[randomInt].clone();

	}

}


2. 确定矩阵变换的方式

拥有了一个数独可用矩阵,我们就可以对这个种子矩阵作转换处理去获取更多的可用数独终盘矩阵。

矩阵转换的方式有很多,在这里列举如下几个:

a) 交换两个数的位置

我们可以生成1到9组成的List,然后遍历种子矩阵,然后矩阵中的数据将用随机产生的List中的对应数字代替。做法如下:
1. 用数字对9求余,得到的值作为List的索引。
    比如 i行j列的数字是3,那么index就是3
2. 根据index获取对应的值,待交换的数字就是List.get(index),
    比如得到的数字是6. 那么3就会用6来代替,其它数字的替换方式一样。


package my.sudoku.utils;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class SudokuPuzzleMatrixGenerator {

	/**待转换的数组种子数组*/
	private int sampleArray[][] = SeedSudokuMatrixFactory.retrieveSeedSudokuArrayByRandom();

	private Random random = new Random();

	public int[][] generateSudokuArray() {

		List<Integer> randomList = buildRandomList();
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				for (int k = 0; k < 9; k++) {
					if (sampleArray[i][j] == randomList.get(k)) {
						sampleArray[i][j] = randomList.get((k + 1) % 9);
						break;
					}
				}
			}
		}
		return sampleArray;
	}

private List<Integer> buildRandomList() {
		int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		int randomInt = 0;
		for (int i = 0; i < 20; i++) {
			randomInt = random.nextInt(8) + 1;
			int temp = array[0];
			array[0] = array[randomInt];
			array[randomInt] = temp;
		}

		List<Integer> randomList = new ArrayList<Integer>();
		for (int i : array) {
			randomList.add(i);
		}
		return randomList;
	}

}

下图就是一个数字9和数据1交换的例子:



b) 调整行或列的位置




行和列的转换,需要保证的是:交换只发生在前三行,中间三行,最后三行,前三列,中间三列以及最后三列之间。而不能越界交换,比如第一行和第四行交换就是不允许的。


public int[][] generateSudokuArray1() {
		int randomRowNum = 0;
		//随机交换20次
		for (int i = 0; i < 20; i++) {
			randomRowNum = random.nextInt(8) + 1;
			for (int col = 0; col < 9; col++) {
				if(randomRowNum % 3 ==0)
				{
					int temp = sampleArray[randomRowNum][col];
					sampleArray[randomRowNum][col] = sampleArray[randomRowNum+1][col];
					sampleArray[randomRowNum+1][col] = temp;
				}
				else
				{
					int temp = sampleArray[randomRowNum][col];
					sampleArray[randomRowNum][col] = sampleArray[randomRowNum-1][col];
					sampleArray[randomRowNum-1][col] = temp;
				}

			}

		}
		return sampleArray;
	}

	public int[][] generateSudokuArray2() {
		int randomColumnNum = 0;

		for (int i = 0; i < 20; i++) {
			randomColumnNum = random.nextInt(8) + 1;

			for (int row = 0; row < 9; row++) {
				
				if(randomColumnNum %3 ==0)
				{
					int temp = sampleArray[row][randomColumnNum];
					sampleArray[row][randomColumnNum] = sampleArray[row][randomColumnNum+1];
					sampleArray[row][randomColumnNum+1] = temp;
				}else
				{
					int temp = sampleArray[row][randomColumnNum];
					sampleArray[row][randomColumnNum] = sampleArray[row][randomColumnNum-1];
					sampleArray[row][randomColumnNum-1] = temp;
				}
				
			}
		}
		return sampleArray;
	}

c) 调整块的位置




d) 矩阵旋转




另外还可以以对角线对对称,交换数据等方式,如:

	public int[][] getArrayWithDiagonalSymmetry() {
		int[][] result = new int[9][9];
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				
				result[i][j] = sampleArray[j][i];
			}
		}
		return result;
	}


矩阵转换法生成数独终盘的方式具有方便速度块的特点。它的缺点产生的终盘的随机性不是很强,毕竟是从一个固定的种子矩阵转换而得的。

下一篇博文将介绍随机法去产生数独,从而增强产生数独终盘的随机性。

测试代码及其测试结果如下:

package test;

import java.io.IOException;
import my.sudoku.utils.SudokuPuzzleMatrixGenerator;

public class Main {

	public static void main(String[] args) throws IOException {
		
		SudokuPuzzleMatrixGenerator sp = new SudokuPuzzleMatrixGenerator();
		
		/*
		 * 采用换数字的方法转换矩阵 
		 */
		System.out.println("采用换数字的方法转换矩阵");
		printArray(sp.generateSudokuArray());
		
		/*
		 * 采用行交换的方法转换矩阵 
		 */
		System.out.println("采用行交换的方法转换矩阵");
		printArray(sp.generateSudokuArray1());
		
		/*
		 * 采用列交换的方法转换矩阵
		 */
		System.out.println("采用列交换的方法转换矩阵");
		printArray(sp.generateSudokuArray2());
		
		
		/*
		 * 采用对角线对称交换数据
		 */
		System.out.println("采用列交换的方法转换矩阵");
		printArray(sp.getArrayWithDiagonalSymmetry());
		
		
	}

	public static void printArray(int a[][]) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				System.out.print(a[i][j]);
				System.out.print(" ");
			}
			System.out.println();
		}
	}
	
	
}
产生的种子矩阵是:
7 6 1 9 8 4 2 3 5
9 8 4 2 3 5 7 6 1
2 3 5 7 6 1 9 8 4
6 7 9 1 4 8 3 5 2
1 4 8 3 5 2 6 7 9
3 5 2 6 7 9 1 4 8
8 1 7 4 9 6 5 2 3
4 9 6 5 2 3 8 1 7
5 2 3 8 1 7 4 9 6
采用换数字的方法转换矩阵
3 7 9 2 6 8 4 5 1
2 6 8 4 5 1 3 7 9
4 5 1 3 7 9 2 6 8
7 3 2 9 8 6 5 1 4
9 8 6 5 1 4 7 3 2
5 1 4 7 3 2 9 8 6
6 9 3 8 2 7 1 4 5
8 2 7 1 4 5 6 9 3
1 4 5 6 9 3 8 2 7
采用行交换的方法转换矩阵
2 6 8 4 5 1 3 7 9
3 7 9 2 6 8 4 5 1
4 5 1 3 7 9 2 6 8
7 3 2 9 8 6 5 1 4
5 1 4 7 3 2 9 8 6
9 8 6 5 1 4 7 3 2
6 9 3 8 2 7 1 4 5
8 2 7 1 4 5 6 9 3
1 4 5 6 9 3 8 2 7
采用列交换的方法转换矩阵
2 8 6 4 5 1 7 3 9
3 9 7 2 6 8 5 4 1
4 1 5 3 7 9 6 2 8
7 2 3 9 8 6 1 5 4
5 4 1 7 3 2 8 9 6
9 6 8 5 1 4 3 7 2
6 3 9 8 2 7 4 1 5
8 7 2 1 4 5 9 6 3
1 5 4 6 9 3 2 8 7
采用列交换的方法转换矩阵
2 3 4 7 5 9 6 8 1
8 9 1 2 4 6 3 7 5
6 7 5 3 1 8 9 2 4
4 2 3 9 7 5 8 1 6
5 6 7 8 3 1 2 4 9
1 8 9 6 2 4 7 5 3
7 5 6 1 8 3 4 9 2
3 4 2 5 9 7 1 6 8
9 1 8 4 6 2 5 3 7

下一篇博文将介绍随机法去产生数独终盘,从而增强数独终盘数据的随机性。

矩阵转换图参考自:
http://zhangroup.aporc.org/images/files/Paper_3485.pdf
  • 大小: 46.8 KB
  • 大小: 45.8 KB
  • 大小: 49.2 KB
  • 大小: 49.4 KB
  • 大小: 48.9 KB
2
1
分享到:
评论

相关推荐

    数独游戏终盘生成算法1

    1、常规回溯方法2、以宫为单位的矩阵置换法3、以数字顺序的以宫为单位的回溯法4、以某一数独为基础的数字替换法1、常规回溯方法这种方法是最容易想到的, 但是执行效

    数独游戏技巧:1~9九宫格数独口诀和解题技巧心得分享.doc

    数独游戏技巧:1~9九宫格数独口诀和解题技巧心得分享.doc

    简洁高效的数独矩阵生成器

    最近看别人玩数独游戏,了解了游戏规则后,编写了一个简洁高效的数独矩阵生成器,可任意设值矩阵阶数,算法简洁高效,欢迎大家下载

    java课程设计作业-基于java+swing构建的数独小游戏(源码+资源文件)

    java课程设计作业——基于java+swing构建的数独小游戏(源码+资源文件) 编程语言:java 界面绘制:swing IDE:MyEclipse,IDEA java课程设计作业——基于java+swing构建的数独小游戏(源码+资源文件) 编程语言...

    Windows数独游戏:Java FX实现

    几何数独游戏,微博[@屠龙的胭脂](https://weibo.com/1852299857?refer_flag=1001030103_)所介绍[几何数独游戏视频介绍](https://video.weibo.com/show?fid=1034:4737961351381034)同款。源码在:[蛇蛇数独游戏源...

    数独矩阵生成

    数独矩阵完成生成,显示,保存,功能,等功能,详情请见头文件内所有详细注释,当前版本不支持逆向计算,凡是正常生成的矩阵都是有具体参考,答案,由于可能根据你的设置不同,答案不唯一,但是会有个系统标准答案,...

    数独游戏,随机生成只有唯一解的数独表

    用c#写了一个能够随机生成唯一解的数独游戏,很多其他人的都不是随机生成,而且也不能保证生成的数独表的解是唯一的,所以我自己写了一个可以随机生成唯一解的数独游戏,上传上来和大家一起学习学习,看看算法还有...

    数独游戏答案生成器 真牛逼

    数独游戏终结者 不要再为数独游戏而纠结了 只要一输入 答案马上给出 当之无愧的数独游戏"终结者

    数独游戏(使用vc实现,含有自动求解答案模块)

    使用对话框创建数独游戏 主要含有以下模块:数独生成 数独判断 数独求解  数独生成方法:先填充一个完整的数独,再去掉若干个构成游戏初始界面  算法运行效率极高

    基于挖洞思想的数独游戏生成算法

    是08年的美国数学建模比赛一等奖,里面的是介绍了挖洞思想的数独生成游戏算法。

    数独自动生成题库

    学习了Mars老师的数独游戏教程,奈何题库太单调,于是查找资料,增加了难度选择自动生成题库功能,游戏胜利后会弹框提示

    数独九宫格,excel自动生成版

    excel为数独9宫格自动生成版本。下载excel后,打开下方的sheet1,即为九宫格题目,复制到word内打印即可。 详细说明: 1.更改sheet2内的A1单元格内的数字(范围1-9),可以调节数独的难度,1难度最低,9难度最高,...

    简单数独游戏,能够自动生成4*4的数独

    VS环境下C++数独游戏

    数独随机矩阵生成

    找了半天没找到,就自己写了,一般迭代个100次就完了

    数独游戏1.2.1(游戏独立运行版)

    如果选择题目模板,在指定录入矩阵模式后,输入81个数值,0为隐藏,非0数值为显示,根据输入重新生成当前数独,指定题目,同模板,但是会检查题目是否符合要求,指定完整数独,同题目,但是会检查不应该有0值,如果...

    微信小程序 小游戏类 数独小游戏 (源代码+截图)

    微信小程序 小游戏类 数独小游戏 (源代码+截图)微信小程序 小游戏类 数独小游戏 (源代码+截图)微信小程序 小游戏类 数独小游戏 (源代码+截图)微信小程序 小游戏类 数独小游戏 (源代码+截图)微信小程序 小...

    Python数独游戏源代码

    Python数独游戏源代码、源程序共包括两个程序文件:main.py及build.py

    JAVA 数独游戏代码

    JAVA的数独游戏代码,随机生成数独,如果有三个难度可选

    C# PC版做的 数独游戏

    介绍:用C#开发的数独游戏 核心:核心代码是从网上借鉴来的, 价值:仅供娱乐和学习参考。 用途:大家开心就好

Global site tag (gtag.js) - Google Analytics