java - 如何在 Java 中正确实现填字游戏解算器

Question

我在执行以下任务时遇到问题。

A square matrix has eleven letters missing, which you have to replace.

Every row, column contain all the letters in the word "BRAVE".

问题是当我尝试运行这段代码时，似乎存在无限递归，该计划永无止境。

调试了两天了，还是没发现问题所在。

public class Crossword {

    static Character[] letters = new Character[]{'B', 'R', 'A', 'V', 'E'};

    static boolean isFilled(char[][] matrix) {
        Set<Character> lettersSet = new HashSet<>(Arrays.asList(letters));

        // Check rows and columns simultaneously
        for (int i = 0; i < matrix.length; i++) {
            Set<Character> rowLetters = new HashSet<>();
            Set<Character> colLetters = new HashSet<>();

            for (int j = 0; j < matrix.length; j++) {
                rowLetters.add(matrix[i][j]);
                colLetters.add(matrix[j][i]);
            }

            if (!rowLetters.containsAll(lettersSet) || !colLetters.containsAll(lettersSet)) {
                return false;
            }
        }

        return true;
    }

    static boolean containsLetter(char[] row, char symbol) {
        for (char c : row) {
            if (c == symbol) {
                return true;
            }
        }

        return false;
    }

    static void fillMatrixBruteForce(char[][] matrix) {

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {

                if (matrix[i][j] == ' ') {

                    for (int k = 0; k < letters.length; k++) {
                        if (!containsLetter(matrix[i], letters[k])) {

                            matrix[i][j] = letters[k];
                            if (isFilled(matrix)) {
                                return;
                            } else {
                                fillMatrixBruteForce(matrix);
                            }

                        }
                    }
                    matrix[i][j] = ' ';
                }
            }
        }

    }

    static void print(char[][] matrix) {
        Arrays.stream(matrix).forEach(
                System.out::println
        );
    }

    public static void main(String[] args) {
        char[][] matrix = {
                {'B', 'R', 'A', 'V', 'E'},
                {' ', 'E', 'B', 'R', ' '},
                {' ', ' ', 'V', ' ', 'B'},
                {' ', 'B', 'R', ' ', ' '},
                {' ', ' ', 'E', 'B', ' '}
        };
        print(matrix);

        fillMatrixBruteForce(matrix);
        print(matrix);

Answer 1

代码有两个问题。

第一个是递归中的错误，导致倒数第二个空白单元格永远不会被填充。

if (isFilled(matrix)) {
    return;
} else {
    fillMatrixBruteForce(matrix);
}

在第一种情况下，我们检查是否刚刚放置了最后一个字母。如果我们这样做了，我们就会回来。这部分很好。

在第二种情况下，我们递归地调用自己来看看这个猜测是否会导致解决方案。然而，无论结果如何，我们都会表现得好像我们失败了一样，并覆盖了我们的猜测。

为了解决这个问题，我们还检查递归是否成功，在这种情况下我们返回:

if (isFilled(matrix)) {
    return;
} else {
    fillMatrixBruteForce(matrix);
    if (isFilled(matrix)) {
        return;
    }
}

(或者，fillMatrixBruteForce 可以返回 true 或 false 来指示它是成功还是放弃。这意味着我们不会再次检查 isFilled。)

第二个问题是性能。正如所写的，该算法非常慢。幸运的是，有一个简单的调整可以大大加快速度。

对于上下文，有 11 个开放单元格，每个单元格可以包含五个字母之一。有 48,828,125 种不同的可能性需要检查。您确实不想强制计算机递归地检查所有这些，这意味着快速放弃不可能的值至关重要。

您已经使用 containsLetter 方法执行了此操作。但是，这只检查给定的行是否包含该字母。这意味着很多明显不可能的组合会从裂缝中溜走，并且完全是暴力破解的。通过添加第二种方法，columnContainsLetter 并检查该字母是否存在于当前行或列(或两者)中，这大大减少了我们的可能性数量。被迫检查并使算法在我的计算机上运行仅需几秒钟。