4

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

初始网格如下所示：

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

这是一个示例单词列表：

pain
nice
pal
id

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

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

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

为了开始解决问题，我将网格存储在 2-dim 中。char 数组，我将单词按它们的长度存储在集合列表中：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垂直放置，但是当意识到这是一个错误的选择时，它会回溯，但是到那时初始网格已经改变并且占位符的数量将会减少。您认为该算法如何修复？

4

2 回答 2

4

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

  • 在 开始处创建矩阵的深层副本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请注意，如果采用上述第二种方法，则简单地返回 a boolean（true如果成功）并传递c给递归调用可能更有意义solve。unfill可以返回void，因为它不会失败，除非你有错误。

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

另请参阅Java 是“按引用传递”还是“按值传递”？

于 2017-06-21T22:40:55.417 回答
1

您自己确定了它：

它会回溯，但到那时初始网格已经改变

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

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

于 2017-06-21T21:57:28.777 回答