首页 > 代码库 > 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从基础到进阶学习之路----数独小游戏制作(二)