Java 中的数独游戏

• 下载 Netbeans 项目 - 36.8 KB
• 下载源代码 - 8.9 KB

引言

本文介绍了用 Java 实现数独游戏。此版本包含一个直观的界面，能够使用提示并检查错误。开启提示将标记所选数字的所有可能位置。检查错误后，程序将用绿色标记有效位置，用红色标记无效位置。此实现中使用的规则如下：

• 整数只能在一个 ...
• ... 同一行中出现一次。
• ... 同一列中出现一次。
• ... 同一 3x3 区域中出现一次。
• 一个游戏只有一个解决方案。

实现

模型

此应用程序最重要的部分是 Game 类，它包含以下功能：

• 生成新解决方案；
• 根据解决方案生成新游戏；
• 跟踪用户输入；
• 将用户输入与生成的解决方案进行比较；
• 跟踪选定的数字；
• 跟踪提示的开启或关闭状态。

由于 Game 类扩展了 Observable，它可以并且确实会在执行某些更改时通知观察者。此应用程序包含两个观察者：ButtonPanel 和 SudokuPanel。当 Game 类执行 setChanged() 后跟 notifyObservers(...) 时，观察者将执行它们的 update(...) 方法。

除了 Game 类之外，模型还包含一个名为 UpdateAction 的枚举，它会告诉观察者发生了哪种类型的更新。

生成解决方案

在我们开始生成游戏之前，我们必须先生成一个解决方案。这是通过下面的方法实现的，需要用户像这样调用：generateSudoku(new int[9][9], 0)。将采取以下步骤：

1. 检查是否找到解决方案。
• 找到 -> 返回解决方案。
• 未找到 -> 继续。
2. 使用模运算，通过当前索引除以一行中的字段数取余来找到 X（当前字段）。
3. 通过将当前索引除以一行中的字段数来找到 Y（当前字段）。
4. 将数字 1 到 9 填入一个 ArrayList 并进行洗牌。洗牌很重要，否则你总是会得到相同的解决方案。
5. 只要 ArrayList 中还有数字，就会执行以下操作：
1. 通过 getNextPossibleNumber(int[][], int, int, List<Integer>) 方法获取下一个可能的数字，稍后将对其进行解释。如果没有下一个可能的数字（返回值为 -1），则返回 null。
2. 找到的数字被放置在当前位置。
3. 该方法被递归调用，索引增加，返回的值存储在一个变量中。
4. 如果此变量不是 null，则返回它；否则，当前位置被重置为 0（表示该字段为空）。
6. 返回 null。希望这部分永远不会被触及。

private int[][] generateSolution(int[][] game, int index) {
    if (index > 80)
        return game;

    int x = index % 9;
    int y = index / 9;

    List<Integer> numbers = new ArrayList<Integer>();
    for (int i = 1; i <= 9; i++)
        numbers.add(i);
    Collections.shuffle(numbers);

    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;
}

如前所述，getNextPossibleNumber(int[][], int, int, List<Integer>) 方法用于获取下一个可能的数字。它从列表中取出一个数字，并检查它是否可以放置在给定游戏中的给定 x 和 y 位置。如果找到可能的位置，则返回该数字。如果列表为空，因此在此位置没有可能的数字，则返回 -1。

private int getNextPossibleNumber(int[][] game, int x, int y, List<Integer> numbers) {
    while (numbers.size() > 0) {
        int number = numbers.remove(0);
        if (isPossibleX(game, y, number)
                && isPossibleY(game, x, number)
                && isPossibleBlock(game, x, y, number))
            return number;
    }
    return -1;
}

生成游戏

生成游戏只需不断移除一个随机字段并确保游戏仍然有效。有效意味着只有一个解决方案。这是通过以下方法实现的。用户应该调用第一个方法，该方法使用第二个方法。我将再次描述这些步骤：

1. 将所有可能的位置填入一个列表。
2. 列表被洗牌。我不知道为什么。我怀疑这样可以更好地分布空白。结果是游戏更难。
3. 列表被传递给 generateGame(int[][], List<Integer>) 方法，并返回其返回值。

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);
}

1. 只要列表中还有位置，就会执行以下操作：
1. 从列表中取出一个位置并存储在一个变量中。
2. 从该位置计算 x 和 y。
3. 该位置的值存储在变量 temp 中。
4. 该位置的值设置为 0（表示该字段为空）。
5. 这一步至关重要。由于移除了该位置的值意味着游戏不再有效，因此将该值放回。否则游戏保持不变。
2. 返回游戏。

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;
}

