パズルの解法

パズルの自動生成やアドバイスを行うためには、アプリの内部でパズルを一度解く必要があります。ここでは、パズルを解く際に本アプリが使用する方法を説明します。 使用されている用語に関してはこちらのページを参照してください。

パズルの解き方

パズルを解くのは、概ね以下のようなステップで行います。

1）初期探索

まず最初に、複数の数字の並びやコーナーに置かれた数字から、一部のエッジの状態を確定します。ここで使用される具体的なパターンに関しては「付録A 初期配置パターン」をご覧ください。

2）探索ループ

続いて、状態の確定した要素の周辺で（１手仮置きの場合は盤面全域で）、連鎖的に確定する要素がないかを、基本解法以下の解法を順に実施することでチェックします。
１つでも確定できる要素が見つかれば、その要素を確定し、再度基本解法からの探索に戻ります。
可能なすべての解法を利用しても確定する要素が全く見つからない状態になると、そのパズルは解けない、ということになります。
確定する要素の探索に利用する解法には、以下のようなものがあります。

基本解法

セルの数字と周辺のエッジの状態、あるいはノードと接するエッジの状態（接するエッジの中でONのものの数は0か2でなければならない）に基づいて、エッジの状態を確定します。具体的な解法は「付録B 基本解法パターン」をご覧ください。

斜めゲート

ゲートと関連するエッジの状態から、未確定のエッジや、他のゲートの状態が確定できることがあります。この性質を利用して確定要素を探します。具体的な解法は「付録C 斜めゲート解法」をご覧ください。

セルの色

隣り合った２つのセルの色と間のエッジの状態から、未確定のセルの色や他のエッジの状態が確定できることがあります。この性質を利用して確定要素を探します。具体的な解法は「付録D セルの色の解法」をご覧ください。

１手仮置き

まだ未確定なエッジの1箇所を、仮にONにしてみます。その後、他の解法を利用してパズルを解き進めていき、結果的に矛盾が発生する場合、そのエッジはOFFに確定します。
矛盾が発生しないまま次に確定する要素がみつからなくなった場合、またはそのまま解けてしまった場合には、今度は仮にOFFにしてみます。 ONのときと同様にそのまま解き進めると矛盾が発生する場合はONで確定します。また、ONのときと同じ状態に変化するエッジが見つかった場合には、そのエッジの状態が確定します。矛盾が発生せず、ONと同じ状態になるエッジも持つからなかった場合にはそのエッジは1手仮置きでは確定しないことになります。
これを確定するエッジが見つかるまで、すべての未確定のエッジで試してみます。
（仮置きで完成しても確定としないのは、他にも条件を満たすループが見つかる可能性があり、その場合その問題は不正となるからです）

領域出入

盤面のある部分だけを見た場合に、その部分に入ってくるONのエッジの数は、最終的には必ず偶数になります。この性質を利用して確定するエッジを探します。