提问人：vanderwaal 提问时间：9/21/2023 最后编辑：Federico klez Cullocavanderwaal 更新时间：9/22/2023 访问量：62
如何在 Java 中正确实现填字游戏求解器
How do I implement crossword solver correctly in Java
问：
我在执行以下任务时遇到问题。
方形矩阵缺少 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);
答：
3赞
BambooleanLogic
9/22/2023
#1
代码有两个问题。
第一个是递归中的错误，导致倒数第二个空白单元格永远不会被填充。
if (isFilled(matrix)) {
return;
} else {
fillMatrixBruteForce(matrix);
}
在第一种情况下，我们检查我们是否刚刚放置了最后一个字母。如果我们这样做了，我们就会回来。这部分很好。
在第二种情况下，我们递归地称呼自己，看看这个猜测是否会导致解决方案。然而，无论结果如何，我们都会表现得好像我们失败了，并撤销了我们的猜测。
为了解决这个问题，我们还检查递归是否成功，在这种情况下，我们返回：
if (isFilled(matrix)) {
return;
} else {
fillMatrixBruteForce(matrix);
if (isFilled(matrix)) {
return;
}
}
（或者，可以返回 or 来表示它是成功还是放弃。这意味着我们不必再检查一次。fillMatrixBruteForcetruefalseisFilled
第二个问题是性能。正如所写的那样，该算法非常慢。幸运的是，有一个简单的调整可以大大加快它的速度。
作为上下文，有 11 个打开的单元格，每个单元格能够包含五个字母中的一个。这是 48,828,125 种不同的可能性需要检查。你真的不想强迫你的计算机递归地检查所有这些，这意味着快速放弃不可能的值是至关重要的。
你已经用你的方法做了一些。但是，这仅检查给定行是否包含该字母。这意味着许多明显不可能的组合从裂缝中溜走，并且完全是暴力破解的。通过添加第二种方法，并检查该字母是否存在于当前行或列（或两者）中，这大大减少了我们被迫检查的可能性数量，并使算法在我的计算机上仅几秒钟即可运行。containsLettercolumnContainsLetter
2赞
Reilas
9/22/2023
#2
这与用于解决数独谜题的算法相同，称为回溯。
class Crossword {
char matrix[][], v[];
int length;
boolean solved;
Crossword(char[][] matrix, char[] v) {
this.matrix = matrix;
length = (this.v = v).length;
}
void solve(int m, int n) {
if (matrix[m][n] == ' ') {
for (int i = 0, a, b; i < length; i++) {
if (valid(m, n, v[i])) {
matrix[m][n] = v[i];
a = m;
b = n;
if (++n == length) {
n = 0;
if (++m == length) {
solved = true;
return;
}
}
solve(m, n);
if (solved) return;
m = a;
n = b;
matrix[m][n] = ' ';
}
}
} else {
if (++n == length) {
n = 0;
if (++m == length) {
solved = true;
return;
}
}
solve(m, n);
}
}
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;
}
}
下面是一个示例。
char[][] matrix = {
{'B', 'R', 'A', 'V', 'E'},
{' ', 'E', 'B', 'R', ' '},
{' ', ' ', 'V', ' ', 'B'},
{' ', 'B', 'R', ' ', ' '},
{' ', ' ', 'E', 'B', ' '}
};
char[] v = new char[] { 'B', 'R', 'A', 'V', 'E' };
Crossword c = new Crossword(matrix, v);
c.solve(0, 0);
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]
评论