Java数独游戏（译文）

原文地址：https://www.codeproject.com/Articles/90885/Sudoku-Game-in-Java

原文作者：Eric Beijer

译文由本站 robot-v1.0 翻译

前言

A Sudoku game written in Java which generates its own games on the fly.

用Java编写的Sudoku游戏,可以即时生成自己的游戏.

• 下载Netbeans项目-36.8 KB(Download Netbeans project - 36.8 KB)
• 下载源8.9 KB(Download source - 8.9 KB)

介绍(Introduction)

本文介绍了Java中Sudoku游戏的实现.该版本包括一个直观的界面,可以使用帮助和检查错误.打开帮助将标记所选号码的所有可能字段.检查错误后,程序将有效字段标记为绿色,将无效字段标记为红色.此实现中使用的规则如下:(This article is on the implementation of a Sudoku game in Java. This version includes an intuitive interface with the ability to use help and to check for errors. Turning on help will mark all possible fields for the selected number. After checking for errors, the program marks valid fields green and invalid fields red. The rules used in this implementation are as follows:)

• 整数只能在…中出现一次(An integer may only appear once in …)

  • …同一行.(… the same row.)
  • …同一列.(… the same column.)
  • …相同的3x3区域.(… the same 3x3 region.)

• 一个游戏只有一个解决方案.(A game has only one solution.)

实作(Implementation)

模型(Model)

此应用程序最重要的部分是(The most important part of this application is in the) Game 类,其中包括以下功能:(class, which includes the following functionality:)

• 产生新的解决方案;(Generate a new solution;)
• 从解决方案中生成新游戏;(Generate a new game from a solution;)
• 跟踪用户输入;(Keep track of user input;)
• 根据生成的解决方案检查用户输入;(Check user input against generated solution;)
• 跟踪所选号码;(Keep track of selected number;)
• 跟踪帮助的开启或关闭.(Keep track of help is on or off.) 因为(Because the) Game 类扩展(class extends) Observable ,它可以并且确实会在执行某些更改时通知观察者.这个特定的应用程序包含两个观察者,(, it can and does notify observers when certain changes have been performed. This particular application contains two observers,) ButtonPanel 和(and) SudokuPanel .当…的时候(. When the) Game 类执行(class executes) setChanged() 其次是(followed by) notifyObservers(...) ,观察员将执行他们的(, the observers will execute their) update(...) 方法.(method.) 除了(Besides the) Game 类,该模型包含一个称为(class, the model consists of an enumeration called) UpdateAction 它将告诉观察者发生了什么样的更新.(which will tell observers what kind of update has taken place.)

产生解决方案(Generate Solution)

在开始生成游戏之前,我们必须首先生成解决方案.这是通过以下方法实现的,用户需要将其称为(Before we can start generating a game, we must first generate a solution. This is achieved by the method below, which needs to be called by the user as) generateSudoku(new int[9][9], 0) .采取以下步骤:(. The following steps are taken:)

• 检查是否找到解决方案.(Check if a solution is found.)

  • 找到->返回解决方案.(Found -> solution is returned.)
  • 找不到->继续.(Not found -> continue.)

• X(当前字段的)是通过使用模运算找到当前索引除以行中字段数得出的余数而得出的.(X (of current field) is found by finding the remainder of the division of the current index by the count of fields in a row using the modulo operation.)

• 通过将当前索引除以一行中的字段数,可以找到(当前字段的)Y.(Y (of current field) is found by dividing the current index by the count of fields in a row.)

• 一个(An) ArrayList 由数字1到9填充并随机播放.改组很重要,因为否则您总是会得到相同的解决方案.(is filled with the numbers 1 to 9 and shuffled. Shuffling is important because otherwise you always get the same solution.)

• 只要有数字(As long as there are numbers in the) ArrayList ,将执行以下操作:(, the following will be executed:)

  • 通过该方法获得下一个可能的数字(The next possible number is obtained by the method) getNextPossibleNumber(int[][], int, int, List<Integer>) ,稍后将对此进行说明.如果没有下一个可能的数字(返回值为-1),(, which will be explained later on. If there’s no next possible number (return value of -1),) null 返回.(is returned.)
  • 找到的号码被放置在当前位置.(Found number is placed on the current location.)
  • 随着索引的增加而递归调用该方法,并将返回值存储在变量中.(The method is recursively called with an increase of the index, and the returning value is stored in a variable.)
  • 如果这个变量不是(If this variable is not) null ,它被返回;否则,将当前位置放回0(表示该字段为空白).(, it is returned; otherwise, the current location is put back to 0 (meaning the field is a blank).)

