6

私はボーグルに似たゲームをコーディングしています。このゲームでは、ゲーマーはランダムな文字でできた大きな文字列の中から単語を見つける必要があります。

たとえば、このように内部に文字列を含む 5 つの配列があります。5 行、それぞれ 6 文字で構成されています。

AMSDNS
MASDOM
ASDAAS
DSMMMS
OAKSDO

したがって、ゲームのユーザーは、次の制限とルールを念頭に置いて、利用可能な文字を使用して単語を作成する必要があります。

  • 同じ文字を繰り返して単語を作ることはできません。サイコロであるゲームの「物理的な」文字について話しています。単語を作るために同じサイコロを 2 回以上使用することはできません。
  • 文字を「ジャンプ」して単語を作ることはできません。単語を構成する文字は連続している必要があります。
  • ユーザーは、上記の 2 つ以上の制限なしに、好きな方向に移動できます。したがって、上、下、右、上、というように移動できます。そのため、言葉を探す動きがどこか不安定なのかもしれません。

すべての文字列を調べて単語を作る方法を知りたいです。単語を知るには、単語を含むtxtファイルを使用します。

検索を実行できるアルゴリズムを設計する方法がわかりません。特に、単語を見つけるために必要な不規則な動きについて考え、制限も尊重します。

UX、サイコロを振ってボードゲームを埋めるロジック、および 6 文字のサイコロのすべてのロジックは既に実装しています。

しかし、この部分は簡単ではありません。この興味深い課題に対するあなたの提案を読みたいと思います。

このゲームでは Python を使用しています。これは、コーディングに使用する言語であり、最も好きな言語だからです。しかし、言語に関係なく、アルゴリズム自体の説明や提案も素晴らしいはずです。

4

2 に答える 2

4

基本的なアルゴリズムは単純です。

  • タイルごとに、次の操作を行います。
    • 空の候補単語から始めて、現在のタイルにアクセスします。
    • 次の手順に従って、タイルにアクセスします。
      • タイルの位置の文字を候補単語に追加します。
      • 候補語は既知語か？その場合は、見つかった単語リストに追加します。
      • 候補語は、既知の語の接頭辞ですか?
        • その場合、候補単語を形成するために訪問されていない隣接タイルごとに、それを訪問します (つまり、再帰)。
        • そうでない場合は、後戻りします (この候補単語の新しいタイルの検討を停止します)。

「この単語は私の辞書の任意の単語の接頭辞ですか」という質問をスムーズに行うために、辞書をtriとして表現することを検討してください。トライにより、単語とプレフィックスの両方の検索時間が短縮されます。

于 2013-01-07T08:15:28.880 に答える
4

Trieが役立つ場合があります。すべての辞書の単語を Trie に入れ、Boggle グリッドから別の Trie を作成します。ただし、辞書 Trie と一致している場合に限ります。

つまり、辞書トライ:

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

グリッド: (簡略化)

STARKX 
XXXTXX 
XXXXXX

グリッド トライ: (S から開始する場合のみ表示 - ART の場合は A から開始するなど)

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

このように、GraphViz を使用して Tries を視覚化できます。

于 2013-01-07T08:17:58.597 に答える