Java中的递归回溯，用于解决填字游戏 [英] Recursive backtracking in Java for solving a crossword

问题描述

在给定初始网格和单词(单词可以使用一次或完全不使用)的情况下，我需要解决一个填字游戏.

I need to solve a crossword given the initial grid and the words (words can be used more than once or not at all).

初始网格如下所示:

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

以下是单词列表示例:

pain
nice
pal
id

任务是像这样填充占位符(水平或垂直长度大于1):

The task is to fill the placeholders (horizontal or vertical having length > 1) like that:

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

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

Any correct solution is acceptable, and it's guaranteed that there's a solution.

为了开始解决问题，我将网格存储在2维中. char数组，我将单词的长度存储在集合列表中:List<Set<String>> words，这样长度为4的单词可以通过words.get(4)

In order to start to solve the problem, I store the grid in 2-dim. char array and I store the words by their length in the list of sets: List<Set<String>> words, so that e.g. the words of length 4 could be accessed by words.get(4)

然后，我从网格中提取所有占位符的位置，并将它们添加到占位符列表(堆栈)中:

Then I extract the location of all placeholders from the grid and add them to the list (stack) of placeholders:

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()方法:

The main part of the algorithm is the solve() method:

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.

Function fill(c, word, pl) just returns a new crossword with the current word written on the current placeholder pl. If word is incompatible with pl, then function 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 上的完整代码.

---

问题是我的回溯算法不能很好地工作.假设这是我的初始网格:

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:

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

这是单词列表:

pain
nice

我的算法会将单词pain垂直放置，但是当意识到选择错误时，它将回溯，但是到那时初始网格将已经更改，并且占位符的数量将减少.您如何看待该算法的固定性?

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?

推荐答案

这可以通过2种方法解决:

This can be solved in 2 ways:

• 创建fill开头的矩阵的深层副本，对其进行修改并返回(保留原样).

• 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.

创建一个unfill方法，该方法将还原在fill中所做的更改，并在每个for循环迭代结束时调用.

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);
    }
}

注意:按照下面的说明，我对fill做了一些改动.

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.

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

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.

就代码而言，您可以在fill中放入如下内容:
(在第一部分中，第二部分是相似的)

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]++;

unfill看起来像这样:(同样仅是第一部分)

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返回boolean(如果成功，则为true)，然后将c向下传递给solve. unfill可以返回void，因为它不会失败，除非您遇到错误.

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.

另请参见是Java的"pass-by-reference" ;或按值传递"?

这篇关于Java中的递归回溯，用于解决填字游戏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！