1

特定のクロスワードを作成するタスクがあります。すべての答えが示されていますが、その場所は不明です。プログラムは、次のようなボード スキームでファイルを読み取る必要があります。

0 1 0 0 0 0 0 0 1 0 0
0 1 0 1 1 1 1 1 1 1 1
0 1 0 1 0 0 1 0 1 0 1
0 S 1 1 0 1 1 1 1 0 1
0 1 0 0 1 0 1 0 1 0 0
1 1 1 1 1 1 1 S 1 1 0
0 0 0 0 1 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0

1 の各列/行を 1 つの可能な答えとして扱います。このファイルを解析して、フィールドごとに gazilion if を使用せずに回答をマークする方法はありますか? 残りのロジックは次のとおりです。
- 解析されたファイルに基づいて、クロスワードが作成されます。
- ユーザーが可能性のリストから回答を選択する - ユーザーが回答
の最初のブロックをクリックし、選択した回答と回答の長さと文字が一致する場合 - フィールドが更新される

ゲームボードは私が推測する2次元配列に格納する必要があり、各回答にはフィールドのインデックスが必要ですか?

4

1 に答える 1

3

クロスワード パズルの構築は、一般に NP 完全です (つまり、1 と 0 の nxn ボードと、そこから答えを選択するための特定のセット)。見てください：http://en.wikipedia.org/wiki/List_of_NP-complete_problemsこれについて言及しています。ゲイリーとジョンソンの古典的な本にもこれについての言及があり、3セットによる正確なカバーはそれに減らすことができると言っています.

したがって、グリッドを埋めるためにバックトラッキング/ヒューリスティックを使用する必要があるでしょう。

おそらく、ダートマス大学の 2 人の学生によるこのプロジェクト レポートが役立つでしょう:クロスワード パズル ジェネレーター. これには、使用できるいくつかのヒューリスティックが含まれています。

もちろん、人間が関与していることを暗示しているようですが、その人を利用してグリッドを埋めることができるかどうか、および問題が基本的にユーザーを支援する際の UI プログラミングの問題であるかどうかは明確ではありません。

于 2010-06-20T19:11:35.733 に答える