Puzzle DE Programming

はじめに

今回はパズルの解法ではなく、パズルの性質のひとつである「偶奇性 (パリティ : parity)」について説明します。

●偶奇性とは？

パズルには奇数と偶数に場合分けできるものがあり、このような性質を「偶奇性 (パリティ)」といいます。簡単な例を示しましょう。次のパズルを考えてみてください。

[問題]

リバーシで用いる石を上図のように並べます。この中から 2 つの石を同時にひっくり返します。石は隣り合わせでなくてもかまいません。この操作を繰り返してすべての石を白にしてください。

実はこのパズル、解くことができません。なぜ解くことができないのか、偶奇性を使って簡単に証明することができます。

今、白石は 2 個あるので偶数です。石をひっくり返す場合、白石と黒石、白石と白石、黒石と黒石の 3 通りがあります。白石と黒石をひっくり返すと、白石と黒石の数は変わりませんね。白石は偶数個のままです。白石と白石をひっくり返す場合、白石が 2 つ減ることになります。この場合も白石は偶数個 (0 を含む) のままです。最後の黒石と黒石をひっくり返す場合、今度は白石が 2 つ増えることになり、この場合も白石は偶数個のままです。

このことから、どんな操作を行っても白石は偶数個にしかならないことがわかります。石は全部で 5 つあるので奇数個ですね。何回石をひっくり返しても、白石は奇数個にはなりません。したがって、このパズルは解くことができない、というわけです。

このように、偶奇性を使って解の有無をチェックすることができます。ただし、パズルによっては偶奇性を満たしているだけでは解けない場合があります。このような場合でも、パズルが「解けない」ことのチェックに偶奇性を使うことができます。

●ペグ・ソリテアの偶奇性

ペグ・ソリテア は、盤上に配置されたペグ（駒）を、最後にはひとつ残るように取り除いていく古典的なパズルです。ペグは次のルールに従って移動し、除去することができます。

• ペグは隣にあるペグをひとつだけ跳び越して、空いている場所へ着地します。
• 跳び越されたペグは盤上から取り除かれます。
• 移動方向は、ふつう縦横のみの 4 方向ですが、 ルールによっては斜め方向の移動を許す場合もあります。
• 同じペグの連続跳び越しは 1 手と数えます。

盤は今までに多数考案されていますが、33 穴英国盤、37 穴フランス盤、41 穴盤が有名でしょう。このペグ・ソリテアにも偶奇性があります。次の図を見てください。

図（左）は 33 穴英国盤と呼ばれるペグ・ソリテアです。黒丸がペグで白丸が空き場所を表しています。これを図（右）に示すような 3 つのグループに分けます。ペグ・ソリテアの場合、このグループに属するペグ数と全体のペグ数の偶奇性を使って、解の有無をチェックすることができます。

ペグをこのようなグループに分けると、1 回のペグの移動により、跳び元と跳び越されるペグのグループはペグ数がひとつ減少し、跳び先のグループのペグ数はひとつ増えることになります。たとえば、図（左）の状態からペグを 1 回移動させると、各グループのペグ数は次のように変化します。

グループ０：11（奇数）=> 11 - 1 = 10（偶数）
グループ１：10（偶数）=> 10 + 1 = 11（奇数）
グループ２：11（奇数）=> 11 - 1 = 10（偶数）
全体ペグ数：32（偶数）=> 32 - 1 = 31（奇数）

このように、ペグを移動するたびに各グループと全体ペグ数の偶奇性は反転します。しかしながら、グループ 0 とグループ 2、グループ 1 と全体ペグ数の偶奇性は、ペグを移動しても一致していることに注意してください。当然のことですが、これがとても重要な関係なのです。

ここで、最後にペグがひとつ残っている状態を思い浮かべてください。全体ペグ数は 1 で奇数になります。3 つのグループのうち、2 つのグループは 0 になるので偶数、残りのグループにペグがひとつ残るので奇数になります。偶奇性の一致関係は、ペグを移動しても変わることはありません。したがって、初期状態で 3 つのグループのうちどれか 1 グループだけが全体ペグ数の偶奇性と一致していなければ、ペグ・ソリテアを解くことはできないのです。

ただし、この関係を満たしているからといって、必ず解けるとはかぎらないことに注意してください。逆に、この関係を満たさなければ、解くことは絶対にできません。

33 穴英国盤の場合、各グループのペグは 11 個あるので、最初に取り除くペグがどれであっても、偶奇性の一致関係を満たすことになります。参考文献 6 の解析結果によれば、どのペグを取り除いても解くことができるようです。

