☰

文字マトリックスから可能な単語のリストを見つける方法 [Boggle Solver] 質問する

tag-icon • tag-icon algorithm puzzle boggle
文字マトリックスから可能な単語のリストを見つける方法 [Boggle Solver] 質問する

最近、私は iPhone で Scramble というゲームをしています。このゲームは Boggle としてご存知の方もいるかもしれません。基本的に、ゲームを開始すると、次のような文字のマトリックスが表示されます。

F X I E
A M L O
E W B X
A S T U

このゲームの目的は、文字をつなげて作れる単語をできるだけ多く見つけることです。どの文字から始めても、その文字の周りの文字はすべて対象になります。次に次の文字に移ると、その文字の周りの文字はすべて対象になりますが、以前に使用した文字は除きます。したがって、たとえば上記のグリッドでは、 、、などLOBの単語を思いつくことができます。単語は少なくとも 3 文字で、NxN 文字以下でなければなりません。これはこのゲームでは 16 文字ですが、実装によっては異なる場合があります。このゲームは楽しくてやみつきになるのですが、どうやら私はあまり上手ではないようで、できるだけ良い単語を出すプログラムを作って少しズルをしたいと思いました (単語が長いほど、より多くのポイントが得られます)。TUXSEAFAME

サンプルボグル
（ソース：boggled.org）

残念ながら、私はアルゴリズムやその効率性などにはあまり詳しくありません。最初の試みでは辞書を使用しましたこのような(~2.3MB) で、辞書のエントリとの組み合わせを一致させようとする線形検索を実行します。この方法では、可能性のある単語を見つけるのに非常に長い時間がかかり、1 ラウンドあたり 2 分しか与えられないため、十分ではありません。

Stackoverflowers の誰かがもっと効率的なソリューションを思いつくかどうか興味があります。私は主に、Big 3 P (Python、PHP、Perl) を使用したソリューションを探していますが、速度が重要なので、Java や C++ を使用したものでもかまいません。

現在のソリューション:

  • アダム・ローゼンフィールド、Python、20代
  • John Fouhy、Python、約 3 秒
  • ケント・フレドリック、Perl、約1秒
  • ダリウス・ベーコン、パイソン、約 1 秒
  • rvarcher、VB.NET、約 1 秒
  • パオロ・ベルガンティーノ、PHP(ライブリンク)、約 5 秒 (ローカルでは約 2 秒)

ベストアンサー1

私の回答はここにある他の回答と同じように機能しますが、辞書のセットアップが速いため、他の Python ソリューションよりも少し高速に見えるため、投稿します。(私はこれを John Fouhy のソリューションと比較して確認しました。) セットアップ後、解決にかかる時間はノイズの中に消えます。

grid = "fxie amlo ewbx astu".split()
nrows, ncols = len(grid), len(grid[0])

# A dictionary word that could be a solution must use only the grid's
# letters and have length >= 3. (With a case-insensitive match.)
import re
alphabet = ''.join(set(''.join(grid)))
bogglable = re.compile('[' + alphabet + ']{3,}$', re.I).match

words = set(word.rstrip('\n') for word in open('words') if bogglable(word))
prefixes = set(word[:i] for word in words
               for i in range(2, len(word)+1))

def solve():
    for y, row in enumerate(grid):
        for x, letter in enumerate(row):
            for result in extending(letter, ((x, y),)):
                yield result

def extending(prefix, path):
    if prefix in words:
        yield (prefix, path)
    for (nx, ny) in neighbors(path[-1]):
        if (nx, ny) not in path:
            prefix1 = prefix + grid[ny][nx]
            if prefix1 in prefixes:
                for result in extending(prefix1, path + ((nx, ny),)):
                    yield result

def neighbors((x, y)):
    for nx in range(max(0, x-1), min(x+2, ncols)):
        for ny in range(max(0, y-1), min(y+2, nrows)):
            yield (nx, ny)

使用例:

# Print a maximal-length word and its path:
print max(solve(), key=lambda (word, path): len(word))

編集: 3 文字未満の単語を除外します。

編集 2: Kent Fredric の Perl ソリューションの方が高速な理由が気になりました。文字セットの代わりに正規表現マッチングを使用していることが分かりました。Python で同じことを行うと、速度が約 2 倍になります。

おすすめ記事