`
MouseLearnJava
  • 浏览: 465993 次
  • 性别: 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

    数独游戏终盘生成算法是计算机科学中一种有趣的算法应用,主要目的是生成具有唯一解决方案的数独谜题。本文将探讨四种不同的数独终盘生成方法,并以代码示例展示其中的一种。 首先,数独是一种逻辑游戏,由9x9的...

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

    在这个场景中,我们讨论的是一个简洁高效的数独矩阵生成器,该生成器是用C++编程语言编写的,能够根据用户的需求生成不同阶数的数独矩阵。 首先,我们来看数独矩阵生成器的核心算法。生成数独矩阵通常涉及两个主要...

    数独随机矩阵生成

    数独是一种广受欢迎的逻辑推理游戏,它基于一个9x9的网格,被分为9个小的3x3的宫格。每个宫格、行和列都必须填入1到9的数字,且每个数字在各自的宫格、行和列中只能出现一次。"数独随机矩阵生成"是指创建符合数独...

    数独游戏矩阵设计实现1

    数独游戏矩阵设计实现1是指通过算法生成一个合法的数独矩阵。数独矩阵是一个9x9的二维数组,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1...

    数独游戏---自写算法。随即生成数独

    数独是一种广受欢迎的逻辑推理游戏,它基于9x9的格子,分为9个3x3的小宫格。每个小宫格内均分布有1到9的数字,玩家的目标是根据已给出的部分数字,推理出剩余空白格子应有的数字,使得每一行、每一列以及每一个小...

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

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

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

    综上所述,基于“挖洞思想”的数独游戏生成算法是一种创新的方法,它从一个完整的数独谜题出发,通过特定的规则删除一些数字,从而得到一个有唯一解的数独谜题。这项算法的提出者为薛源海、蒋彪彬和李永卓,他们来自...

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

    “数独游戏答案生成器”是一款专为数独爱好者设计的工具,它的功能强大,能够帮助玩家快速找到数独游戏的答案。这款生成器的出现,无疑为那些在数独题目面前感到困惑或者想要验证自己解答正确性的玩家提供了极大的...

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

    数独是一种逻辑推理游戏,源于18世纪末的瑞士,后在美国流行并由日本推广开来。游戏基于一个9x9的九宫格,被划分为9个小的3x3宫格。玩家需根据已给定的数字,用1到9的数字填充空格,使得每一行、每一列和每一个小...

    数独自动生成题库

    数独是一种广受欢迎的逻辑推理游戏,它源自19世纪末的瑞士,由美国的Howard Garns在1979年发扬光大,并在20世纪90年代末通过日本的《Number Place》杂志传遍全球。数独游戏的目标是在9×9的网格中填入1到9的数字,...

    数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏.rar

    数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏数独游戏...

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

    数独是一种广受欢迎的逻辑推理游戏,它基于9x9的格子,分为9个3x3的小宫格。每个小宫格内填入数字1到9,使得每一行、每一列以及每一个小宫格内的数字都只出现一次。在这个案例中,我们讨论的是一个简化版的4x4数独,...

    100个数独(Python语言生成)

    数独是一种广受欢迎的逻辑游戏,它通过填充1到9的数字到9x9的九宫格中,使得每一行、每一列以及每个3x3的小宫格内都包含这9个数字,且每个数字在各自的行、列和小宫格内只出现一次。这个项目“100个数独(Python语言...

    Windows数独游戏:Java FX实现

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

    Python数独游戏源代码

    Python数独游戏是一种基于Python编程语言开发的桌面应用程序,它利用了Python的灵活性和易读性,为用户提供了一个交互式的数独游戏体验。这个压缩包包含的文件是"main.py"和"build.py",它们构成了游戏的核心部分。 ...

    数独的难度衡量、生成及微粒群算法(张艳宗)

    **数独生成**:为了生成具有特定难度级别的数独谜题,研究者开发了一种基于数独终盘的生成方法。这种方法首先生成一个完整的数独终盘,然后通过删除某些已知数字来形成谜题。在删除过程中,算法确保剩余的谜题只有一...

    java数独生成算法及基于此算法的android数独游戏APK

    数独是一种广受欢迎的逻辑推理游戏,它基于9x9的格子,分为9个3x3的小九宫格。每个格子可以填写1到9的数字,目标是使得每行、每列以及每个小九宫格内的数字都恰好出现且仅出现一次。在本项目中,我们将探讨Java实现...

    java编写的 数独游戏

    这部分代码是一个完整的Java程序,它首先提示用户输入数独矩阵的大小(这个数必须是奇数),然后生成并填充数独矩阵,最后输出生成的数独矩阵。 从标签“数独游戏”来看,我们关注的知识点主要是如何用编程语言实现...

    数独矩阵生成

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

Global site tag (gtag.js) - Google Analytics