パ ズ ル Solver

概要

パズル問題を与えると解いてくれる 自作小物プログラムによる実演を紹介しています。 プログラムでパズルを解かせたいという単純な気持と、 自分も含めパズルを作りたいと思う人に、解や別解の有無のチェック等で、 役立つのではという思いがあります。

すべてHTMLとJavascriptで記述しています。 新たに何かをインストールする必要はなく、 お使いのブラウザの中で実行させることができます。 いくつかの新しい機能を利用していますので、 できるだけ新しい版のブラウザ上で動かして下さい (Internet ExplorerはVer.9以降を使って下さい)。 PC以外でもスマートフォンやタブレット上で動いてほしいと期待して作っていますが、 使い勝手は悪いでしょうし保証できるものではありません。

画面の構成はほぼ共通です。

• 最上部： タイトル
• 中央左側： 問題図・解いた結果図
• 中央右側： 問題作成用のメニュ
• 下部左側： コマンドメニュ
• 下部右側： 問題例のメニュ
• 最下部 (問題を解かせた時など)： メッセージ

使い方も似ています。 基本的な使い方は、

1. 問題を与えて (あるいは問題例を指定して)
2. “Solve”

です。 試してみれば容易に理解できると思いますが、 それぞれの注意点は (このページの下の方にある) 補足を見て下さい。

一覧

(*3) 正規の連珠の問題を「パズル」のカテゴリーに入れて紹介するのは 筆者自身にもいくらか抵抗がありますが、 「パズル」の本来の意味からは許容できるものとしてご容赦下さい。
(*4) 「連珠世界」1993.1と1994.7の坂田吾朗氏による記事中に関連話題があります。

履歴 　(今後も少しずつ増やしていく予定です)

補足

0a. 共通

• サイズが可変の問題では、 サイズ入力後に、あるいは問題例指定後に図が表示されます。
• 問題入力は、右側にある要素を指定して (指定された要素は記憶されます) 問題図中を クリック/タッチ します。
• 入力の訂正は、他の要素で上書きするか、あるいは メニュ中の 空白/×等 を指定してから問題図中を クリック/タッチ して消去します。
• 右にOKボタンがある場所での入力後は、 必ずOKボタンをクリック/タッチして下さい。
• 多少の問題チェックはしていますが、 整合性のない問題を与えた時の動作は保証できません。
• 解かせた時に最下段に No solution 等の表示が出た時は、 解がないことを示します。
• 解かせた時に最下段に表示される try# などは、 解を見つけるためにプログラムが“努力”した回数です。 人の解き方とは異なる方法を使っていることが多いので、 必ずしも難易度に比例しませんが、目安にはなるでしょう。
• 複数解の有無も調べるパズルでは、 Solveメニュの前に小さなチェックボックスが付いています。 これにチェックを入れると、2つの解を順番に表示してくれます (このプログラムをパズル作成支援に使う場合に便利な機能です)。
• “Reset”は、問題を解く前の状態に戻します。 問題を白紙化したい時は、ページの再読込みを使って下さい。
• ここで用いる解法の多くは、深さ優先探索 (バックトラック)、 あるいは幅優先探索を多かれ少なかれ使います。 問題によっては、時間的・空間的な理由で解を求められないことがあり得ます。

0b. 連珠の基本用語

ここには 連珠 (五目並べ) 関連のパズル・問題を多く載せていますが、 連珠に馴染みの薄い方のために、 連珠の基本用語の説明の簡略版をここに付けておきます。

連珠に興味をお持ちになった方は、 日本の連珠界の大元である 日本連珠社の ホームページ や、 各地の連珠会のホームページ (例えば、本Webサイト管理者の所属する東海連珠会の ホームページ )をご覧下さい。

1. 六路盤詰連珠 (四追い)

• 攻撃側の指定は、入力メニュの黒石・白石で指定します。
• 最短解の 1つを表示し終了します。 最短解やより長い解が複数あっても 1つの解だけを表示し、 解がない場合は最下段に No solution と表示します。
• ほとんどバックトラックだけで解いていますが、狭い盤ですので、 特殊な初期配置の時を除き、短い時間で解いてくれます。
• 禁手か否かの判定は正確に行なっています(と思います)。
• 問題例は、このサイトで紹介している d06, d15, d11, d14, m12aです。

2. 六路盤詰連珠 (追詰め)

