Java 中用于解决填字游戏的递归回溯

Question

我需要根据初始网格和单词 （单词可以多次使用或根本不使用）.

来解决填字游戏

初始网格如下所示：

++_+++
+____+
___+__
+_++_+
+____+
++_+++

这是一个单词列表示例：

pain
nice
pal
id

任务是填充占位符（水平或垂直长度 > 1） 像这样：

++p+++
+pain+
pal+id
+i++c+
+nice+
++d+++

任何正确的解决方案都可以接受，并且保证有解决方案。

为了开始解决问题，我将网格存储在2-dim中。 char 数组，我将单词按长度存储在集合列表中：List<Set<String>> words，例如words.get(4)

可以访问长度为 4 的单词

然后我从网格中提取所有占位符的位置并将它们添加到占位符列表（堆栈）中：

class Placeholder {
    int x, y; //coordinates 
    int l; // the length
    boolean h; //horizontal or not
    public Placeholder(int x, int y, int l, boolean h) {
        this.x = x;
        this.y = y;
        this.l = l;
        this.h = h;
    }
}

算法的主要部分是solve()方法：

char[][] solve (char[][] c, Stack<Placeholder> placeholders) {
    if (placeholders.isEmpty())
        return c;

    Placeholder pl = placeholders.pop();
    for (String word : words.get(pl.l)) {
        char[][] possibleC = fill(c, word, pl); // description below
        if (possibleC != null) {
            char[][] ret = solve(possibleC, placeholders);
            if (ret != null)
                return ret;
        }
    }
    return null;
}

函数 fill(c, word, pl) 只是 returns 一个新的填字游戏，当前单词写在当前占位符 pl 上。如果 word 与 pl 不兼容，则函数 returns null.

char[][] fill (char[][] c, String word, Placeholder pl) {

    if (pl.h) {
        for (int i = pl.x; i < pl.x + pl.l; i++)
            if (c[pl.y][i] != '_' && c[pl.y][i] != word.charAt(i - pl.x))
                return null;
        for (int i = pl.x; i < pl.x + pl.l; i++)
            c[pl.y][i] = word.charAt(i - pl.x);
        return c;

    } else {
        for (int i = pl.y; i < pl.y + pl.l; i++)
            if (c[i][pl.x] != '_' && c[i][pl.x] != word.charAt(i - pl.y))
                return null;
        for (int i = pl.y; i < pl.y + pl.l; i++)
            c[i][pl.x] = word.charAt(i - pl.y);
        return c;
    }
}

这是 Rextester 上的完整代码。

问题是我的回溯算法运行不正常。假设这是我的初始网格：

++++++
+____+
++++_+
++++_+
++++_+
++++++

这是单词列表：

pain
nice

我的算法会将单词 pain 垂直放置，但当意识到这是一个错误的选择时，它会回溯，但到那时初始网格已经改变，占位符的数量将是减少。您认为该算法可以如何修复？

Answer 1

您自己识别的：

it will backtrack, but by that time the initial grid will be already changed

那个网格应该是局部矩阵，而不是全局矩阵。这样，当您使用 null 的 return 进行备份时，来自父调用的网格仍然完好无损，准备好尝试 for 循环中的下一个单词。

您的终止逻辑是正确的：当您找到解决方案时，立即将该网格传递回堆栈。

Answer 2

这可以通过两种方式解决：

在fill的开头创建矩阵的a deep copy，修改并return那个（保持原样不变）。

鉴于您已经绕过了矩阵，这不需要任何其他更改。

这很简单，但效率很低，因为每次尝试填写单词时都需要复制矩阵。
创建一个 unfill 方法，它恢复在 fill 中所做的更改，在每个 for 循环迭代结束时调用。
```
for (String word : words.get(pl.l)) {
    if (fill(c, word, pl)) {
        ...
        unfill(c, word, pl);
    }
}
```
注意：我根据下面的注释对 fill 做了一些改动。

当然只是试图擦除所有字母可能会擦除其他放置单词的字母。为了解决这个问题，我们可以计算每个字母属于多少个单词。

更具体地说，有一个 int[][] counts（也需要传递或以其他方式访问）并且每当您更新 c[x][y] 时，也增加 counts[x][y]。要还原展示位置，请将该展示位置中每个字母的数量减少 1，并且仅删除数量为 0 的字母。

这有点复杂，但比上述方法更有效。

在代码方面，您可以在 fill:
中放置类似这样的内容（第一部分，第二部分类似）
```
for (int i = pl.x; i < pl.x + pl.l; i++)
    counts[pl.y][i]++;
```
而 unfill 看起来像这样：（同样只是第一部分）
```
for (int i = pl.x; i < pl.x + pl.l; i++)
    counts[pl.y][i]--;
for (int i = pl.x; i < pl.x + pl.l; i++)
    if (counts[pl.y][i] == 0)
        c[pl.y][i] = '_';
// can also just use a single loop with "if (--counts[pl.y][i] == 0)"
```

请注意，如果采用上述第二种方法，简单地使用 fill return a boolean（如果成功则为 true）和只需将 c 传递给 solve 的递归调用即可。 unfill 可以 return void，因为它不会失败，除非你有错误。

您在代码中传递的只有一个数组，您所做的只是更改其名称。

另见 Is Java "pass-by-reference" or "pass-by-value"?

Java 中用于解决填字游戏的递归回溯

Recursive backtracking in Java for solving a crossword

java

algorithm

recursion

backtracking

recursive-backtracking

这是 Rextester 上的完整代码。