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

スクラブルのルールによれば、あなたの言葉はボード上の既存の言葉に接続するか、固定する必要があります。一度に1行を見ると、3種類のアンカーがあります。

  • 同じ行の文字の左側にあるタイル、
  • 同じ行の文字の右側にあるタイル、
  • 現在の行の上または下の行の文字に隣接するタイル。

上または下の行の文字に隣接するアンカーに文字を配置する場合、それらの文字でも有効な単語を形成する必要があるため、そのアンカーに許可される文字に追加の制約を課します。現在の行の文字に隣接して（そしてそれらにのみ）アンカーを使用する場合、そのタイルに配置できる文字は、現在の行に形成する単語によってのみ制約されるため、実際の行以外のチェックは行われません。単語形成アルゴリズムが必要です。

つまり、あなたの例では、実際にはタイル上の文字に追加の制約はありませんx。左から伸びる接頭辞を見つけてx、文字.で有効な単語（またはより長い接頭辞）を形成しますA。

また、ユニット6のスクラブル解決アルゴリズムについて説明しているUdacityコース「コンピュータープログラムの設計」も確認してください。

于 2012-09-08T11:19:10.337 に答える
0

フラッド フィルに基づいてアルゴリズムを作成し、ドロップしたばかりのタイルに接触しているすべてのタイルを収集します。プレイを有効にするには、そのうちの 1 つが中央のタイルと交差する必要があります。

アルゴリズムは、ドロップした各タイルから開始し、周囲の各タイルをチェックします。タイルが特定の方向に存在する場合は、それを Set に追加し、この新しいタイルに接触しているタイルごとに同じことを再帰的に行います。タイルが存在する場合は、関数を終了します。再生した文字からすべての方向にタイルがなくなると、再帰は終了します。

    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 に答える