• 攻撃側の指定は、入力メニュの黒石・白石で指定します。
• 勝ちに至る最後の四追いは長くても1手と数えます (詰連珠のルール)。 この意味で“最短解”の最初の一手を表示し終了します (注：下の項も参照)。 “最短解”やより長い解が複数あっても 1つの解だけを表示し、 解がない場合は最下段に No solution と表示します。
• ただし、ある種の状況 (防ぎ手の無駄な四ノビ、防ぎ手の四ノリ後の四、等) では、必ずしも“最短解”を求められていません。 また、攻撃側の最後の四追いでは無駄な四ノビをすることがあります。
• 最初の一手が示された後、 人が防ぎ手を指してから再び Solve で次の一手を示します。
• 手数上限を増やしつつバックトラックを行なう反復深化法を使うことで “最短解”を求めようとしています。
• ミセ手・含み手の発見、およびそれらの防ぎについては、 四追いの有無を判定基準にした単純な方法を使っています。
• 解がない場合、解が長い手数の場合、追い手の変化が多い場合などでは、 長い時間を要することが多々あります (いずれ改善したいのですが、できるかどうか)。
• 禁手か否かの判定は正確に行なっています (と思います)。
• 解を見落としたり、解がないのに“解”を見つけることは、 ありません (と思います)。
• 問題例は、このサイトで紹介している c249, c125, c200, c100, c012です。

3. 連珠・四追い問題

• 右下にある小さな黒/白石は、 次に入力される石の色、およびSolve指定時の攻撃側を表わします。 右上にあるメニュのクリックで変更します。
• メニュ欄にある左黒・右白の円は、黒白交互入力モードの指定です。
• ← → ↑ ↓ の各ボタンは、 問題図を左右上下に移動するものです。外にはみ出た部分は復元できません。
• 盤の下に表示される“----- (m,n)”は、盤上の黒石の数m、白石の数nです。
• “Solve”により、最短解の 1つを表示し終了します。 最短解やより長い解が複数あっても 1つの解だけを表示し、 解がない場合は最下段に No solution と表示します。
• 複雑な問題では、 最短解であることの確認に多くの時間が必要となることがあります。 “Solve(trace)”では、最短解とは限らないけれど解を見つける毎にそれを表示します。 ある解を表示した場合、次に表示されるのはそれより短い手数の解のみです。 “Solve”で解が表示されない場合は、“Solve(trace)”を試してみて下さい。 本当に難しい問題では、“Solve(trace)”でも結果を出さずに考え込むことでしょうが。
• 手順前後解の探索は省きつつ深さ優先探索 (バックトラック) 法で解いています。 変化の多い長い解の問題では、時間的理由から解けないことがあり得ます (いずれ改善したいのですが、できるかどうか)。
• 解がある時に表示される2種類の実行時間は、 最初の解(最短とは限らない)を見つけるまでと、 表示解が最短であることを確認するまでの時間です (いずれも開始時からの経過時間でCPU時間ではありません)。
• 問題例は、定石からとったもの1題と拙作です。

4. 連珠・4手五連問題

• 右下にある小さな黒/白石は、 次に入力される石の色、およびSolve指定時の攻撃側を表わします。 右上にあるメニュのクリックで変更します。
• メニュ欄にある左黒・右白の円は、黒白交互入力モードの指定です。
• ← → ↑ ↓ の各ボタンは、 問題図を左右上下に移動するものです。外にはみ出た部分は復元できません。
• 盤の下に表示される“----- (m,n)”は、盤上の黒石の数m、白石の数nです。
• 解がない場合、下部に“no Solution”のメッセージを出します。
  解がある場合、
  • 攻め手側の3個以下の石で勝てる場合、解を表示し、 “wins by 3 or less atacker moves”のメッセージを出します。
  • 4手五連のユニークな解がある場合、解を表示します。
  • 余詰めのある場合、1つの解を表示し、 “other solution(s) exist (x,y)”のメッセージを出します。 (x,y)は別解です。 2つ目の解を見つけた時点で探索を終了するので、 3つ以上の解があるか否かは不明です。
  いずれの場合も経過時間(単位：秒)を最下部に “m.m / n.n sec used”の形で表示します。ここで、
  m.m：最初の解を見つけるまでの時間
  n.n：全体の時間 (ユニーク解の場合は余詰めなしの確認時間となります)
  
• 解ではないが、解候補と考えられる点を下部に “(x,y) => (X,Y)”の形で表示します。ここで、 (x,y)：解候補、 (X,Y)：唯一の防ぎ手です。
  防ぎ手がユニークである場合に、解候補と(便宜的に)考えます。 ただし、四ノビはここでの解候補には含めません。
• 効率を考慮しつつ、しらみつぶし法で探索しています。 手数が限られていますので、どの問題も妥当な時間内に解きます。
• Resetボタンの押下で、用意されている問題を読み込んだ時点、 あるいは直前のSolveボタンを押した時点の局面に戻します。
• 盤上の点は (x,y) の座標で表わし、 x：左から右に1〜15、 y：上から下に1〜15 です。
• 問題例は拙作です (詰連珠は多く作ってきましたが、4手五連問題は初めて作りました)。

