5

スマートフォンには、Ruzzleと呼ばれるこのゲームがあります。
ラズルボード
単語検索ゲームです。

簡単な説明：
ゲームボードは4x4の文字グリッドです。
任意のセルから開始し、上、下、左、右、または斜めにドラッグして単語のスペルを試みます。
ボードは折り返されません。また、選択済みの文字を再利用することはできません。

平均して、私の友人と私は約40語を見つけ、ラウンドの終わりに、ゲームはあなたが得ることができた可能性のある単語の数を通知します。この数は通常約250〜350です。
どのボードが可能な限り多くの単語を生成するのか疑問に思っています。

最適なボードを見つけるにはどうすればよいですか？
私はCで、16文字を取り、すべての適切な単語を出力するプログラムを作成しました。
80,000語以上をテストすると、処理に約1秒かかります。

問題：
ゲームボードの順列の数は26^16です。
それは43608742899428874059776（43六十億）です。

ある種のヒューリスティックが必要です。単語数が少ないと予想されるため、z、q、xなど
のボードをすべてスキップする必要がありますか？確信が持てずに手紙を除外したくありません。 ボードを回転させても同じ結果が得られるため、すべてのボードに4つの複製があります。 しかし、これらの制限があっても、答えを見つけるのに十分な時間が私の人生にはないと思います。

たぶん、ボードの生成は答えではありません。
単語のリストを見て答えを見つけるためのより速い方法はありますか？

4

2 に答える 2

3

興味深い問題です。私は（少なくとも、しかし主に）2つのアプローチを見ます

  1. 1 つは、辞書に基づいて、できるだけ多くの単語を (全方向に)貼り付けるという難しい方法を試すことです。あなたが言ったように、多くの可能な組み合わせがあり、そのルートには、具体的なものに到達するために精巧で複雑なアルゴリズムが必要です

  2. 私がもっと好きな確率に基づく別の「緩い」解決策があります。ボードの歩留まりを最大化するために、外観の悪い文字をいくつか削除することを提案しました。これを拡張すると、辞書で出現頻度の高い文字をより多く使用することができます。

さらなるステップは次のとおりです。

  • 80k 辞書に基づいて、26 文字の L アンサンブルのD各l1文字について、文字l2がl1の前後にある確率を調べます。これはL x L確率配列であり、非常に小さいため、 に拡張することもできますL x L x L。つまり、l1とl2を考慮して、どの確率がl3に適合するかを考えます。アルゴリズムが正確な確率を推定したい場合、これはもう少し複雑です。確率の合計は、たとえば「三角形」構成 (たとえば、位置 (3,3)、(3,4 ) と (3,5)) の結果は、おそらく文字が整列している場合よりも結果が少なくなります [単なる仮定]。まで行かない理由L x L x L x L、これにはいくつかの最適化が必要です...

  • 次に、いくつかの見栄えの良い文字（4〜6など）をボード上にランダムに配置し（8つの可能な方向のうち少なくとも5つの方向に少なくとも1つの空白セルを配置します）、L x L [xL]probas配列を使用して完了します-意味に基づく既存の文字、次のセルは、構成が与えられた確率が高い文字で埋められます [再び、文字は確率の降順でソートされ、2 つの文字が密接に結びついている場合はランダム性を使用します]。

たとえば、水平構成のみを使用して、次の文字を配置し、 と の間の最良の 2 つを見つけたいとしますER。TO

  ...ER??TO...

を使用してL x L、次のようなループを行います (l1 と l2 は、欠落している 2 つの文字です)。絶対に良い文字を見つけますが、代わりにbestchoiceとbestprobaを配列にして、10 個の最良の選択肢を保持することもできます。注: この場合、確率を [0,1] の範囲に保つ必要はありません。 = ( p(l0,l1) + p(l2,l3) ) / 2、l0 と l3 はこの例ではRとTですL x L)

  bestproba = 0
  bestchoice = (none, none)
  for letter l1 in L
    for letter l2 in L
      p = proba('R',l1) + proba(l2,'T')
      if ( p > bestproba ) 
        bestproba = p
        bestchoice = (l1, l2)
      fi
    rof
  rof

アルゴリズムはより多くの要因を考慮することができ、垂直方向と対角線も考慮する必要があります。を使用すると、 、 、のように、よりL x L x L多くの方向のより多くの文字が考慮されます。これには、アルゴリズムをさらに検討する必要があります。ER?R????T?TOL x L

これの多くは事前に計算されている可能性がありL x L、もちろん配列はその1つであることに注意してください。

于 2013-01-19T10:35:50.810 に答える