哪種算法最適合用Python解決像「Boggle」這樣的文字搜索遊戲

Question

我正在編寫類似於Boggle的遊戲，遊戲者應該在隨機字母組成的大字符串中找到單詞。

例如，有五個陣列帶有像這樣的字符串。五排，由六個字母每一個：

• 它不可能：

  AMSDNS 
  MASDOM 
  ASDAAS 
  DSMMMS 
  OAKSDO 
  

  所以，遊戲的用戶使用提供了下列限制和規則，記住字母應話重複同一封信來表達一個字。我在談論骰子游戲中的「物理」字母。它不可能使用相同的骰子兩次或更多來製造這個詞。

• 它不可能「跳」任何字母來形成一個詞。使這個詞的字母必須是連續的。
• 用戶可以在任何方向上移動，而不受上述兩個限制。所以它有可能先到頂部，然後到底部，然後到右側，然後再頂部，依此類推。所以尋找單詞的動作可能會有些不穩定。

我想知道如何通過所有的字符串來說話。要知道單詞我要使用帶文字的txt文件。

我不知道如何設計一個能夠執行搜索的算法，特別是思考尋找單詞和尊重限制所需的不規則運動。

我已經實現了UX，擲骰子和填充棋盤遊戲的邏輯以及六字母骰子的所有邏輯。

但是這部分其實並不容易，我想讀一讀你對這個有趣的挑戰的建議。

我在這款遊戲中使用Python，因爲它是我用來編寫代碼的語言，也是我最喜歡的語言。但是算法本身的解釋或建議也應該很好，與語言無關。

Answer 1

基本算法很簡單。

• 對於每個圖塊，請執行以下操作。
  • 從空的候選詞開始，然後訪問當前拼貼。
  • 按照以下步驟訪問磁貼。
    • 將瓷磚的位置的字母添加到候選字。
    • 候選詞是已知詞嗎？如果是這樣，請將其添加到找到的單詞列表中。
    • 候選詞是任何已知單詞的前綴嗎？
      • 如果是這樣，對於沒有被訪問以形成候選詞的每個相鄰小塊，訪問它（即，遞歸）。
      • 如果不是，回溯（停止考慮這個候選詞的新瓷磚）。

爲了使事情順利進行問這個問題的時候「是這個字詞在我的字典裏前綴」，考慮代表你的字典爲trie。嘗試爲單詞和前綴提供快速查找時間。

Answer 2

您可能會發現一個有用的Trie - 將所有字典單詞放入Trie，然後從Boggle網格中創建另一個Trie，只要您匹配字典Trie即可。

I.e.字典特里：

S->T->A->C->K = stack 
     \->R->K = stark 
     \->T = start 

電網：（簡體）

STARKX 
XXXTXX 
XXXXXX 

電網特里：（只顯示從S開始 - 也開始以一種藝術等）

S->X (no matches in dict Trie, so it stops) 
\->T->X 
    \->A-R->K (match) 
     | |->T (match) 
     | \->X 
     \->C->K (match) 
     \->X  

你可以用GraphViz想象你的嘗試像this。