26

金曜日の午後です。楽しいパズル/アルゴリズムの問​​題を解決しましょう。

私のお気に入りのニンテンドー DS ゲームの 1 つは、ピクロス DSです。ゲームは非常にシンプルで、ノノグラムと呼ばれるパズルを解く必要があります。ここで簡単なオンライン ピクロス クローンを試すことができます: TylerK's Picross .

ノノグラムはグリッドであり、グリッドのすべての行と列に対して一連の数値が定義されています。数字は、その行/列の「塗りつぶされた」正方形のブロックを定義しますが、ブロックの両側の塗りつぶされていない領域は定義されていません。たとえば、次のような行があるとします。


(出典: steam-punk.net )

その行の考えられる解決策は次のとおりです。


(出典: steam-punk.net ) (出典: steam-punk.net )

等

「4 5」は、行のどこかに、4 つの連続したブロックが埋められ、その後に 5 つの連続したブロックが埋められていることを示しています。定義されていません。

すべての行と列が定義を満たし、矛盾がなければ、パズルは完成です。

コンセプトは非常に単純なゲームですが、手動で解決するにはかなりの時間がかかる場合があります。ピクロス DS のパズルは、最大 25x20 グリッドまで徐々にサイズが大きくなり、通常、解くのに約 30 分かかります。

しかし、解決するプログラムを書くのはかなり簡単なゲームになるだろうといつも思います。私はそれに慣れたことはありませんが、おそらくここにいる何人かの人々は挑戦を楽しむでしょう. かなりの数の解決策が投稿された場​​合、Paolo Bergantino が Boggle question でここで行ったのと同様に、相互に大きなパズルでそれらをベンチマークします。ウィキペディアのノノグラムのページには、パズルを攻撃する方法に関するかなりの情報があります。参照したい場合は.

これは、TylerK の Picross からのパズル #1 の解析しやすい定義です。これで、プログラムにフィードするものが得られます。行 1 はパズルの寸法 (おそらく不要)、行 2 は行の定義、行 3 は列の定義です。これは最初に頭に浮かんだことなので、誰かがより良い入力形式を考えられる場合は、お気軽にコメントするか、この投稿を編集してそれを含めてください。

15 15
15,4 5,2 4,1 3,2,2,2 4 3,2 6 2,2 1 6 2,2 1 1 4 2,1 1,1 3 2 1,2 2 1 2 1,3 3 2 1,9
4 4,3 1 2 3,2 1 2 2,2 1 1,1 4 2,1 3,1 8,1 3 1 1,1 4 2 1,1 4,2 4 3,3 3 3,4 1,10 3,10
4

10 に答える 10

22

はい、問題は NP 完全ですが、それは、パズルのサイズが大きくなるにつれて実行時間が指数関数的に増加することに (かなり) 悩まされていることを意味するだけです。しかし、実際にはパズルのサイズは大きくなりません。100x100 より大きいパズルを作成しようとする人はほとんどおらず、大部分は 50x50 より小さいです。本や雑誌に掲載されているパズルの 95% を一瞬で解くソルバーを構築することは、実際には特に難しいことではありません。かなり単純な深さ優先検索システムがそれを行います。

あまり明白でないのは、非常に厄介で、ほとんどの単純なソルバーの実行時間を爆発させる原因となるパズルがごく一部あることです。これらのほとんどは、人間が解決するのが困難または不可能な、設計の悪いパズルですが、ほとんどの AI プログラムが管理できるよりも深い洞察を使用して、経験豊富な人間の解決者が容易に解決できる特に巧妙なパズルもあります。

ほとんどのパズルを非常に迅速に解決する独自のソルバーを作成し、パフォーマンスを比較するベンチマーク結果を使用して他の多くのソルバーの調査を行いました。また、興味深いクラスのハード パズル (ドミノ パズル) についても説明します。これは、賢い人間には難しくないパズルが、ほとんどのプログラムでは非常に難しいことが証明されていることを示しています。マイ ソルバーとドミノ パズルへのリンクはアンケートに記載されています。

