首页 > 代码库 > Java从基础到进阶学习之路----数独小游戏制作(二)
Java从基础到进阶学习之路----数独小游戏制作(二)
详细设计
游戏数据结构设计
显然,需要存储数据的地方只有九宫格地图部分。
对于地图,很明显我们可以采用二维数组int [] [] game;来存储地图中的数据。但是int的二维数组虽然直接简单,但是还是有一定不便之处,比如没有集合的内置处理方法丰富。所以,显然,在游戏地图的生成过程中,一些辅助数据我们可以采用Java的集合。
地图生成算法
对于数独而言,游戏的成功的最根本的保证就是当前的地图有一个存在的解。这就像是解方程,如果不存在解,那么这个游戏本身就是失败的。
所以,重点在于如何产生一个存在解且解唯一的地图。如果我们仅仅是随机产生数字,显然是不可以的,虽然在我们看来,地图上的这些数字确实像是随机产生的:每次出现的位置不定,大小不一样。
不过,随机产生不能保证游戏的结果一定有解!
那么我们要如何产生一个可以玩的地图呢?
这就需要我们逆向思考一下,既然前提是要有一个可行解,那么我们就直接产生一个解,称之为终盘,然后将这些解的数字随机剔除,形成初盘,剩下的显示在地图上不就ok了么?
那么又有一个新的问题出现了,我们要如何产生一个可行解?
首先我们要明确对可行解的要求:
- 解必须要符合游戏规则
- 每次生成的解都是不一样的
- 解唯一
有了这两个要求我们就有了目标。
首先考虑的是如何产生符合游戏规则的解?游戏规则是:
- 每一行不可以出现重复的数字
- 每一列不可以出现重复的数字
- 每个小宫格区(3X3)内不可以出现重复的数字
其实做过ACM题目的应该都可以看出来这就是一个简单的ACM题目了。
即是:现在给定义一个九宫格,让你在符合九宫格规则的情况下,随机生成一个九宫格的完整的终盘地图。
做题比较有经验的人,显然一眼就可以出来,这道题目,显然用搜索做最适合。
我则采用了dfs,深度优先搜索进行处理。过程如下,首先现在我们将宫格的坐标定义如下:
共有9*9=81格,因此可以定义一个变量index,使其从0开始直至80,将其整除9等到行坐标,对9取余得到列坐标。即是:
X = index / 9
Y = index % 9
dfs的代码如下所示:/** * Generates Sudoku game solution. * * @param game Game to fill, user should pass 'new int[9][9]'. * @param index Current index, user should pass 0. * @return Sudoku game solution. */ private int[][] generateSolution(int[][] game, int index) { if (index > 80) return game; // 获取坐标 int x = index % 9; int y = index / 9; // 产生1-9的数字的ArrayList,并打乱顺序 List<Integer> numbers = new ArrayList<Integer>(); for (int i = 1; i <= 9; i++) numbers.add(i); Collections.shuffle(numbers); // 打乱list顺序 // 尝试确定该坐标的数字值 while (numbers.size() > 0) { int number = getNextPossibleNumber(game, x, y, numbers); // 获取该坐标的可能值 if (number == -1) return null; game[y][x] = number; int[][] tmpGame = generateSolution(game, index + 1); // 递归调用,下一个可能值 if (tmpGame != null) return tmpGame; game[y][x] = 0; } return null; }
即是,从左到右,从上到下,一个坐标一个坐标的数字的确定,之所是尝试获取可能值,是因为,在这种逐步搜索确定的情况下,可能会在某个坐标的值存在无解,即是该坐标不能填入任何数字,否则就违反了规则,这个时候,就会递归出栈,返回到上一个坐标,并将之前无解的坐标的值置为0,重新确定上一个坐标的其他可能的值(即除去上一个已经取了的值),如果也是无解,则继续出栈,再回到更上的一个坐标,重新确定,如果有其他可取值,则从这个坐标开始再次递归搜索。这样直至成功搜索完整张地图结束。
上面的只是终盘的生成算法,那么如何生成初盘呢?
我们上面说了,采取在终盘上剔除数字,这个也可以形象的说是“挖洞”,即是在终盘上随机挖洞,挖洞的规则是:
挖去一个洞,然后判断当前的盘面的解是否存在且唯一,如果不唯一,则终止挖洞。否则可以继续挖洞,直至满足要求。
实现代码如下:
private int[][] generateGame(int[][] game) { List<Integer> positions = new ArrayList<Integer>(); for (int i = 0; i < 81; i++) positions.add(i); Collections.shuffle(positions); return generateGame(game, positions); } /** * Generates Sudoku game from solution, user should use the other * generateGame method. This method simple removes a number at a position. * If the game isn't anymore valid after this action, the game will be * brought back to previous state. * * @param game Game to be generated. * @param positions List of remaining positions to clear. * @return Generated Sudoku game. */ private int[][] generateGame(int[][] game, List<Integer> positions) { while (positions.size() > 0) { int position = positions.remove(0); int x = position % 9; int y = position / 9; int temp = game[y][x]; game[y][x] = 0; if (!isValid(game)) game[y][x] = temp; } return game; } /** * Checks whether given game is valid. * * @param game Game to check. * @return True if game is valid, false otherwise. */ private boolean isValid(int[][] game) { return isValid(game, 0, new int[] { 0 }); } /** * Checks whether given game is valid, user should use the other isValid * method. There may only be one solution. * * @param game Game to check. * @param index Current index to check. * @param numberOfSolutions Number of found solutions. Int[] instead of * int because of pass by reference. * @return True if game is valid, false otherwise. */ private boolean isValid(int[][] game, int index, int[] numberOfSolutions) { if (index > 80) return ++numberOfSolutions[0] == 1; int x = index % 9; int y = index / 9; if (game[y][x] == 0) { List<Integer> numbers = new ArrayList<Integer>(); for (int i = 1; i <= 9; i++) numbers.add(i); while (numbers.size() > 0) { int number = getNextPossibleNumber(game, x, y, numbers); if (number == -1) break; game[y][x] = number; if (!isValid(game, index + 1, numberOfSolutions)) { game[y][x] = 0; return false; } game[y][x] = 0; } } else if (!isValid(game, index + 1, numberOfSolutions)) return false; return true; }
暂时先说这个算法吧,不是很好理解的。具体基于“挖洞”的初盘生成算法可以搜索相关的文档加以理解。
Reference:
数独之谜
http://www.shs.edu.tw/works/essay/2008/10/2008103010094624.pdf
数独生成方法的讨论
http://www.sudoku.org.tw/phpBB/viewtopic.php?f=6&t=36
关于挖洞的文献
http://wenku.baidu.com/view/f9e3f17101f69e31433294e1.html
Java从基础到进阶学习之路----数独小游戏制作(二)