数独之谜第1部分:数独类

Question

最近我有一个数独难题要解决，自从我开始解决许多数独谜题后，我决定尝试创建一个数独难题查看器与JavaFX。我还没有完成，但已经决定把它分成几个部分，以便更容易解决未来的问题。第1部分是Sudoku类。Sudoku类做：

• 表示一个法定的(“每行、每列和每框只能包含1-9中的每一个数字一次”) Sudoku难题。
• 允许检查和编辑方块，只要谜题仍然合法。
• 可以得到一个随机的拼图(可以更改为生成拼图)

守则如下：

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Random;

public class Sudoku {

    public static final int SUDOKU_SIZE = 9;
    public static final int SUDOKU_SQUARE_SIZE = 3;

    private static final int ROW_TEST = 0;
    private static final int COL_TEST = 1;
    private static final int SQ3_TEST = 2;

    private static final int NUM_OF_PUZZLES = 1;

    private final int[][] puzzle;

    private static final Random random = new Random();

    /**
     * Creates a new Sudoku Puzzle from a 9x9 board. If array is larger than
     * 9x9, then it will ignore the elements out of range. Note that it will
     * still take puzzles that are unsolvable or solved, but will throw an
     * {@link java.lang.IllegalArgumentException IllegalArgumentException} if
     * the puzzle is illegal. The puzzle is illegal if it does not follow the
     * standard Sudoku rules: "Each row, column, and box may only contain one of
     * each number from 1-9."
     * 
     * @param board
     *            the board to copy from
     */
    public Sudoku(int[][] puzzle) {
        checkBoard(puzzle);
        this.puzzle = Arrays.copyOf(puzzle, SUDOKU_SIZE);
        for (int i = 0; i < SUDOKU_SIZE; i++) {
            this.puzzle[i] = Arrays.copyOf(puzzle[i], SUDOKU_SIZE);
        }
    }

    private void checkBoard(int[][] puzzle) {
        boolean[] alreadyHasNumber = new boolean[SUDOKU_SIZE];
        for (int i = ROW_TEST; i <= SQ3_TEST; i++) {
            for (int j = 0; j < SUDOKU_SIZE; j++) {
                for (int k = 0; k < SUDOKU_SIZE; k++) {
                    int num = getNumFromTest(puzzle, i, j, k);
                    if (num != -1) {
                        if (!alreadyHasNumber[num]) {
                            alreadyHasNumber[num] = true;
                        } else {
                            throw new IllegalArgumentException(
                                    "Puzzle is not legal.");
                        }
                    }
                }
                for (int k = 0; k < SUDOKU_SIZE; k++) {
                    alreadyHasNumber[k] = false;
                }
            }
        }
    }

    private int getNumFromTest(int[][] puzzle, int testType, int i, int j) {
        switch (testType) {
        case ROW_TEST:
            return puzzle[i][j] - 1;
        case COL_TEST:
            return puzzle[j][i] - 1;
        case SQ3_TEST:
            return puzzle[(i / SUDOKU_SQUARE_SIZE) * SUDOKU_SQUARE_SIZE + j
                    / SUDOKU_SQUARE_SIZE][i % SUDOKU_SQUARE_SIZE
                            * SUDOKU_SQUARE_SIZE + j % SUDOKU_SQUARE_SIZE] - 1;
        default:
            return 0;
        }
    }

    /**
     * Returns the digit in the specified square, 0 if empty.
     * 
     * Calling with arguments (0, 0) will get the digit on the top left corner,
     * and (8, 8) will point to the bottom right corner. (8, 0) will point to
     * the top right corner, while (0, 8) will point to the bottom left corner.
     * 
     * Note that in (x, y), x is the column number and y is the row number.
     * 
     * @param x
     *            the column which the digit is to be taken from
     * @param y
     *            the row which the digit is to be taken from
     * @throws IllegalArgumentException
     *             if x or y is out of range
     * @return the digit in the specified square
     */
    public int getDigit(int x, int y) {
        if (!isInRange(x) || !isInRange(y)) {
            throw new IllegalArgumentException(
                    "the given square is out of range");
        }
        return puzzle[y - 1][x - 1];
    }