まだまだ改善の余地があると思いますので、斬新なアイデアをお持ちの方はぜひ挑戦してみてください。しかし、明らかなことはすでに行われており、それらを再び行うことにはあまり意味がないことに注意してください。

于 2010-10-08T15:21:28.243 に答える
6

ノノグラム ソリューションが存在する/一意であるかどうかを判断することは NP 困難です。http://en.wikipedia.org/wiki/Nonogram#cite_note-0を参照

于 2009-05-01T23:04:18.350 に答える
4

「最初の」行を配置しようとするのではなく、「最も制限された」行または列から情報を取得しようとすると、検索が大幅に削減されます。簡単な目安としては、行/列のすべての値を合計し、#_of_values - 1 を加算してから、そのような値が最大の行/列を探します (または、この値と行または列の数との差が最小の場合は、行と列が異なります)。したがって、25x25 のパズルがあり、行の 1 つが「5 1 1 6 1 1 3」である場合、その行の値は 24 になります。これは、非常に制約されていることを意味します。つまり、空白の正方形の 1 つを除くすべての相対位置です。その行は既知であり、最後の空白の正方形は 8 つの異なる相対位置のいずれかにある可能性があります。したがって、塗りつぶされた正方形の各グループには、次の 2 つの可能性しかありません。余分な空白の四角がこのグループの左側にあるか、余分な空白の四角がこのグループの右側にあります。したがって、たとえば、その 6 つのグループの塗りつぶされた四角形のうちの 5 つが既に知られています。

一方向からいくつかの強制値を取得すると、既知の情報と交差する他の方向からのグループがさらに制限されます。したがって、最良のアプローチは、より多くの情報が知られるにつれて、列と行の間を行き来することである可能性が高く、これはほとんど手動で解決する必要がある方法です.

于 2009-05-02T01:11:32.193 に答える
3

本当の問題は、このパズルを人間よりも速く解決するアルゴリズムを誰かが思いつくことができるかどうかです。これは、リファレンス パズルなどの比較的簡単なパズルでは簡単ですが、パズルが大きくなると、ここでのほとんどのアルゴリズムはすぐに遅くなります。これが私が解こうとしたパズルです。問題は、たとえば 4 行目に 2220075 の可能な組み合わせがあることです。チャーリーのアルゴリズムが一時的に行 3 の間違った行を受け入れると、行 4 のこれらすべての組み合わせを通過します。これは、アルゴリズムが行 2 で犯した間違いをめぐって行 35 で矛盾する場合は言うまでもありません。

私のアルゴリズムはジョンのアルゴリズムに似ていました。私の 64 ビット デスクトップでは、x86 モードで実行できませんでした。64 ビット モードに切り替えて一晩実行したところ、午前中にコンピューターがまったく使用できなくなりました。プロセスは 8 ギガのメモリ (デスクトップでは 8 ギガの物理メモリ) を予約していましたが、コンピュータは必死のスワッピングのために応答しませんでした。そして、すべての可能な行を解決していませんでした。言うまでもなく、可能な列の組み合わせにも触れていませんでした。