• null 返回.希望这一部分永远不会实现.(is returned. This part will never be reached, hopefully.)

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

如前所述,该方法(As previously said, the method) getNextPossibleNumber(int[][], int, int, List<Integer>) 用于获取下一个可能的数字.它从列表中获取一个数字,并检查在给定游戏中给定的x和y位置是否可能.如果可能,则返回该数字.如果列表为空,因此此位置没有数字,则返回-1.(is used for obtaining the next possible number. It takes a number from the list and checks whether it is possible at the given x and y position in the given game. When found possible, the number is returned. If the list is empty and thus no number is possible at this location, -1 is returned.)

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

产生游戏(Generate Game)

只需不断移除随机字段并确保游戏仍然有效,即可轻松生成游戏.有效表示只有一种解决方案.这可以通过以下方法实现.用户应调用第一种方法,该方法使用第二种方法.我将再次描述这些步骤.(Generating a game is simply achieved by constantly removing a random field and making sure the game is still valid. Valid means there is only one solution. This is achieved by the methods below. The user should call the first method, which uses the second method. I will describe the steps again.)

• 列表中列出了所有可能的职位.(A list is filled with all possible positions.)
• 列表被拖曳了.我不知道为什么.我怀疑这样可以更好地分配空白.结果,游戏变得更加困难.(The list is shuffled. I do not know why. I suspect that this way, the blanks are better distributed. With the result that the game is harder.)
• 列表被传递给方法(The list is passed to the method) generateGame(int[][], List<Integer>) 返回值将被返回.(and the return value will be returned.)

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

• 只要列表中有职位,就会执行以下操作:(As long as there are positions in the list, the following will be executed:)

  • 从列表中获取一个职位,并将其存储在变量中.(A position is taken from the list and stored in a variable.)
  • x和y从该位置计算.(x and y are calculated from this position.)
  • 此位置的值存储在变量中(Value at this position is stored in the variable) temp .(.)
  • 此位置的值设置为0(表示该字段为空白).(Value at this position is set to 0 (meaning the field is a blank).)
  • 此步骤至关重要.由于移除位置上的值意味着游戏不再有效,因此将位置上的值放回原处.否则,游戏将保持不变.(This step is critical. As the removal of the value at the position means that the game is no longer valid, the value at the position is put back. Otherwise the game stays the same.)

• 游戏被退回.(The game is returned.)

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

如您所见,此方法用于传递默认值.那为什么(As you can see, this method is used to pass default values. So why the) new int[] { 0 } ？这是通过引用而不是通过值传递整数的最常见方法.(? This is the most common way of passing an integer by reference, instead of by value.)

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

一个有效的游戏在每一行,每一列以及每个区域中都有1到9的数字.此外,应该只存在一个解决方案.为此,所有打开的字段均填充有第一个有效值.即使找到了解决方案,搜索也会通过将下一个有效值放在一个开放字段中来继续进行.如果找到第二个解决方案,则搜索将停止并且该方法返回(A valid game has in every row, every column, and every region the numbers 1 to 9. Additionally, there should only be one solution existing. To achieve this, all open fields are filled with the first valid value. Even after finding a solution, the search continues by putting the next valid value in an open field. If a second solution is found, then the search will be stopped and the method returns) false .总会有至少一种解决方案(因此(. There will always be at least one solution (hence) game 是一个不完整的解决方案),因此,如果解决方案少于两个,则该游戏有效且该方法返回(is an incomplete solution), so if there are less than two solutions, the game is valid and the method returns) true .一步步:(. Step by step:)

• 检查是否找到解决方案.(Check if a solution is found.)

  • 找到->增加(Found -> increase) numberOfSolutions 然后返回(and return) true 如果等于1;(if it equals 1;) false 除此以外.(otherwise.)
  • 找不到->继续.(Not found -> continue.)

• 根据索引计算x和y.(Calculate x and y from index.)

