問題タブ [boggle]

これは宿題のためなので、正確なコードは必要ありませんが、正しい方向に向けるのに役立つアイデアをいただければ幸いです。

宿題は、ボーグルを解くプログラムを書くことです。再帰的な部分は理解できたと思いますが、現在の文字列を辞書と比較する方法についての洞察が必要です。

辞書をセットまたはソートされたリストに保存する必要があります。私はセットを使用してこれを実装する方法を試みてきました。プログラムをより速く実行し、行き止まりの道をたどらないようにするために、現在の文字シーケンスがセット (辞書) 内の何かのプレフィックスとして存在するかどうかを確認する必要があります。

set.find() 操作は、文字列が完全に一致する場合にのみ true を返すことがわかりました。ラボの要件で、教授は次のように述べています。

「辞書がセットに格納されている場合、多くのデータ構造ライブラリは、検索している文字列に最も近いセット内の文字列を見つける方法を提供します。このような操作を使用して、特定の接頭辞を持つ単語をすばやく見つけることができます。 ."

私は今日、教授が説明していることを探していました。試行に関する多くの情報を見つけましたが、リストまたはセットを使用する必要があるため、うまくいかないと思います。

オートコンプリート機能のアルゴリズムも調べてみましたが、ここで達成しようとしているものは非常に複雑に思えます。

また、現在のシーケンスを辞書セットの単語と比較するために strncmp() を使用することも考えていましたが、この状況でそれがどのように機能するかはわかりません。

これがセットでどのように機能するかを調査し続けることは価値がありますか、それともソートされたリストを使用して辞書を保存してみるべきですか?

ありがとう

ボーグル ボードが n x n の場合、ボーグルを解く関数の最適な時間計算量 O(n) は?

n^2キャラクターごとに他のキャラクターを見なければならないからだと思い2(n-1)ます。インタビュアーは、これは辞書引きn^2用ではないと主張しました。O(1)

私は、テキスト ファイル (ボード) の行を読み取るBoggleゲーム ソルバーに取り組んでいます。

vectors の aを使用するstringか、s のvector行列を使用するかを行ったり来たりしていcharます。vectorofが関数を使用する必要がある場所であるため、ofのchars方がアクセスしやすいと思います。myvec[y][x]vectorstringstring.at()

char各行をs に解析するか、行を のままにして必要に応じstringてそれぞれにアクセスする必要がある場合、どちらがパフォーマンスが向上するかわかりませんchar。どちらをすべきかについての提案はありますか? 理由を説明すると役立ちます。

そのため、Boggle のシミュレーションの再帰呼び出しを実装する方法を見つけようとしています。人間とコンピューターの 2 人のプレイヤーがいます。人間が行くと、ボード上で単語を見つけ（ランダムにシャッフルされました）、再帰呼び出しが有効性をチェックすることになっています。基本的に、単語入力のインデックス 0 から始まる隣接する文字をループし、そのようにクロールして、その単語が存在するかどうかを毎回確認する必要があります。問題は、これを行う方法が正確にわからないことです。これまでの私のコードは次のとおりです。私の意図をさらに説明するために、いくつかの疑似コードを提供しました。誰でも助けることができますか？

Boggleソルバーを組み立てているときに、誰かが私に説明してくれることを期待していた奇妙な動作に遭遇しました。可能な単語のセットを返す関数を取得しましたが、同じ正方形を2回訪問して作成された単語がソルバーに含まれないようにする方法が欠けているように見えました。seen以前に探索したパスをメモするために使用されるグローバル変数（これは正しくないことを知っています）を反復処理することにより、現在のプレイ内ですでに訪問した正方形のリスト（ボードを表す文字列内のインデックス番号のリスト）を作成しようとしました。ただし、以下を使用してこれらの値で変数を初期化するだけです。

再帰関数内でfind_bwords、何らかの形でインデックス変数に影響を与えi、find_bwordsの最後の行に由来するIndexErrorsを引き起こします。

紹介する前のインデックスのプリントアウトの一部を次に示しますprev_ind。

そしてここに後の部分があります：

なぜこうなった？

明確にするために、私はこの割り当ての解決策を探していません。別の方法で解決しました。この場合に何が起こっているのかを理解したいだけです。

だから私はJavaでBoggleプログラムに取り組んでおり、可能なすべての単語を見つけるのに苦労しています。

