#acl All:
== ばらばらにする ==

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

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

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

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

----
=== 置換 ===

ものの並びの順番を入れ替える操作を置換と言います。

並べるものの一つ一つを数で表すことにすると、
例えば５つのものの並びは
(1,2,3,4,5)や(1,3,5,4,2)や(4,3,2,5,1)
などのように書けます。

1番目の並びを２番目の並びに変える操作は置換の１つで
(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回の互換で上の置換ができました。

他の方法もあります。

しかしどの方法をとっても、互換の回数は偶数回か奇数回のどちらかになります。

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

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

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

----
{{{#!java
	void shokika()
	{
		int x, y, x2, y2, w, cnt;
		...
		...
		for (cnt = 0; cnt < (tate*yoko*2); cnt++)
		{
			x = (int)(Math.random() * (yoko-1));
			y = (int)(Math.random() * (tate-1));
			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;
		}
	}
}}}