List<List<int>> rows =
                new List<List<int>>()
                {
                    new List<int> { 8,29,4 },
                    new List<int> { 6,4,25,4,3 },
                    new List<int> { 5,3,2,3,9,4,2,1,3 },
                    new List<int> { 4,2,2,2,2,1,2,2 },
                    new List<int> { 4,1,1,9,10,2,2,1 },
                    new List<int> { 3,2,6,5,5,1,1 },
                    new List<int> { 3,1,5,5,1,1 },
                    new List<int> { 3,1,4,4,1,1 },
                    new List<int> { 3,1,4,4,1,1 },
                    new List<int> { 3,1,3,3,1,1 },
                    new List<int> { 3,1,3,6,2 },
                    new List<int> { 3,1,2,3,2,4,2 },
                    new List<int> { 4,3,1,8,7,1,2,3 },
                    new List<int> { 4,2,1,12,11,1,2,4 },
                    new List<int> { 5,1,2,7,2,2,6,1,1,4 },
                    new List<int> { 4,1,1,1,6,2,2,6,1,2,1,3 },
                    new List<int> { 4,1,1,2,4,3,4,3,1,1,1,1,3 },
                    new List<int> { 4,1,1,2,1,4,1,2,3,2,1,2,2 },
                    new List<int> { 3,1,1,1,2,5,6,1,1,1,3,2 },
                    new List<int> { 3,2,1,1,2,1,5,4,4,2,1,2,1,2 },
                    new List<int> { 3,2,2,1,1,4,2,2,3,1,1,2,1,1,2 },
                    new List<int> { 3,1,3,2,1,1,4,1,5,3,2,1,3,1,2 },
                    new List<int> { 3,1,2,1,2,1,3,7,4,1,4,2,2 },
                    new List<int> { 2,1,4,1,1,1,2,6,2,2,2,3,2,1 },
                    new List<int> { 2,2,4,1,2,1,2,5,2,1,1,3,2,1 },
                    new List<int> { 2,2,1,4,1,1,3,3,2,1,4,4,1 },
                    new List<int> { 2,3,3,2,1,3,3,7,4,1 },
                    new List<int> { 2,3,2,4,5,8,1,2,1 },
                    new List<int> { 1,1,3,11,6,7,1,3,1 },
                    new List<int> { 1,1,2,2,13,10,2,3,2 },
                    new List<int> { 1,2,3,1,6,1,1,7,1,5,2 },
                    new List<int> { 1,1,3,2,6,1,1,1,1,4,1,4,2 },
                    new List<int> { 1,1,6,7,2,4,2,5,6,1 },
                    new List<int> { 1,1,2,3,1,4,2,2,11,2,1 },
                    new List<int> { 1,1,1,1,2,1,5,10,1,1,1 },
                    new List<int> { 1,1,1,1,4,7,4,10,1,1,1 },
                    new List<int> { 1,2,1,1,28,1,1,3 },
                    new List<int> { 1,2,1,2,27,2,1,3 },
                    new List<int> { 1,1,1,1,26,1,1,1,1 },
                    new List<int> { 2,3,1,28,2,1,2,1 }
                };
            List<List<int>> cols =
                new List<List<int>>()
                {
                    new List<int> { 40 },
                    new List<int> { 28,1 },
                    new List<int> { 23,8 },
                    new List<int> { 5,6,7,4 },
                    new List<int> { 3,6,1,9,3,1 },
                    new List<int> { 2,3,2,5,4,2,2 },
                    new List<int> { 1,2,4,1,2,5,2 },
                    new List<int> { 1,1,4,9,2,3,2 },
                    new List<int> { 2,4,2,6,1,4,3 },
                    new List<int> { 1,4,1,3,4,1,6 },
                    new List<int> { 1,4,3,2,3,5,5 },
                    new List<int> { 2,4,1,2,3,4,1,3 },
                    new List<int> { 1,2,3,4,2,2,4,4,1 },
                    new List<int> { 1,1,2,3,2,1,4,2,4 },
                    new List<int> { 2,3,5,3,3,5,4 },
                    new List<int> { 3,1,6,1,2,5,5 },
                    new List<int> { 3,2,6,2,15 },
                    new List<int> { 3,1,8,2,13 },
                    new List<int> { 2,2,4,5,15 },
                    new List<int> { 2,2,2,2,22 },
                    new List<int> { 2,1,1,1,12,6 },
                    new List<int> { 2,1,10,4,5 },
                    new List<int> { 3,1,3,1,2,4 },
                    new List<int> { 3,1,1,4,3,1,4 },
                    new List<int> { 3,2,2,3,2,2,5 },
                    new List<int> { 3,1,1,5,1,1,5 },
                    new List<int> { 3,1,1,5,1,1,5 },
                    new List<int> { 3,1,1,5,1,1,5 },
                    new List<int> { 3,2,5,2,1,1,4 },
                    new List<int> { 3,1,1,3,2,2,4 },
                    new List<int> { 3,1,6,4,5 },
                    new List<int> { 2,2,12,2,6 },
                    new List<int> { 2,2,1,1,22 },
                    new List<int> { 2,1,2,2,5,15 },
                    new List<int> { 3,1,4,3,2,14 },
                    new List<int> { 3,1,7,2,1,13 },
                    new List<int> { 3,2,6,1,1,6,8 },
                    new List<int> { 3,2,5,2,2,4,7 },
                    new List<int> { 2,1,2,4,1,1,1,4,1,4,2 },
                    new List<int> { 1,1,4,4,3,1,4,5,1 },
                    new List<int> { 1,1,5,1,1,2,1,2,2,3,2 },
                    new List<int> { 1,5,2,2,1,5,5,3 },
                    new List<int> { 1,6,2,1,4,2,6,1 },
                    new List<int> { 1,6,2,6,5,2 },
                    new List<int> { 1,5,3,1,9,2 },
                    new List<int> { 2,2,4,2,6,3 },
                    new List<int> { 1,2,2,2,9,2,1 },
                    new List<int> { 3,5,5,8,4 },
                    new List<int> { 4,13,9 },
                    new List<int> { 27,2 }
                };