それらのほとんどすべてを見つけますが、私の人生では、なぜそれらすべてを取得できないのかわかりません。

これが問題の方法です。Boggle ボード上の単語を再帰的に検索します。

単語の約 75% しか見つからない理由を知っている人はいますか?

必要に応じて、さらにコードを添付できます。

重複の可能性:
文字マトリックスから可能な単語のリストを見つける方法 [Boggle Solver]

私は次のようなString[][]配列を持っています

ArrayList で指定された単語を見つけるには、ArrayList をこの配列と照合する必要があります。単語を検索するときは、正の一致と文字の位置を取得する必要があります。helloたとえば、この場合は(0,0)、、、(1,1)およびです。(2,1)(3,1)(3,2)

文字ごとに移動し、最初の文字を見つけることに成功したと仮定するとl、プログラムはその隣の場所で次の文字 ( ) を見つけようとしますl。したがって、e、e、g、k、o、l、m、および i に対して一致する必要があります。これは、その周囲のすべての文字 (水平、垂直、斜め) を意味します。単語内で同じ位置を 2 回見つけることはできないため(0,0)、位置が 2 回一致するため(1,1)、、、、および(2,1)は受け入れられません。この場合、斜めの位置が許可されているため、両方が単語と一致しますが、位置を複数回使用できないという要件により、別の単語と一致する必要があります。(2,1)(3,2)(2,1)l

この場合も一致する必要があります

を検索しようとするとhelllo、一致しません。または一致しないかのどちら(x1, y1) (x1, y1)かです。(x1, y1) (x2, y2) (x1, y1)

この種の機能を実装するための最良の方法は何かを知りたいです。ArrayList に4x4String[][]配列と 100,000 ワードがある場合、これを行う最も効率的で簡単な方法は何ですか?

このボグルゲームのPythonチャレンジを学校で終わらせようとしています。そして、16個のランダムな文字でボードを作成するドローボード関数を作成しました。def関数を使用して、単語の長さに応じて、単語を入力してスコアを付けるようにユーザーに求めるにはどうすればよいですか？それが完了すると、ゲームは正しく動作するはずです。どんな助けでも大歓迎です:)

この問題を解決する再帰関数を実現しました。

• 文字 (A...Z) で構成された 4x4 マトリックスを使用すると、すべての文字について、 adiacent セルと斜めセルのみをたどることによって、すべてのn 長の単語を取得します。

私の関数のアイデアは、すべての文字をあらゆる可能な方向に再帰的に呼び出し、それが形成される文字列を連結することです。この文字列の長さがnになると停止します。すでに使用されている文字に戻るのを防ぐために、新しい可能性のあるすべての文字と使用されているすべての文字を比較する文字のクラスへのポインターの配列を作成しました。これを行うために、すべての文字に対して特別なクラスを作成しました。

これが関数です: (申し訳ありませんが、非常に長いです)

dirSu は、上 - dirGiu 下 - dirDx 右 - dirSx 左 - およびその他すべての対角位置を意味します

さて、3 文字の単語の関数を有効にすると、非常に高速です。4 文字: 行列の 1 文字あたりの計算時間は 0.028 秒、5 文字: 0.225 秒、6 文字: 1.891 秒、7 文字: 14.914 秒です。

関数を最適化して計算時間を短縮する方法はありますか? （または私のばかげた論理エラーを削除しますか？）どうもありがとう！

テストに使用したマトリックスは次のとおりです。

私はすべての速度テストにこれを使用し（頻度またはランダムに計算することなく）、これを使用すると（質問以来改善された再帰関数を使用して）、開始文字ごとに5、6、7文字のすべての単語を約90秒で取得します。4×4のマトリックスだけなのに言葉が多い！私が個人的にあなたにそれを送ることができれば、同じ問題に対するあなたの解決策も見るのは興味深いかもしれません. （こちらへの連絡方法がわかりません）

そのため、NetBeansIDEのJavaでBoggleソルバーを実行しています。実行すると、完全に実行するのに約2時間かかるため、10分ほどで終了する必要があります。私のコードに何か問題がありますか、それとも大幅に高速化する方法がありますか？

ここからこのメソッドを呼び出します。

編集：ところで、私はGUIを使用しており、ボード上の文字はJLabelを使用して表示されます。