• 检查当前字段是否为空白(等于0).(Check if current field is a blank (equals 0).)

  • 真正(True)

    • 用数字1到9填充列表.(Fill a list with numbers 1 to 9.)

    • 当列表包含数字时,执行以下操作:(While the list contains numbers, execute the following:)

      • 获取下一个可能的号码.如果返回值等于-1,则执行中断,返回.(Get the next possible number. If the returned value equals -1, perform a break resulting a return of) true .(.)

      • 在当前字段设置此数字.(Set this number at current field.)

      • 递归调用此方法,并立即检查返回的值.(Call this method recursively and instantly check against the returned value.)

        • 正确->未找到任何解决方案,请继续搜索.(True -> one or no solution found, continue search.)
        • 错误->找到多个解决方案,请停止搜索.恢复游戏并返回(False -> more than one solution found, stop searching. Restore game and return) false .(.)

      • 将当前字段的值恢复为0(表示空白).(Restore value of current field to 0 (meaning it is blank).)

  • 假(False)

    • 递归调用此方法,并立即检查返回的值.(Call this method recursively and instantly check against the returned value.)

      • 正确->继续(导致返回(True -> continue (resulting in returning) true ).().)
      • 假->返回(False -> return) false .(.)

• 返回(Return) 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;
}

检查游戏(Check Game)

通过检查用户输入,我们将游戏中的每个字段与解决方案中的相应字段进行比较.结果存储在二维布尔数组中.所选数字也设置为0(表示未选择任何数字).通知所有观察者模型已更改,相应的(With checking user input, we compare each field in the game against the corresponding field in the solution. The result is stored in a two dimensional boolean array. The selected number is also set to 0 (meaning no number is selected). All observers are notified that the model has changed with the corresponding) 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);
}

视图和控制器(View & Controller)

关于视图部分,没有太多要说的,只是面板的结构.控制器对用户输入做出反应,并对模型进行更改.模型通知它已更改.视图对此通知和更新做出响应.视图的这些更新仅限于更改颜色和更改字段数.没有涉及火箭科学.(There is not much to say about the view part, only the structure of the panels. The controllers react to user input and implement changes to the model. The model notifies it has been changed. The view responses to this notification and updates. These updates of the view are limited to changing colors and changing the number of a field. There is no rocket science involved.)

数独(Sudoku)

该视图也是该应用程序的切入点.的(The view also is the entry point of this application; the) Sudoku 类包含主要方法.此类通过创建一个(class contains the main method. This class builds up the user interface by creating a) JFrame 和放置(and placing) SudokuPanel 和(and) ButtonPanel 在这个框架内.它还会创建(inside this frame. It also creates the) Game 类,并添加(class, and adds) SudokuPanel 和(and) ButtonPanel 作为它的观察者.(as observers to it.)

Sudoku面板和字段(SudokuPanel and Fields)

SudokuPanel 包含9个子面板,每个子面板包含9个字段.所有子面板和字段都放置在(contains 9 sub panels each containing 9 fields. All sub panels and fields are placed in a) GridLayout 3x3.每个子面板代表Sudoku游戏的一个区域,主要用于绘制在视觉上分隔每个区域的边框.他们也得到了(of 3x3. Each sub panel represents a region of a Sudoku game, and is primarily used for drawing a border visually separating each region. They also get the) SudokuController 添加到他们,负责处理鼠标的用户输入.(added to them, which is in charge of processing user input by mouse.)

按钮面板(ButtonPanel)

ButtonPanel 包含两个带有标题边框的面板.第一个面板包含三个按钮.按钮New用于启动新游戏,按钮Check用于检查用户输入,按钮Exit用于退出应用程序.第二个面板包含放置在按钮组内的9个切换按钮.这样,它们就像单选按钮一样反应.单击这些切换按钮之一将在(contains two panels with a titled border. The first panel contains three buttons. Button New for starting a new game, button Check for checking user input, and button Exit for exiting the application. The second panel contains 9 toggle buttons placed inside a button group. This way, they react like radio buttons. Clicking one of these toggle buttons will set the corresponding selected number in the) Game 类.(class.)

兴趣点(Points of Interest)

• 要通过引用而不是通过值传递整数,请使用整数数组.(For passing an integer by reference instead of by value, use an integer array.)
• 查找区域的基本x和y值,请使用以下命令:(Finding the base x and y values of a region, use the following:)

历史(History)

• 初始发行.(Initial release.)

道歉(Apologies)

第一,如果我让您因我的英语不好而生气,我深表歉意.第二,如果以前因为我的消息源通常不包含评论而使您发疯,我对此表示歉意,在这种情况下,我可以告诉您.不是因为我承认它们的用处,而是为了避免讨论.第三,很抱歉,如果我之前没有提到您可以使用鼠标右键清除字段.(One, if I have driven you mad with my bad English, I apologize. Two, if I have driven you mad before because usually my source doesn’t contain comments, I apologize, and I can tell you, in this case, it does. Not because I acknowledge their usefulness, but to avoid discussions. Three, if I didn’t mention before that you can use your right mouse button to clear a field, I apologize.)

许可

本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。