這個拼字遊戲算法究竟是什麼「錨點」？

我想實現這個算法：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的交叉檢查時，它顯然並不需要它？

來源

2012-09-08 NPS

根據拼字遊戲的規則，你的單詞必須連接到 - 或者是停留在板上的現有單詞處。現在，當我們看一條線在同一時間有三種類型的錨：

瓷磚在同一行字母左側，
瓷磚的一封信就在同一直線上，
和與當前行上方或下方行中的字母相鄰的圖塊。

如果我們在上面或下面一行中的字母旁邊放置一個字母，我們必須用這些字母形成一個有效的單詞，從而對該錨定字母的附加約束。當使用相鄰錨在當前行的信（和僅那些），我們可以在該瓷磚放置字母由我們要形成在當前行的字僅受限，所以沒有檢查比其他實際的單詞形成算法是必需的。

這意味着，在你的例子有實際上通過對瓷磚x信件沒有額外的限制。只需找到一個從x到左邊的前綴，形成一個有效的單詞（或更長的前綴），其中包含字母A。

您可能還需要檢查出的Udacity課程「Design of Computer Programs」，他們在單位6

來源

2012-09-08 11:19:10

好吧，這有點幫助，但我仍然有一些問題。第3.3.1段規定：「......此外，錨方**恰恰是那些具有非平凡**交叉覈對的......」。我用大膽的建議（IMO）來表示那些錨點的部分只是**那些需要進行交叉檢查的部分（因此那些與當前線條上方或下方線條相鄰的那些）。然而，你在帖子中寫的是讓我認爲錨是那些只有**有時需要檢查的方格。我錯在哪裏，哪一個是真的？ ---另外，爲什麼我從不**需要交叉檢查左邊部分的正方形？ – NPS

我認爲，術語_cross check_的用法在這裏有點不一致。我理解3.3.1的方式是，anchor _never_左側的部分觸及另一個字母。（它由現有字母組成，或者最多擴展到左側的下一個錨點，否則該單詞將屬於另一個錨點。）因此，左側部分可以是任何前綴（來自已知前綴的集合），並且只有當前綴到達錨時，才檢查它是否適合板上現有的字母。 –

我把你的帖子標記爲答案，儘管它是另一種線索，最終讓我意識到什麼是實際答案。儘管如此，我非常感謝。你的帖子和你提供的鏈接都有幫助。順便說一句。我想澄清一些事情供其他人閱讀：** ANCHORS是任何方式（垂直或水平方向）與董事會上已有的任何TILE相鄰的**。我真的希望有人在任何地方說過。：P另外，**錨有時（但不總是）需要交叉檢查**，不多也不少。 – NPS

討論一個拼字遊戲，解決算法我創建了一個算法基於洪水填充收集所有可在瓷磚觸摸我們剛掉落的那些，然後其中一個必須與中央瓷磚相交才能使戲劇有效。

該算法從您放置的每個拼貼開始，然後檢查每個周圍方塊的拼貼，如果拼塊存在於特定方向，則將其添加到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-07 13:04:59 cjnevin

改進了我的答案，我也將盡快添加MD文件。該函數滿足上面發佈的錨點定義。 – cjnevin

雖然這個鏈接可能回答這個問題，但最好在這裏包含答案的重要部分，並提供供參考的鏈接。如果鏈接頁面更改，則僅鏈接答案可能會失效。 – DavidPostill

感謝您的提示，沒有想到，但它是有道理的。我會更新我的答案。 – cjnevin

這個拼字遊戲算法究竟是什麼「錨點」？

回答

相關問題