javascript - 填字游戏可视化工具 带方向的广度优先搜索

Question

我目前正在开发一个小项目，一个填字游戏解算器。

给定 64 个字符的输入，算法将它们显示在 8x8 板上，然后继续查看是否有任何单词匹配。

到目前为止，我已经编写了一个算法，对于每个单词循环遍历板上的字母并检查它们中的任何一个是否等于该单词的第一个字符。如果是这种情况，我调用一个辅助函数，该函数返回当前字符的所有邻居，并继续检查这些邻居中的任何一个是否等于单词的第二个字符，依此类推......所以基本上它是宽度优先使用队列并将邻居推送到该队列的搜索算法:)

到目前为止，这工作得很好，但是我现在意识到，一旦算法匹配了单词的第二个字符，辅助函数应该只返回具有相同方向的邻居。

例如，如果我的主板如下所示:

Y A T
C E V
B X S

我需要查找单词“YES”，该算法在 [0][0] 处获得匹配并获取所有邻居(在本例中为 A、C、E)。然后它检查其中是否有任何一个与单词的第二个字符匹配(这里是 E)。但现在算法应该看到该单词诊断性地跟随并且仅返回对 Angular 邻居(此处为 S)。

您知道有什么优雅的方法可以将此信息传递给辅助函数，而无需编写数千个 if 语句吗？

为了更好地理解，这是我迄今为止编写的代码:

https://jsfiddle.net/jakob_mayerhofer/84xrfuwL/7/

当然，如果您对我如何编写更精简/更有效的算法有任何其他建议，我愿意接受所有反馈。

感谢您的帮助，非常感谢:)

Answer 1

我不会为此选择 BFS 算法，因为您已经知道要查找的单词的长度。当您需要在备选方案中找到最短路径时，您会选择 BFS，但这里从给定的起点(北、南、东、西)只有 4 种可能的备选方案，并且它们都具有相等的长度。在这种情况下，您实际上并不需要图搜索算法。

因此，我将更改 crossWordSolver 的内部部分，并在 4 个可能的方向上使用循环，每个方向只需立即沿该方向扫描到单词的长度即可。

这是这样的:

function crosswordSolver(words, grid) {
  let directions = [[-1, 0], [0, -1], [1, 0], [0, 1]];
  for (word of words) {
    let found = false;
    for (let i = 0; i < 8 && !found; i++) { // <-- extra exit condition
      for (let j = 0; j < 8 && !found; j++) { // <-- ... also here.
        if (grid[i][j] == word[0]) { // Simple check for 1st char
          for (let [dx, dy] of directions) { // Four directions to scan.
            found = true;
            for (let k = 0, x = i, y = j; k < word.length; k++, x+=dx, y+=dy) {
              if (x < 0 || y < 0 || x > 7 || y > 7 || word[k] !== grid[x][y]) {
                found = false; // Out of bounds, or mismatch
                break;
              }
            }
            if (found) break;
          }
        }
      }
    }
    if (found) checked.push(word);
  }
  console.log(checked);
}