== 解のある配置を作る ==

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

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

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

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

----
=== ちょっと数学的な説明 ===

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

==== 並び ====

並べるものの一つ一つを数で表すことにすると、
例えば５つのものの'''並び'''は
 . (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)に変えるには
互換の回数は偶数回になります。

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

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

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

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

偶置換の問題だけを作るようにプログラムを作成します。
----
=== プログラム ===
最初に正しい位置に配置した後で
互換を偶数回(50回)行うことで問題を作成します。

{{{#!java
	void shokika()
	{
		int x, y, x2, y2, w, cnt;
		
		for (x = 0; x < 4; x++)
			for (y = 0; y < 4; y++)
				ban[x][y] = x + y*4;
		for (cnt = 0; cnt < 50; cnt++)
		{
			x = (int)(Math.random() * 3);
			y = (int)(Math.random() * 3);
			if(Math.random() < 0.5)
			{
				x2 = x;
				y2 = y + 1;
			}
			else
			{
				x2 = x + 1;
				y2 = y;
			}
			w = ban[x][y];
			ban[x][y] = ban[x2][y2];
			ban[x2][y2] = w;
		}
	}
}}}

==== プログラムの解説 ====

５～７行目でもとの配置にしています。。

１０～２４行目が１つの互換を行う処理です。

その外側のforループを偶数回(50回)繰り返すことで偶置換の問題を作り出しています。

１つ１つの互換は ban[x][y]にある内容を、その右隣または直下の内容と入れ替える操作にします。

１０，１１行目ではｘとｙの値を乱数で決めています。
乱数は横の数、縦の数より１つ小さい範囲に制限しています。
互換は下図のどれかが行われ、右下のピースの位置だけは変わりません。

右下隅のピースはゲーム中は取り除くので、このピースを除いた他のピースの置換(互換)だけを考えなければならないからです。

 . {{attachment:tikan2.png}}

１２～２１行目で乱数の値により、x2,y2の位置をx,yの右か下かのどちらかに決めています。
右隣と入れ換えるときは
 . x2 = x + 1
 . y2 = y
直下と入れ換えるときは
 . x2 = x
 . y2 = y + 1
となっていればよい。

２２～２４行目が入れ換えの操作です。
入れ替え元の位置が(x,y)、入れ替え先の位置が(x2,y2)です。

 . {{attachment:tikan1.png}}

----
=== 演習 ===

メソッドshokikaを上で示したものに変更し、動作を確認しなさい。