用于解决填字游戏的Java中的递归回溯(Recursive backtracking in Java for solving a crossword)

用于解决填字游戏的Java中的递归回溯(Recursive backtracking in Java for solving a crossword)

给定初始网格和单词（单词可以多次使用或根本不使用），我需要解决填字游戏。

初始网格看起来像这样：

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

以下是Rextester的完整代码。

---

问题是我的回溯算法不能很好地工作。 让我们说这是我的初始网格：

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

Here is the full code on Rextester.

---

The problem is that my backtracking algorithm doesn't work well. Let's say this is my initial grid:

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

And this is the list of words:

pain nice

My algorithm will put the word pain vertically, but then when realizing that it was a wrong choice it will backtrack, but by that time the initial grid will be already changed and the number of placeholders will be reduced. How do you think the algorithm can be fixed?

最满意答案

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

在fill开始时创建矩阵的深层副本 ，修改并返回（保留原始原样）。

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

这很简单但效率很低，因为每次尝试填写单词时都需要复制矩阵。

创建一个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返回一个boolean （如果成功则为true ）可能更有意义，只需将c传递给resolve的递归调用。 unfill可以返回void ，因为它不会失败，除非你有bug。

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

另请参阅Java“pass-by-reference”或“pass-by-value”？

This can be solved in 2 ways:

Create a deep copy of the matrix at the start of fill, modify and return that (leaving the original intact).

Given that you already pass around the matrix, this wouldn't require any other changes.

This is simple but fairly inefficient as it requires copying the matrix every time you try to fill in a word.

Create an unfill method, which reverts the changes made in fill, to be called at the end of each for loop iteration.

for (String word : words.get(pl.l)) { if (fill(c, word, pl)) { ... unfill(c, word, pl); } }

Note: I changed fill a bit as per my note below.

Of course just trying to erase all letter may erase letters of other placed words. To fix this, we can keep a count of how many words each letter is a part of.

More specifically, have a int[][] counts (which will also need to be passed around or be otherwise accessible) and whenever you update c[x][y], also increment counts[x][y]. To revert a placement, decrease the count of each letter in that placement by 1 and only remove letters with a count of 0.

This is somewhat more complex, but much more efficient than the above approach.

In terms of code, you might put something like this in fill: (in the first part, the second is similar)

for (int i = pl.x; i < pl.x + pl.l; i++) counts[pl.y][i]++;

And unfill would look something like this: (again for just the first part)

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)"

---

Note that, if going for the second approach above, it might make more sense to simply have fill return a boolean (true if successful) and just pass c down to the recursive call of solve. unfill can return void, since it can't fail, unless you have a bug.

There is only a single array that you're passing around in your code, all you're doing is changing its name.

See also Is Java "pass-by-reference" or "pass-by-value"?