ばらばらにする

右下の１つを除いた他のピースをばらばらに入れ替えた後、 スライドするだけで元の位置に戻すのがこのパズル(１５ゲーム)の問題です。

どんなにばらばらに配置しても元の位置にもどせるのかというと、そうではありません。

• 元にもどせる配置と、元にもどせない配置があります。

どんな配置だと元にもどせるかを解説した後、 元にもどせる配置だけを作成するメソッドを示します。

ちょっと数学的な説明

• 並び、置換、互換とその関係の説明をします。

並び

並べるものの一つ一つを数で表すことにすると、 例えば５つのものの並びは

• (1,2,3,4,5) や
• (1,3,5,4,2) や
• (4,3,2,5,1)

のように書けます。

並び(4,3,2,5,1)は

• ４という目印のものが１番目に
• ３という目印のものが２番目に
• ２という目印のものが３番目に
• ５という目印のものが４番目に
• １という目印のものが５番目に

並んでいることを表しています。

置換

• ものの並びの順番を入れ替える操作を(数学の用語では)置換と言います。

たとえば

• 並び(1,2,3,4,5)を
• 並び(1,3,5,4,2)に変える操作

も置換の１つです。

互換

• 置換のうち２つの要素を互いに入れ替えるものを互換といいます。

たとえば

• 並び(1,2,3,4,5)を
• 並び(2,1,3,4,5)に変える操作

は互換の１つです。

交換される２つ以外の要素の位置は変わりません。

互換の積

• 置換は互換の積で表すことができます。

どんな置換(入れ替え)も、互換(２つの入れ替え)を繰り返すことで行うことができるという意味です。

たとえば、並び(1,2,3,4,5)を並び(1,3,5,4,2)に変えるには

• 元の状態	互換	入れ替え後の状態
  (1,2,3,4,5)	2と3を入れ替え	(1,3,2,4,5)
  (1,3,2,4,5)	2と5を入れ替え	(1,3,5,4,2)

と、2回の互換で行うことができました。

==== 偶置換、奇置換 ===

何回かの互換を繰り返すことで置換ができることがわかりました。

上の例では2回の互換で目的の置換ができましたが他の手順も考えられます。

• 元の状態	互換	入れ替え後の状態
  (1,2,3,4,5)	2と3を入れ替え	(1,3,2,4,5)
  (1,3,2,4,5)	2と4を入れ替え	(1,3,4,2,5)
  (1,3,4,2,5)	2と5を入れ替え	(1,3,4,5,2)
  (1,3,4,5,2)	4と5を入れ替え	(1,3,5,4,2)

4回の互換で行うことができました。

ほかにもいろいろな手順が考えられます。

しかしどの方法をとっても、 並び(1,2,3,4,5)を並び(1,3,5,4,2)に変えるには 互換の回数は偶数回になります。

• どんな置換も互換を繰り返すことでできるが、互換の回数は偶数回か奇数回のどちらかに決まる。

奇数回の互換で表される置換を偶置換といいます。

偶数回の互換で表せれる置換を奇置換といいます。

１５ゲームでは 偶置換の問題は解けるが、奇置換の問題は解けません。

偶置換の問題だけを作るようにプログラムを作成します。

最初に正しい位置に配置した後 互換を偶数回行うことで問題を作成します。

   1         void shokika()
   2         {
   3                 int x, y, x2, y2, w, cnt;
   4                 ...
   5                 ...
   6                 for (cnt = 0; cnt < (tate*yoko*2); cnt++)
   7                 {
   8                         x = (int)(Math.random() * (yoko-1));
   9                         y = (int)(Math.random() * (tate-1));
  10                         if(Math.random() < 0.5)
  11                         {
  12                                 x2 = x;
  13                                 y2 = y + 1;
  14                         }
  15                         else
  16                         {
  17                                 x2 = x + 1;
  18                                 y2 = y;
  19                         }
  20                         w = ban[x][y];
  21                         ban[x][y] = ban[x2][y2];
  22                         ban[x2][y2] = w;
  23                 }
  24         }