5. 連珠・5手五連問題

上記の「連珠・4手五連問題」のプログラムを単純に拡張しただけですので、 使い方等は上記をご覧下さい。 ただし、以下の点に注意して下さい。

• 一般に、解くのに多くの時間を要します。 特に解のない問題を解かせると、no Solutionと出るまでかなりの時間を要します。
• 終了までの時間を短くするためですが、 余詰めのチェックはせず1つの解を見つけた時点で探索を終了しています。 また、解候補の列挙はしていません。
• 5手五連問題の例は連珠専門誌にもほとんどありません。 「天空の城」(連珠世界2004.12) はある趣向を実現している興味ある例です。 ここに挙げた問題例は、通常の詰連珠として作った拙作の小作品で、 攻め手の5個以内の石で五連を作ることができるので代用しています。
• 4手五連問題を解くプログラムでは時間がかかりすぎる4手五連問題があった場合、 この5手五連問題を解くプログラムを使えば、 1つの解の表示だけですが、早く結果を出してくれるかもしれません。

6. ゴールは5

• 盤サイズは、6〜15の範囲で自由に設定できます
• 最初に見つけた最短解を表示し終了します。 最短解やより長い解が複数あっても 1つの解だけを表示し、 解がない場合は最下段に No solution と表示します。
• 手順前後解の探索は省きつつ幅優先探索で解いています。 変化の多い長い解の問題では、時間的・空間的理由から解けないことがあり得ます (いずれ改善したいのですが、できるかどうか)。
• 問題例は、例1は問題説明用に作ったもの、 例2は六路盤詰連珠コーナーにあるm13aで、 他は以前に連珠問題として作った小作品を転用しています。

7. ハノイの塔

• 円盤の枚数 1〜8 の数値を与えて見ているだけです。
• 最小移動回数の解を示しますが、 円盤が n 枚の時の最小移動回数は 2ⁿ-1 ですので、 n が大きい時はアニメーションの終了までそれなりの時間がかかります (中止はResetなどで可能です)。

8. ペントミノ

• 各ピースはその形に応じて F, I, L, N, P, T, U, V, W, X, Y, Z の名前がついています。
• ピース Xの中心位置を限定することで、対称解をかなり除去できます (問題図の形によっては完全に除去できます)。 ここでもピース Xの中心位置の範囲を指定できるようにしています (左上が (1,1) で、x座標は右方向に、y座標は下方向に進みます)。
• 左側から埋めていく単純な探索をしているため、 ピース Xの範囲を右側に指定したり、問題図を縦長にすると、 解の発見までの時間が長くなります。
• 一般に多くの解がありますので、表示する解の範囲を指定できるようにしています。 解の総数だけを求めたい時は、解の範囲の下限を大きな数にします。
• 問題図の作成では任意の図形を指定できます。 全体をカバーできる長方形を指定し、×で不要なセルを消していくのがよいでしょう。 全体の面積は60である必要があり、右下に現在の面積が表示されます。
• 問題例は、よく使われる長方形などを用意しています。
• (参考) 対称解を除いた解の総数は、 10×6 の長方形で2339、 12×5 で1010、 15×4 で368、 20×3 で2、であることが知られています。

9. 数独

• 解が2つ以上ある場合、2つ目まで調べ sol#=2 のメッセージを出して終了します。 チェックボックス中のチェック有無により解の表示が変わります。
• 2種類の戦術を軸にしつつバックトラックを使って解いています。 難しい問題でも短い時間で解いてくれます。
• 問題例は、ここに載せるために初めて作った拙作です。 難易度は、容易〜中程度でしょう。

10. 四角に切れ

• 解が2つ以上ある場合、2つ目まで調べ sol#=2 のメッセージを出して終了します。 チェックボックス中のチェック有無により解の表示が変わります。
• 2種類の戦術を軸にしつつバックトラックを使って解いています。 ほとんどの場合、短い時間で解いてくれます。
• ある種の状況が起こった時に人であれば使うであろう “大局的な観点”からの戦術や、 “特定部分に注目”しての背理法的戦術は組み込んでいません。 その種の状況が起こる問題では、時間的理由から解けない可能性があります (可能性はかなり小さいでしょうが、いずれ改善したいと思っています)。
• 問題例は、ここに載せるために初めて作った拙作です。 難易度は容易〜中程度でしょう。

11. カックロ

