详细设计

游戏数据结构设计

显然，需要存储数据的地方只有九宫格地图部分。

对于地图，很明显我们可以采用二维数组int [] [] game;来存储地图中的数据。但是int的二维数组虽然直接简单，但是还是有一定不便之处，比如没有集合的内置处理方法丰富。所以，显然，在游戏地图的生成过程中，一些辅助数据我们可以采用Java的集合。

地图生成算法

对于数独而言，游戏的成功的最根本的保证就是当前的地图有一个存在的解。这就像是解方程，如果不存在解，那么这个游戏本身就是失败的。

所以，重点在于如何产生一个存在解且解唯一的地图。如果我们仅仅是随机产生数字，显然是不可以的，虽然在我们看来，地图上的这些数字确实像是随机产生的：每次出现的位置不定，大小不一样。

不过，随机产生不能保证游戏的结果一定有解！

那么我们要如何产生一个可以玩的地图呢？

这就需要我们逆向思考一下，既然前提是要有一个可行解，那么我们就直接产生一个解，称之为终盘，然后将这些解的数字随机剔除，形成初盘，剩下的显示在地图上不就ok了么？

那么又有一个新的问题出现了，我们要如何产生一个可行解？

首先我们要明确对可行解的要求：

• 解必须要符合游戏规则
• 每次生成的解都是不一样的
• 解唯一
  

有了这两个要求我们就有了目标。

首先考虑的是如何产生符合游戏规则的解？游戏规则是：

• 每一行不可以出现重复的数字
• 每一列不可以出现重复的数字
• 每个小宫格区（3X3）内不可以出现重复的数字

其实做过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