Java中的递归回溯算法用于解决填字游戏问题

Question

Java中的递归回溯算法用于解决填字游戏问题

javaalgorithmrecursionbacktrackingrecursive-backtracking

4

我需要解决一个填字游戏的问题，给定初始网格和单词（单词可以重复使用或者不使用）。

初始网格如下：

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

以下是一个单词列表的例子：

pain
nice
pal
id

任务是填充占位符 （水平或垂直，长度> 1），如下：

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

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

为了开始解决问题，我将网格存储在二维字符数组中，并按其长度将单词存储在集合列表中：List<Set<String>> words，例如长度为4的单词可以通过words.get(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)函数只是将当前单词写在当前占位符pl上，并返回一个新的填字游戏。如果word与pl不兼容，则函数返回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 垂直放置，但意识到这是错误的选择后会回溯，但此时初始网格已经改变，占位符的数量也会减少。你认为该如何修复算法？

- gdrt

可能是Solving crosswords的重复问题。 - PlsWork

哈哈哈哈哈，这就是我所说的交叉火力：DDD - gdrt

2个回答

1

您自己已经发现了这一点：

它将会回溯，但此时初始网格已经被更改。

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

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

- Prune

请问您能否添加代码？您在谈论哪个矩阵？我认为possibleC矩阵是局部的。 - gdrt

我也相信这是本地的 - 但让我们一起来解决调试技巧：你所说的“初始网格”已经改变了吗？你是否在适当的时候打印出主网格以跟踪数据流？ - Prune

请看最后一个例子，其中只有2个占位符。 "Initial grid" 是指网格上没有字母的情况。然后我的算法选择一个垂直的占位符，然后错误地用单词 pain 填充它，然后递归并尝试使用 nice 填充水平占位符，但失败了，然后回溯并尝试填充垂直占位符（第一个），但现在无法这样做（因为有一个错误），因为初始网格被单词 pain 破坏了。 - gdrt

没错。Dukeling 给了你一个很好的答案，正是我试图引导你的方向。 - Prune

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bernhard Barker · Accepted Answer

这个问题可以通过以下两种方式解决：

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

请注意，如果采用上述第二种方法，简单地让fill返回一个布尔值（如果成功则为true），并将c传递到solve的递归调用中可能更有意义。只要你没有错误，unfill可以返回void，因为它不会失败。

在你的代码中只有一个数组在传递，你所做的就是改变它的名称。

另请参见Java是"按引用传递"还是"按值传递"？