如何在Java中正确实现填字游戏解决器

Question

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

方阵缺少 11 个字母，您必须替换它们。

每一行、每一列都包含“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

方法做到了这一点。但是，这只检查给定的row是否包含该字母。这意味着很多明显不可能的组合会从裂缝中溜走，并且完全是暴力破解的。通过添加第二种方法

columnContainsLetter

并检查该字母是否存在于当前行或列（或两者）中，这大大减少了我们被迫检查并使算法运行的可能性数量在我的电脑上只需几秒钟。

Answer 2

数独

难题的算法相同，称为回溯。

class Crossword {
    char[][] matrix;
    char[] letters = new char[] { 'B', 'R', 'A', 'V', 'E' };
    int length = letters.length;
    boolean solved;

    Crossword(char[][] matrix) {
        this.matrix = matrix;
    }
    
    void solve(int m, int n, char c) {
        if (matrix[m][n] == ' ') {
            for (int i = 0; i < length; i++) {
                if (valid(m, n, letters[i])) {
                    matrix[m][n] = letters[i];
                    if (m == length - 1 && n == length - 1) {
                        solved = true;
                        return;
                    }
                    int mc = m, nc = n;
                    if (++n == length) {
                        n = 0;
                        if (++m == length) {
                            solved = true;
                            return;
                        }
                    }
                    solve(m, n, 'B');
                    if (solved) return;
                    m = mc;
                    n = nc;
                    matrix[m][n] = ' ';
                }
            }
        } else {
            if (++n == length) {
                n = 0;
                if (++m == length) {
                    solved = true;
                    return;
                }
            }
            solve(m, n, 'B');
        }
    }

    boolean valid(int m, int n, char c) {
        for (int i = 0; i < length; i++) {
            if (matrix[m][i] == c) return false;
            if (matrix[i][n] == c) return false;
        }
        return true;
    }
}

这是一个示例用法。

public static void main(String[] args) {
    char[][] matrix = {
        {'B', 'R', 'A', 'V', 'E'},
        {' ', 'E', 'B', 'R', ' '},
        {' ', ' ', 'V', ' ', 'B'},
        {' ', 'B', 'R', ' ', ' '},
        {' ', ' ', 'E', 'B', ' '}
    };
    Crossword c = new Crossword(matrix);
    c.solve(0, 0, 'B');
    Stream.of(c.matrix).forEach(x -> System.out.println(Arrays.toString(x)));
}

输出

[B, R, A, V, E]
[V, E, B, R, A]
[R, A, V, E, B]
[E, B, R, A, V]
[A, V, E, B, R]