-1

たとえば、クロスワードグリッドがあります

+-----+
|  *  |
|     |
+-----+

と単語リスト

a
ababa
bb
cc
ba
bb
ca
cb

すべての単語を使用する必要があります。目標は、このクロスワードをどのように解決できるかをすべてのバリアントを見つけることです。この場合、2 つのバリアントがあります。

bb*cc
ababa

と

cc*bb
ababa

いくつかのより複雑なクロスワードは、たとえば次のようになります。

+-----+
|   * |
|     |
|    *|
|   * |
|  * *|
|  *  |
|     |
+-----+

20単語のリストなど

この種の問題を解決するアルゴリズムを作成しようとしましたが、成功しませんでした。誰かが私を助けることができますか？

4

1 に答える 1

0

最初に、与えられた辞書を使用してクロスワードが「解決可能」であるかどうかを判断することさえNP-Hard 1であるため、0 以上の解決策があるかどうかを判断することさえ多項式で行うことができないことに注意してください ( P=NP でない限り)。

したがって、別の方法は、徹底的な検索ソリューションを使用することです。単語を「配置」するためにすべての可能性を試してから、このソリューションが有効かどうかを確認してください。

擬似コード:

solve(words,grid):
   if words is empty:
       if grid.isValidSolution():
          print grid as a possible solution
          return
   for each word in words:
       candidate<- grid.fillFirstSpace(word)
       solve(words\{word},candidate)

(1) 参照: P は NPセクション 3.3と等しいか

于 2012-12-01T17:12:07.823 に答える