数学の部屋へもどる
15パズルは、4×4のセルに置かれた、1から15までの数字が書かれた15個のピースを一つずつずらして特定の順序に並べ替えるパズルです。
これは、1878年にアメリカのパズル作成家Sam Loydにより発明され、彼はある問題に懸賞金をかけていました。
しかしその翌年、その問題は解けないことが数学者により証明されてしまいました。
|
●青木注： この辺りの事情は『スライドゲームPart２』でも取り上げました。 １５パズルはこのページの一番下にあります。 |
では、このパズルはどのようなときに解け、どのようなときに解けないのでしょうか。
ここでは少し一般化して、m×nの場合を考えてみましょう。
まず用語を定義します。
◆定義1.
m,nを3以上の整数とし、
m×nのセルに1からmn-1までの数字が書かれた
mn-1個のピースが置かれているとする。
このときこの並びをm×n「配置」といい、横、縦の並びをそれぞれ「行」、「列」という。
またピースの置かれていないセルを「空セル」といい、空セルに隣接するピースを空セルにずらすことを「移動」という。
そして有限回の移動により別の配置を得ることを「変形」という。
さらに、ピースが左上から行を優先にして書かれた数字の順に並び、右下に空セルがある配置を「標準形」といい、標準形に変形される配置を「可解」であるという。
ではまず、与えられた配置はどのくらい標準形の近くまで変形されるでしょうか。
初めから一般の場合では難しいので、最も簡単な場合を考えてみましょう。
【問題１】
任意の3×3配置は次の配置に変形されることを示せ。
| １ | ２ | ３ |
| ４ | ５ | ＊ |
| ７ | ＊ |
ただし、[*]は[6],[8]のいずれかを表す。
それでは実際にやってみましょう。
Joel Fan，Eric Ries，Calin Tenitchi著
「Ｊａｖａゲームプログラミング」 翔泳社にこのゲームを見つけたので紹介します。
◆３×３ゲーム
Randomizeボタンをクリックすると、ピースの並び方が変わります。
ピースをクリックすると、動きます。
（同時に同じ行や列の複数のピースを動かすこともできます。）
ピースを最初の並び方にもどせば完成です。
（笑い声がでます）
次に少しこれを一般化してみましょう。
【問題２】
mを3以上の整数とする。
任意のm×3配置は次の配置に変形されることを示せ。
| １ | ２ | ３ |
| ４ | ５ | ６ |
| ７ | ８ | ９ |
| : | : | : |
| 3m-8 | 3m-7 | 3m-6 |
| 3m-5 | 3m-4 | ＊ |
| 3m-2 | ＊ |
ただし、[*]は[3m-3],[3m-1]のいずれかを表す。
今度はさらにこれを一般化してみましょう。
【問題３】
m,nを3以上の整数とする。
任意のm×n配置は次の配置に変形されることを示せ。
| 1 | 2 | 3 | ... | n-2 | n-1 | n |
| n+1 | n+2 | n+3 | ... | 2n-2 | 2n-1 | 2n |
| 2n+1 | 2n+2 | 2n+3 | ... | 3n-2 | 3n-1 | 3n |
| : | : | : | ... | : | : | : |
| (m-3)n+1 | (m-3)n+2 | (m-3)n+3 | ... | (m-2)n-2 | (m-2)n-1 | (m-2)n |
| (m-2)n+1 | (m-2)n+2 | (m-2)n+3 | ... | (m-1)n-2 | (m-1)n-1 | ＊ |
| (m-1)n+1 | (m-1)n+2 | (m-1)n+3 | ... | mn-2 | ＊ |
ただし、[*]は[(m-1)n],[mn-1]のいずれかを表す。
さて、任意の配置は”ほとんど標準形”に変形されることがわかりました。
では、与えられた配置が可解になるのはどのような場合でしょうか。
それを知るために少し準備をします。
●準備.
nを正の整数とし、集合{1,2,3,...,n}の上の全単射をn文字の「置換（順列）」という。
（すなわちn文字の置換とは、1からnまでの数字の並べ替えのことです。）
特に二つの元を交換するだけの置換を「互換」という。
任意の置換σは有限個の互換の積（合成）として表される。
その表し方は一意的ではないが、互換の個数の偶奇は一意的である。
そこで互換の個数が偶数のとき、「偶置換」といい、
sgnσ=1と記す。
また互換の個数が奇数のとき、「奇置換」といい、
sgnσ=-1と記す。
このとき任意の置換σ,τに対して、
sgn(στ)=sgnσsgnτが成り立つ。
ここでもう一度定義します。
◆定義2.
m×n配置Cに対して、Cのピースを左上から行を優先させて一列に並べ、
空セルをmnとして得られるmn文字の置換をCに「対応する置換」という。
（この言葉を用いれば、標準形は対応する置換が恒等写像である配置にほかなりません。）
またCの「符号」を次のように定義する。
s(C)=(-1)i+jsgnσ.
ただし、i, jはそれぞれ空セルの行、列の番号、σはCに対応する置換である。
このとき次が成り立ちます。
【問題４】
配置の符号は任意の移動により不変である。
すなわちm×n配置Cが一回の移動により配置C'に変形されるならば、
s(C)=s(C').
したがって、配置の符号は任意の変形により不変である。
さて、冒頭で述べた問題を解決する準備ができました。
【問題５】
m×n配置Cが可解であるための必要十分条件は
s(C)=(-1)m+n
であることを示せ。
特にm=nならば、Cが可解であるための必要十分条件は
s(C)=1.
●注1.
置換σに対して、
i＜j, σ(i)＞σ(j)となる組(i,j)をσの反転といいます。
rをσの反転数とすれば、
sgnσ=(-1)rが成り立ちます。
したがって、定義2の仮定の下でCの符号は
s(C)=(-1)i+j+rとして求めることができます。
●注2.
各nに対してn文字の偶、奇置換は同数存在します。
したがって、m,nの少なくとも一方が偶数ならば、可解、非可解なm×n配置は同数存在します。
Randomizeボタンをクリックすると、ピースの並び方が変わります。
ピースをクリックすると、動きます。
（同時に同じ行や列の複数のピースを動かすこともできます。）
ピースを最初の並び方にもどせば完成です。
（笑い声がでます）
◆パズル問題へもどる
数学の部屋へもどる