著作権は Tampere Guild of Information Technology / Kaisapais / フィンランドの醸造所に帰属します。

于 2009-05-02T08:58:56.453 に答える
2

これは、「n queens」の問題と同様に、バックトラックを使用した深さ優先探索の非常に明白なケースのようです。キュートな部分は、行/列を配置するだけでなく、ブロックをシフトできることです。

さて、ここに概要があります。

  1. 空のボードから始めて、最初の行を配置します

  2. 次に、そのボードで2番目の行を配置し、列の制約と照合します。合格した場合は、その状態に対して次の行を再帰的に試行します。合格しない場合は、その行の次の可能な配置を試してください。

  3. 制約を満たす行の可能な配置が不足した場合はいつでも、パズルに解決策はありません。そうでなければ、あなたが列を使い果たしたとき、あなたは問題を解決しました。

これらの行を2進数として扱うことができると便利なので、可能性には自然な順序があります。

于 2009-05-01T22:27:26.427 に答える
1

今は解決策を具体化するのに十分な時間はありませんが、これが私がそれに取り組む方法です。

"function1" は、上部または側面の数字の制約、および既に塗りつぶされた正方形と空になった正方形を考慮して、行または列の可能な組み合わせを決定します。

"function2" は function1 からの出力を論理的に取得し、すべての結果をまとめて - 1 のスポットを埋めることができます。

"function3" は function1 からの出力を取得し、論理的に、またはすべての結果をまとめて取得します。ゼロのスポットは空にすることができます。

ボックスが空になったり埋められたりしなくなるまで、function2 と function3 をすべての行と列に適用し続けます。パズルが解けたら完了です。

パズルが解けない場合は、可能性が最も少ない行または列を取り、最初の可能性を適用します。次に、function2 と function3 を新しいボードに適用します。矛盾 (行または列の可能性が 0) につながる場合は、可能性の適用を解除して、別の可能性を試してください。解決策が見つかるまで、このように再帰を続けます。

于 2009-05-01T22:04:19.943 に答える
1

数ヶ月前、私は C++ でノノグラムのソルバーを書きました。影付きのセルと空白のセルの許容されるすべての位置を探すだけです。そして、すべての解決ステップで、すべての位置が問題ないかどうかを調べます。チャド・バーチのタイミング付きノノグラムの結果は次のとおりです: http://i.stack.imgur.com/aW95s.png .

そして、Mikko Rantanen の nongram のソルバーも試してみました: http://i.stack.imgur.com/o1J6I.png。

于 2014-07-26T18:24:47.513 に答える
0

これが私が見つけたものです：