では、次に示す 5 行 5 列盤のペグ・ソリテアはどうでしょうか。

図に示すように中央のペグを取り除いた場合、各グループの偶奇性は次のようになります。

グループ０： 8（偶数）
グループ１： 8（偶数）
グループ２： 8（偶数）
全体ペグ数：24（偶数）

この場合、全グループの偶奇性が全体ペグ数と一致しているので、解くことはできません。

ペグ・ソリテアの偶奇性について簡単に説明しました。参考文献 9 には、ペグ・ソリテアの詳しい説明がありますので、興味のある方は一読することをおススメします。

●15 パズルの偶奇性

今度は 15 パズルの偶奇性について調べてみましょう。15 パズルの場合、Puzzle DE Programming 数字の並べ替え で説明した「転倒数」を使います。まずは簡単な 8 パズルで考えてみましょう。下図を見てください。

ここで、数字は位置 A から始まって青線の経路 (A - B - C - F - E - D - G - H - I) に沿って並んでいると定義します。このとき、空き場所は無視してください。すると、完成形の並びは [1 2 3 6 5 4 7 8] となります。数字の順番が逆になっているところに注目してください。

数字が順番に並んでいる場合、各数字の左側には自分より大きな数字はありません。ところが、完成形では 5 の左側に 6 があり、4 の左側には 5, 6 があります。このように、数字の順番が逆になっている個数を数え、その総数を「転倒数」と呼びます。そして、転倒数が奇数の場合を「奇順列」といい、偶数の場合を「偶順列」といいます。完成形の場合、転倒数は 3 ですから奇順列になります。

次に、駒を動かすことで転倒数がどのように変化するか調べてみましょう。まず、青線の経路に沿って駒を動かす場合、転倒数が変化することはありませんね。次に、紫線に沿って駒を動かしてみます。下図を見てください。

たとえば、図 (1) のように駒 5 を動かしてみましょう。すると、数字の並びは [1 2 3 6 5 4 7 8] から [1 2 3 6 4 7 5 8] になります。駒 5 は 4 と 7 の 2 つの駒を跳び越したことになります。4 の左には 6 があり、5 の左側には 6 と 7 があるので、転倒数は 3 のままです。

後ろへ跳び越す場合、自分よりも大きな駒を跳び越せば転倒数は 1 つ減ることになり、小さな駒を跳び越せば 1 つ増えることになります。跳び越す 2 つの駒には、自分よりも大きな駒と小さな駒、大きな駒 2 つ、小さな駒 2 つという 3 通りの場合があり、転倒数の変化はそれぞれ 0, -2, +2 と偶数個になります。前へ跳び越す場合、これとは逆になることに注意してください。

次に、赤線に沿って駒を動かしてみます。図 (2) を見てください。この場合、駒を 4 つ跳び越すことになります。自分よりも大きな駒と小さな駒の数を (B, S) で表すと、(4, 0), (3, 1), (2, 2), (1, 3), (4, 0) の 5 通りがあります。後ろへ跳び越す場合、転倒数はそれぞれ -4, -2, 0, +2, +4 と偶数個になります。

けっきょく、跳び越す駒が偶数個であれば、転倒数の変化も偶数個にしかなりません。つまり、紫線と赤線どちらに沿って駒を動かしても、転倒数は偶数個しか変化しないのです。したがって、何回駒を動かしても奇順列は奇順列のまま、偶順列は偶順列のままであり、奇順列から偶順列へ、逆に偶順列から奇順列へ移行することはできない、というわけです。

15 パズルも 8 パズルと同様に考えることができます。次の図を見てください。

8 パズルと同様に、数字は位置 A から始まって青線の経路 (A - B - C - D - H - G - F - E - I - J - K - L - P - O - N - M) に沿って並んでいると定義します。すると、紫線に沿って駒を動かすと駒を 2 つ跳び越し、赤線に沿って動かすと 4 つ跳び越し、緑線に沿って動かすと 6 つ跳び越すことがわかります。けっきょく、15 パズルも跳び越す駒の数が偶数個しかないので、転倒数も偶数個しか変化しません。したがって、奇順列から偶順列へ、偶順列から奇順列へ移行することはできない、というわけです。

15 パズルの偶奇性について簡単に説明しました。参考文献 9 には、15 パズルの詳しい説明がありますので、興味のある方は一読することをお勧めします。