2

我正在尝试实现这个算法：http ://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/lectures/scrabble.pdf但我无法弄清楚这些锚到底是什么正方形是（首先在 3.1.2 中提到，然后在 3.3 中提到）。

我知道他们的候选人都是与已经在董事会上的人相邻的空白方格，但不知道我应该选择哪个。

另外，我不知道为什么左侧的所有方块都有微不足道的交叉检查（意味着每个字母都可能放在那里），而锚点总是有非微不足道的交叉检查。这种情况怎么办：

_._._._
_._.x.A
_._._._

_ 是空方格，x 是锚点，A 是板上已经存在的一些字母 - 为什么在这种情况下我需要检查 x 以进行交叉检查，而它显然不需要它？

4

2 回答 2

3

根据 Scrabble 的规则，你的单词必须连接或锚定在板上的现有单词。现在，当我们一次查看一行时，存在三种类型的锚点：

  • 同一行中字母左侧的平铺，
  • 同一行中字母右侧的瓷砖，
  • 和与当前行上方或下方行中的字母相邻的拼贴。

如果我们将一个字母放在与上一行或下一行中的一个字母相邻的锚上，我们也必须用这些字母形成一个有效的单词，从而对该锚所允许的字母施加额外的限制。当使用与当前行中的字母相邻的锚点时（并且仅限于那些），我们可以放置在该图块上的字母仅受我们将在当前行中形成的单词的限制，因此除了实际之外没有其他检查需要单词形成算法。

这意味着，在您的示例中，实际上对 tile 上的字母没有额外的限制x。只需找到一个从x左侧延伸的前缀，与字母组成一个有效的单词（或更长的前缀）A。

您可能还想查看 Udacity 课程“计算机程序设计”，其中他们在第 6 单元中讨论了拼字游戏求解算法。

于 2012-09-08T11:19:10.337 回答
0

我创建了一个基于洪水填充的算法来收集所有与我们刚刚放下的瓷砖相接触的瓷砖，其中一个必须与中心瓷砖相交才能使游戏有效。

该算法从您放下的每个瓷砖开始，然后检查每个周围的方块是否有瓷砖，如果瓷砖存在于特定方向，则将其添加到 Set 并递归地对接触这个新瓷砖的每个瓷砖执行相同的操作，如果没有tile 存在它将退出该功能。当我们播放的字母在各个方向都用完瓷砖时，递归结束。

    func getFilledSquare(c: Coordinate) -> Square? {
        return squares
            |> { s in filter(s) { $0.c == c && $0.tile != nil } }
            |> { s in first(s) }
    }

    func getAdjacentFilledSquares(c: Coordinate?, vertically v: Bool, horizontally h: Bool, original: Square, inout output: Set<Square>) {
        // We may hit the original square several times in different directions, so we allow it through multiple times
        if let coord = c, sq = getFilledSquare(coord) where sq == original || !output.contains(sq) {
            output.insert(sq)
            if h {
                getAdjacentFilledSquares(coord.next(.Horizontal, d: 1, b: self), vertically: v, horizontally: h, original: original, output: &output)
                getAdjacentFilledSquares(coord.next(.Horizontal, d: -1, b: self), vertically: v, horizontally: h, original: original, output: &output)
            }
            if v {
                getAdjacentFilledSquares(coord.next(.Vertical, d: 1, b: self), vertically: v, horizontally: h, original: original, output: &output)
                getAdjacentFilledSquares(coord.next(.Vertical, d: -1, b: self), vertically: v, horizontally: h, original: original, output: &output)
            }
        }
    }

它是开源的，该方法称为 getAdjacentFilledSquares（我知道有点冗长）。我的仓库在这里：https ://github.com/ChrisAU/Locution?files=1

于 2015-06-07T13:04:59.397 回答