NP Complete の問題はすべて同じ感じです。 残りのケースの次の 80% を解決するのは常に簡単です。たとえば、ナノグラムは 1 行に分解されます。ルーチンを作成してsolve_one_line(old_state, line_definition, new_state)、1 行についてわかっていることを更新し、行と列を繰り返し処理することができます。その後、いくつかのケースで失敗するので、それらのケースの 80% を解決する何かを書きます。次に、乱数を追加して、これまでに見つけたすべてのケースを解決しますが、最適に悪いケースを構築することは可能です。

このパターンに続く他のゲームは、MineSweeperとSodukuです。

並行して考えるのは難しいです。たとえば、solve_one_line上記のルーチンが行で実行されている場合は別の行に影響を与えず、列で実行されている場合は別の列に影響を与えないことがわかるかもしれません。

これで次のようになります。

  all_until_completion(rows):
      solve_one_line(...)
  all_until_completion(cols):
      solve_one_line(...)

これにより、データのロックなどを行わずに (20x20 で) 20 コアを実行できます。次に、各セルにプロセッサを搭載したグラフィックス カードで実行することを考えます。その後、どれだけの時間が経過したかに気付きます。

あるとき、現代のコンピューター サイエンスの教科書を見て、 O(n)表記がO(n, p)表記に置き換えられていると感じたことがありました。8 クイーン ソリューションは、高速フェイル、効率的なメモリ使用を備えた優れた高速再帰アルゴリズムであり、1 つのプロセッサでのみ実行されます。

問題は遊びの良い言い訳です。同じものをさらに磨くのは退屈です。より多くの経験が必要なテクノロジのリストに目を通してください。動作駆動テスト。依存性注入; 純粋な関数型プログラミング; ニューラルネット; 遺伝的アルゴリズム; 速くてずさんで制御不能。GPGPU; OCR; 例主導の学習; クラウドソーシング; など。 1 つを選択し、問題を解決するために何らかの方法で使用してみてください。問題を解決することが目的ではなく、未知の領域をさまようことが目的の場合もあります。

何か貢献してください。* これは簡単な書き込みでもかまいません。他の人がプレイできるように、数百ナノグラムのリポジトリの方が良いかもしれません. [リポジトリが存在する場合はお知らせください。存在しない場合は作成します]。 いいものを見つけたらすぐに貢献を始めましょう。クリンゴンの言葉に注意してください。 おそらく今日は死ぬのに良い日です。私たちはそれを出荷すると言います。

ですから、NP 問題に対する奇妙で並列的な解決策を書き、それらを共有してください。そして、素晴らしい一日を！

于 2016-04-21T17:40:58.043 に答える
0

古典的なノノグラム パズルの 2 つの興味深いひねりを指摘させてください。

  • パズルが占有セルの長さをリストするだけではありません。この公の挑戦は、いくつかのセルを占有されているものとして事前に制約しました: http://www.gchq.gov.uk/press_and_media/news_and_features/Pages/Directors-Christmas-puzzle-2015.aspx

  • ノノグラムに空/占有セル以上のセルが含まれているが、異なる色のパッチを使用してセルを占有している場合。たとえば、http://onlinenonograms.comを参照してください。これらを手で解いてみると、実際には通常のノノグラムよりも簡単に解ける気がします。

アルゴリズム設計者にとっての特定の課題は、色付きのノノグラムが、水平/垂直の制約を一緒に考慮することから大きな恩恵を受けることです。ここでは、通常の行ごとのソルバーは明らかに不利です。

于 2016-01-04T11:32:29.390 に答える
0

Steven Simpsonは、JavaScript スクリプトを含むさまざまなバージョンで自由に利用できるノノグラム ソルバーを作成しました。彼はその Web サイトでアルゴリズムの詳細について説明しています (ここなど- 基本的に、彼は速度と完全性をトレードオフする一連のラインソルバーを使用しており、すべてのラインソルバーがいつ行き止まりに達したかを推測することで分割統治を組み合わせています。彼にはリンクもあります。ここにあるよりも広い範囲をカバーする他のアプローチに。

于 2011-07-02T22:37:32.890 に答える