    /**
     * Sets the specified square's number to the specified digit.
     * 
     * Calling with arguments (0, 0) will get the digit on the top left corner,
     * and (8, 8) will point to the bottom right corner. (8, 0) will point to
     * the top right corner, while (0, 8) will point to the bottom left corner.
     * 
     * Note that in (x, y), x is the column number and y is the row number.
     * 
     * This method will return <code>false</code> if the set is illegal. The set
     * is illegal if it changes the puzzle in a way that forces it to not follow
     * the standard Sudoku rules: "Each row, column, and box may only contain
     * one of each number from 1-9."
     * 
     * @param x
     *            the column number of the square to set the digit
     * @param y
     *            the row number of the square to set the digit
     * @param digit
     *            the digit to set the square to
     * @throws IllegalArgumentException
     *             if x or y is out of range
     * @return <code>true</code> if successful (legal set), <code>false</code>
     *         otherwise.
     */
    public boolean setDigit(int x, int y, int digit) {
        if (!isInRange(x) || !isInRange(y)) {
            throw new IllegalArgumentException(
                    "the given square is out of range");
        }
        if (getDigit(x, y) != digit) {
            if (digit < 1 || digit > SUDOKU_SIZE) {
                throw new IllegalArgumentException("digit is out of range");
            }
            // check row
            boolean[] alreadyHasNumber = new boolean[SUDOKU_SIZE];
            alreadyHasNumber[digit - 1] = true;
            for (int i = 1; i <= SUDOKU_SIZE; i++) {
                if (i != x) {
                    int num = getDigit(i, y) - 1;
                    if (num != -1) {
                        if (!alreadyHasNumber[num]) {
                            alreadyHasNumber[num] = true;
                        } else {
                            return false;
                        }
                    }
                }
            }
            for (int i = 0; i < SUDOKU_SIZE; i++) {
                if (i != digit - 1) {
                    alreadyHasNumber[i] = false;
                }
            }
            // check column
            for (int i = 1; i <= SUDOKU_SIZE; i++) {
                if (i != y) {
                    int num = getDigit(x, i) - 1;
                    if (num != -1) {
                        if (!alreadyHasNumber[num]) {
                            alreadyHasNumber[num] = true;
                        } else {
                            return false;
                        }
                    }
                }
            }
            for (int i = 0; i < SUDOKU_SIZE; i++) {
                if (i != digit - 1) {
                    alreadyHasNumber[i] = false;
                }
            }
            // check box
            for (int i = 0, j = (x - 1) - ((x - 1) % SUDOKU_SQUARE_SIZE), k = (y
                    - 1) - ((y - 1)
                            % SUDOKU_SQUARE_SIZE); i < SUDOKU_SIZE; i++) {
                int tempX = j + i % SUDOKU_SQUARE_SIZE;
                int tempY = k + i / SUDOKU_SQUARE_SIZE;
                if (tempX != x - 1 && tempY != y - 1) {
                    int num = puzzle[tempY][tempX] - 1;
                    if (num != -1) {
                        if (!alreadyHasNumber[num]) {
                            alreadyHasNumber[num] = true;
                        } else {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    public static Sudoku getRandomPuzzle() {
        return new Sudoku(readFile(random.nextInt(NUM_OF_PUZZLES) + 1));
    }

    private static int[][] readFile(int puzzleNum) {
        // TODO
        File file = new File("puzzle" + puzzleNum);
        int[][] result = new int[Sudoku.SUDOKU_SIZE][Sudoku.SUDOKU_SIZE];
        try (BufferedReader reader = new BufferedReader(new FileReader(file))) {
            for (int i = 0; i < Sudoku.SUDOKU_SIZE; i++) {
                String[] line = reader.readLine().split(" ");
                for (int j = 0; j < Sudoku.SUDOKU_SIZE; j++) {
                    result[i][j] = Integer.parseInt(line[j]);
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        return result;
    }

    private boolean isInRange(int i) {
        return i > 0 && i <= SUDOKU_SIZE;
    }

}

一些关切事项：

1. 在setDigit()和checkBoard()类中，有一个boolean数组alreadyHasNum。在每个循环之后，这个数组应该重置，还是应该创建一个新的数组？
2. 逻辑有意义吗？(与之一样，我处理行/列号和板检查的方式是否合理？)
3. 还要别的吗？

Answer 1

有几件事就在最上面。

如果你有任何关于发现谜题的解决方案的野心，那么你应该首先阅读Knuth的舞蹈链接纸和诺维格的sudoku散文。

private int getNumFromTest(int[][] puzzle, int testType, int i, int j) {
    switch (testType) {
    case ROW_TEST:
        return puzzle[i][j] - 1;
    case COL_TEST:
        return puzzle[j][i] - 1;
    case SQ3_TEST:
        return puzzle[(i / SUDOKU_SQUARE_SIZE) * SUDOKU_SQUARE_SIZE + j
                / SUDOKU_SQUARE_SIZE][i % SUDOKU_SQUARE_SIZE
                        * SUDOKU_SQUARE_SIZE + j % SUDOKU_SQUARE_SIZE] - 1;
    default:
        return 0;
    }
}

主要代码气味在这里--你用开关来改变行为。这几乎总是意味着存在一个尚未发现的底层类。在本例中，您有一个约束/规范接口的证据，该接口有三个不同的实现。

for (int i = ROW_TEST; i <= SQ3_TEST; i++) 

这里的主要症状是枚举索引，不是因为您想要int，而是因为您希望获得int允许您拥有的其他东西(在本例中，我前面提到过的约束)。这强烈地意味着您应该从集合中读取--如果没有特定的顺序，则为Set；如果顺序重要，则为List。

private void checkBoard(int[][] puzzle) {
    boolean[] alreadyHasNumber = new boolean[SUDOKU_SIZE];
    for (int i = ROW_TEST; i <= SQ3_TEST; i++) {
        for (int j = 0; j < SUDOKU_SIZE; j++) {
            for (int k = 0; k < SUDOKU_SIZE; k++) {
                int num = getNumFromTest(puzzle, i, j, k);
                if (num != -1) {
                    if (!alreadyHasNumber[num]) {
                        alreadyHasNumber[num] = true;
                    } else {
                        throw new IllegalArgumentException(
                                "Puzzle is not legal.");
                    }
                }
            }
            for (int k = 0; k < SUDOKU_SIZE; k++) {
                alreadyHasNumber[k] = false;
            }
        }
    }
}

这里的代码很混乱，因为你写的是“如何去做”，而不是先写出你想要做的事情。因此，让我们仔细研究一下；您要验证的规则是，在任何相关的单元格分组中，不应该出现多于一次的数字。特别要注意的是，“不重复”部分并不关心我们谈论的是哪一组细胞--在这个组中总是有9个细胞，在这个组中不应该出现多于一次的数字。

这意味着，应该有一个函数，它接收最多9个数字的列表，并确保那里没有重复，还有一个东西需要一个9x9网格，在同一组中给出大约9个单元格。实际上，有27件事--有9件知道如何选择不同的行，9件知道如何选择不同的列，9件知道如何选择不同的正方形。所以您的验证检查实际上类似于

for (Selector s : selectors) {
    CellValues cellValues = s.getCellValues(board);
    if ( ! noDuplicates.isSatisfiedBy(cellValues) ) {
        throw new IllegalArgumentException(...);
    }
}

更一般的注释

// Convention: ALLCAPS for static data members unless you have a compelling
// reason.
private static final Random RANDOM = new Random();

public static Sudoku getRandomPuzzle() {
    return new Sudoku(readFile(RANDOM.nextInt(NUM_OF_PUZZLES) + 1));
}

非常糟糕的想法，因为以这种方式引入随机数，很难构造出对此代码的可靠测试。至少，您希望将随机数生成与如何使用它分开，这样您就可以编写一个没有随机性的测试。

public static Sudoku getRandomPuzzle() {
    return getPuzzle(RANDOM.nextInt(NUM_OF_PUZZLES));
}

public static Sudoku getPuzzle(int puzzleId) {
    return new Sudoku(readFile(puzzleId + 1));
} 

更好的是，允许有人给你一个随机-没有什么特别的理由，只有你的RNG应该被使用。

public static Sudoku getRandomPuzzle() {
    return getPuzzle(RANDOM);
}

public static Sudoku getRandomPuzzle(Random random) {
    return getPuzzle(random.nextInt(NUM_OF_PUZZLES));
}

public static Sudoku getPuzzle(int puzzleId) {
    return new Sudoku(readFile(puzzleId + 1));
} 

当然，拼图的来源需要一个File没有什么特别的原因；这里有一个Factory或Repository的抽象空间(或者两者兼而有之)。

Answer 2

如果数组大于* 9x9，则忽略超出范围的元素。

通常失败的速度快，失败的声音大。如果数组的大小错误，我建议失败，因为这肯定表示调用代码中有错误。