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

我需要在给定初始网格和单词的情况下解决填字游戏（单词可以多次使用或根本不使用）.

初始网格如下所示：

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

这是一个单词列表示例：

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() 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. If 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;
    }
}

这是完整的代码雷克斯特 http://rextester.com/MEYRW1661.

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

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

这是单词列表：

pain
nice

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

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

• Create 深拷贝 https://stackoverflow.com/questions/1564832/how-do-i-do-a-deep-copy-of-a-2d-array-in-java矩阵的开头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]++;
  

  And 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直到递归调用solve. unfill可以返回void，因为它不会失败，除非你有错误。

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

也可以看看Java是“按引用传递”还是“按值传递”？ https://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value