正如你所见，此方法用于传递默认值。那么为什么是 new int[] { 0 } 呢？这是通过引用而不是通过值传递整数的最常见方式。

private boolean isValid(int[][] game) {
    return isValid(game, 0, new int[] { 0 });
}

一个有效的游戏在每一行、每一列和每一个区域中都包含数字 1 到 9。此外，应该只有一个解决方案。为此，所有空字段都用第一个有效值填充。即使找到一个解决方案，搜索也会通过在空字段中放置下一个有效值来继续。如果找到第二个解决方案，则停止搜索，并且该方法返回 false。将始终至少有一个解决方案（因此 game 是一个不完整的解决方案），如果解决方案少于两个，则游戏有效，并且该方法返回 true。分步说明：

1. 检查是否找到解决方案。
• 找到 -> 增加 numberOfSolutions，如果等于 1 则返回 true；否则返回 false。
• 未找到 -> 继续。
2. 从索引计算 x 和 y。
3. 检查当前字段是否为空（等于 0）。
• True
1. 用数字 1 到 9 填充列表。
2. 当列表包含数字时，执行以下操作：
1. 获取下一个可能的数字。如果返回值为 -1，则执行 break，导致返回 true。
2. 将此数字设置在当前字段。
3. 递归调用此方法并立即检查返回的值。
• True -> 找到一个或零个解决方案，继续搜索。
• False -> 找到一个以上解决方案，停止搜索。恢复游戏并返回 false。
4. 将当前字段的值恢复为 0（表示它是空白）。
• 假
1. 递归调用此方法并立即检查返回的值。
• True -> 继续（导致返回 true）。
• False -> 返回 false。
4. 返回 true。

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;
}

检查游戏

在检查用户输入时，我们将游戏中的每个字段与解决方案中的相应字段进行比较。结果存储在一个二维布尔数组中。选定的数字也设置为 0（表示没有选定数字）。所有观察者都会收到模型已更改的通知，并附带相应的 UpdateAction。

public void checkGame() {
    selectedNumber = 0;
    for (int y = 0; y < 9; y++) {
        for (int x = 0; x < 9; x++)
            check[y][x] = game[y][x] == solution[y][x];
    }
    setChanged();
    notifyObservers(UpdateAction.CHECK);
}

视图和控制器

关于视图部分没有太多可说的，只有面板的结构。控制器响应用户输入并对模型进行更改。模型通知其已更改。视图响应此通知并进行更新。这些视图更新仅限于更改颜色和更改字段的数字。没有什么高深的东西。

数独

视图也是此应用程序的入口点；Sudoku 类包含 main 方法。此类通过创建 JFrame 并将 SudokuPanel 和 ButtonPanel 放置在该框架内来构建用户界面。它还创建 Game 类，并将 SudokuPanel 和 ButtonPanel 添加为它的观察者。

SudokuPanel 和字段

SudokuPanel 包含 9 个子面板，每个子面板包含 9 个字段。所有子面板和字段都放置在 3x3 的 GridLayout 中。每个子面板代表数独游戏的一个区域，主要用于绘制边框以在视觉上分隔每个区域。它们还添加了 SudokuController，负责通过鼠标处理用户输入。

ButtonPanel

ButtonPanel 包含两个带有标题边框的面板。第一个面板包含三个按钮。New 按钮用于开始新游戏，Check 按钮用于检查用户输入，Exit 按钮用于退出应用程序。第二个面板包含放置在按钮组内的 9 个切换按钮。这样，它们的反应就像单选按钮一样。单击这些切换按钮之一将设置 Game 类中相应的选定数字。

关注点

• 要通过引用而不是通过值传递整数，请使用整数数组。

isValid(game, 0, new int[] { 0 });
private boolean isValid(int[][] game, int index, int[] numberOfSolutions);

• 要查找区域的基本 x 和 y 值，请使用以下方法：

int x1 = x < 3 ? 0 : x < 6 ? 3 : 6;
int y1 = y < 3 ? 0 : y < 6 ? 3 : 6;

历史

• 初始发布。

抱歉

一、如果我的蹩脚英语让你抓狂，我道歉。二、如果你以前让我抓狂，因为通常我的源代码不包含注释，我道歉，我可以告诉你，这次包含。不是因为我承认它们的有用性，而是为了避免争论。三、如果我之前没有提到你可以用鼠标右键清除字段，我道歉。