一筆書きパズルの判定法：解けるかどうかを見抜く
遊びを見つける執筆にClaudeを使用しています。
「この図形、一筆書きできる？」と問われたとき、何度試しても途中で詰まってしまうのに、なぜ解けないのかが分からない——そういう経験をしたことがある方は多いはずです。実は一筆書きが可能かどうかは、試行錯誤をしなくても図形を「見る」だけで判定できます。18世紀の数学者レオンハルト・オイラーが定式化した方法で、今でもパズルの設計や解析に使われているルールです。 この記事では、そのルールの仕組みと具体的な判定手順、そして「なぜそうなるのか」を一緒に説明します。ゲームをプレイしながら「解けそうか」を素早く見切る力が身につくことを目指しています。
一筆書きの可否を決める「次数」という概念
グラフ理論（点と線のつながりを研究する数学の分野）では、図形を「頂点（点）」と「辺（線）」で表します。一筆書きの判定で重要なのは、各頂点に何本の辺が接続しているかを表す「次数（じすう）」です。
次数が偶数の頂点を「偶数頂点」、奇数の頂点を「奇数頂点」と呼びます。一筆書きの可否はこの分類だけで決まります。
判定の結論を先に示します。
- 奇数頂点が0個のとき：一筆書きができ、どの頂点からスタートしても出発点に戻ってくる「一筆書き回路（閉路）」が成立します。
- 奇数頂点がちょうど2個のとき：一筆書きができ、その2つの奇数頂点が「スタート」と「ゴール」になります。
- 奇数頂点が4個以上のとき：一筆書きはできません。何度試しても必ずどこかで行き詰まります。
奇数頂点が1個または3個という状況は、理論上ありえません。理由は後述します。
なぜそのルールが成り立つのか
頂点を「通過する」場面と「出発・到着する」場面を分けて考えると分かりやすくなります。
ある頂点を経由するとき、必ず「入る辺」と「出る辺」がペアで使われます。つまり経由するだけの頂点は偶数本の辺を消費します。一方、スタート地点は最初に1本「出る」だけ、ゴール地点は最後に1本「入る」だけです。
- スタートとゴールが同じ頂点（回路）の場合、出発して戻ってくるので出入りの本数は偶数になります。すべての頂点が偶数次数のとき成立します。
- スタートとゴールが別の頂点の場合、その2頂点だけは奇数本使われ、それ以外の経由点はすべて偶数本使われます。奇数頂点がちょうど2個のとき成立します。
奇数頂点が4個以上あると、「奇数本使われる頂点」を2個しか割り当てられるスタート・ゴールのペアが足りず、どうしても通り残しが出ます。また、辺の本数を足したとき必ず偶数になる（各辺は2頂点に1本ずつ数えられるため）という性質から、奇数頂点の数は常に偶数個になります。1個や3個は理論上発生しません。
実際のパズルでの判定手順
理屈が分かれば、あとは手を動かすだけです。次の手順で判定できます。
- 図形をグラフとして描き直す。線が交わる点や線の端点を「頂点」とし、それぞれの頂点に何本の線が接しているかを数えます。
- 奇数頂点を数える。接続している線が1本・3本・5本……の頂点を全部数えます。
- 0個なら回路、2個なら一本道、4個以上なら不可能と判断します。4個以上の場合、一筆書きになるよう問題を修正したければ「奇数頂点のペアを辺で結ぶ」という方針が出発点になります。
たとえば正方形（4頂点・4辺）の場合、各頂点に2本ずつ辺が接しているので全頂点が偶数次数です。奇数頂点は0個なので、どこからでも一筆書き回路が完成します。
十字（＋）の形を一筆書きしようとするケースを考えます。中心の頂点には4本の辺が集まる（偶数）ので問題ありませんが、4つの端点にはそれぞれ1本だけ（奇数）。奇数頂点が4個になるため、一筆書きは不可能です。「＋字パズルを全部なぞって」と言われたら解けない、と即座に判断できます。
判定できない「落とし穴」に注意する
実際のパズルでは、グラフが複数の部分に分かれている（連結でない）場合があります。たとえば図形が完全に離れた2つのブロックに分かれていたら、奇数頂点の条件を満たしていても一筆書きはできません。オイラーの条件は「グラフが連結である（どの頂点からでも他の全頂点へ行ける）」ことを前提としています。
パズルで判定を誤りやすいのは次の2点です。
- 交差しているように見えて実際は別の点：平面上で線が交わって見えても、その交差点が頂点として定義されていない場合、次数の計算には含めません。問題の設計を確認する必要があります。
- 同じ辺を複数回通れるかどうか：一般的な一筆書きパズルは「各辺を1回だけ通る」というルールですが、「各頂点を1回だけ通る」問題（ハミルトン路）はまったく別の話です。見た目が似ていても判定ルールが変わるため、問題文を読んで区別します。
ゲームで役立てるための視点
ブラウザ上の一筆書きパズルを遊ぶとき、このルールをどう使うかを考えてみます。
まず、ステージが始まった瞬間に奇数頂点の数だけを確認します。0個か2個でなければ「このステージは解けない設計になっている」か、「自分がグラフを誤読している」かのどちらかです。よくできたパズルゲームなら必ず解けるように設計されているので、判定で「不可能」という結論が出たときは、頂点と辺の読み取り方を見直すサインだと考えてください。
奇数頂点が2個のとき、スタート位置を選べる問題ではその2頂点のどちらかから必ず始めなければなりません。逆に言うと、奇数頂点ではない頂点からスタートした試みはすべて失敗に終わるので、早めに切り上げて出発点を変えることができます。これだけで無駄な試行が大幅に減ります。
解き方の手がかりを絞りたいときは、「奇数頂点から出発し、もう一方の奇数頂点で終わるルートを意識する」というだけで選択肢がかなり狭まります。残りは経路の順序を試行錯誤する問題になり、少なくとも「どこからスタートするか」という最初の迷いはなくなります。
次の行動
次に一筆書きパズルを見かけたときは、解く前に30秒だけ各頂点の次数を指で数えてみてください。奇数頂点が何個あるかを把握してからプレイすると、試行の質が変わるのを実感できます。アソバースには一筆書き系のパズルを含む作品も公開されているので、判定の練習場として活用してみてください。
参考資料
- オイラー路・オイラー閉路（グラフ理論）に関する数学教科書・大学講義資料
- レオンハルト・オイラー「ケーニヒスベルクの橋の問題」原論文（1736年）の解説資料