• ヒント値の入力では、 右上三角 (横行のヒント) か左下三角 (縦列のヒント) をクリック/タッチし、 ヒント値 (メニュ左列の0〜4が10の位、右列の0〜9が1の位) を指定し、 望みのセルをクリック/タッチします。 ヒント値のない壁セルを作るには、00をヒント値として上のようにします。
• 縦/横のヒントの一方だけを消去したい場合は、 上記方法で00をヒント値として与えます。 ヒント値の縦・横両方の消去は、 □ をクリック/タッチ後に消去したいセルをクリック/タッチします。
• 解が2つ以上ある場合、2つ目まで調べ sol#=2 のメッセージを出して終了します。 チェックボックス中のチェック有無により解の表示が変わります。
• 主戦術と2つの補助戦術を軸にしつつバックトラックを使って解いています。 難しい問題でも短い時間で解いてくれます。
• 問題例は、ここに載せるために初めて作った拙作です。 難易度は容易〜難でしょう。

12. お絵かきロジック

• 最初に、「問題 (行・列のヒント) を与えて解かせるモード (Solver)」と、 「絵から問題を作り問題として成立するかをチェックするモード (Maker)」の いずれかを選びます。
• いずれのモードでも、 最初にキャンバスの横幅と縦幅 (いずれも5の倍数) を与えます。
• Solver モードでは、ヒントを与える行/列を指定してから ヒントをスペースで区切って与えます。
• Maker モードでは、 ■/□を指定後にキャンバスの中をマウスボタンを押した状態でなぞって 答となる絵を作ります。 その後 saveInfo をクリックしてから「試しに解いてみる」で 問題をチェックする画面に移ります。 Maker モード画面にある ← → ↑ ↓ の各ボタンは、 画像を左右上下に移動するものです。外にはみ出た部分は復元できません。
• いずれのモードでも問題を解く画面では、 解が2つ以上ある場合、 2つ目まで調べ sol#=2 のメッセージを出して終了します。 チェックボックス中のチェック有無により解の表示が変わります。
• ヒントのブロック長に対応する範囲を狭め、 セルの状態を決定するためのいくつかの戦術を組み合わせつつ、 バックトラックを使って解いています。
• 人の解き方とは異なるので、 人なら進展が見込めるヒントに注目することで解けるが このプログラムでは解けない (非常に時間がかかる) 問題や、 逆に、プログラムでは解けるが人にはまず解けない問題もあり得ます。 問題を作り答のユニークさをチェックした後では、 自分でも解いて難易度を確認するのがよいでしょう。
• 問題例は、ここに載せるために初めて作った拙作です。 難易度は、容易〜難でしょう。

13. 波及効果

• 解が2つ以上ある場合、2つ目まで調べ sol#=2 のメッセージを出して終了します。 チェックボックス中のチェック有無により解の表示が変わります。
• 数字を与えるメニュに加え、線を引く/消すメニュもあります。
• ルールが定める制約条件を実現する基本戦術を使って各セルに可能な数を絞りつつ、 バックトラックで解いています。 それ以上の高等戦術は組み込んでいません。
• 高等戦術を多用しないと解けない非常に難しい問題の時を除き、 短い時間で解いてくれます。
• 整合性のない問題に対しては不安定な動作をするかもしれません。
• 問題例は、ここに載せるために初めて作った拙作です。 難易度は中〜難でしょう。

14. 美術館

• 解が2つ以上ある場合、2つ目まで調べ sol#=2 のメッセージを出して終了します。 チェックボックス中のチェック有無により解の表示が変わります。
• 多くのパターン知識を使いつつバックトラックも使って解いています。 例えば、ヒント値と隣接する空点との関係に関する知識、 2つのヒント値が縦・横あるいは斜めに隣接する場合の種々の知識、などです。
• 人なら使うであろういくつかのパターン知識を組み込んでいないため、 解を見つけるのに長い時間を要する問題もあり得ます (いずれ改善したいと思っています)。
• 問題例は、ここに載せるために初めて作った拙作です。 難易度は容易〜やや難でしょう。

15. のりのり

• 解が2つ以上ある場合、2つ目まで調べ sol#=2 のメッセージを出して終了します。 チェックボックス中のチェック有無により解の表示が変わります。
• ルールに基づく基本戦術に数種類のパターン知識による戦術を加え、 バックトラックを使って解いています。
• 難しい問題では、 ある種の“局所範囲に限定した”試行錯誤や、黒マスの存在だけを認定しての推論を 人であれば使うでしょうが、 それらは組み込んでいません。 多くの問題は短い時間で解きますが、難しい問題だと長い時間を要することがあります。
• 問題例は、ここに載せるために初めて作った拙作です。 難易度は容易〜難でしょう。 (例5を解くのにこのプログラムでは数秒〜数十秒かかります。 解の表示まで気長に待って下さい。)

JirKisホームページのトップへ