Crossword Visualizer 广度优先搜索方向

Question

我目前正在做我的一个小项目，一个填字游戏求解器。

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

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

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

例如，如果我的看板是这样的：

Y A T
C E V
B X S

并且我需要查找单词 'YES'，算法在 [0][0] 处进行匹配并获取所有邻居（在本例中为 A、C、E）。然后它检查是否有任何匹配单词的第二个字符（这里是 E）。但是现在算法应该看到这个词在诊断上跟随并且只有 return 对角线邻居（这里是 S）。

您是否知道无需编写数千个 if 语句即可将此信息传递给辅助函数的优雅方法？

为了更好地理解，这是我目前编写的代码：

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

当然，如果您对我如何高效地编写算法有任何其他建议leaner/more，我愿意接受所有反馈。

感谢您的帮助，感激不尽:)

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

Crossword Visualizer 广度优先搜索方向

Crossoword Visualizer Breadth first search with direction

javascript

algorithm

breadth-first-search

visualizer