解のある配置を作る
右下の１つを除いた他のピースをばらばらに入れ替えた後、 スライドするだけで元の位置に戻すのがこのパズル(１５ゲーム)の問題です。
どんなにばらばらに配置しても元の位置にもどせるのかというと、そうではありません。
元にもどせる配置と、元にもどせない配置があります。
どんな配置だと元にもどせるかを解説した後、 元にもどせる配置だけを作成するメソッドを示します。
ちょっと数学的な説明
- 並び、置換、互換とその関係の説明をします。
並び
並べるものの一つ一つを数で表すことにすると、 例えば５つのものの並びは
- (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)に変えるには 互換の回数は偶数回になります。
どんな置換も互換を繰り返すことでできるが、互換の回数は偶数回か奇数回のどちらかに決まる。
奇数回の互換で表される置換を偶置換といいます。
偶数回の互換で表せれる置換を奇置換といいます。
１５ゲームが解ける条件
１５ゲームでは 偶置換の問題は解けますが、奇置換の問題は解けません。
偶置換の問題だけを作るようにプログラムを作成します。
プログラム
最初に正しい位置に配置した後で 互換を偶数回行うことで問題を作成します。
メソッドshokikaに次の処理を追加してください。
- ... で示した箇所は、前回作成したものです。
- ... の箇所で、正しい位置に配置しています。(前回作成)
- 6行目以下が互換を偶数回行う処理です。
- 3行目は変数宣言です。必要に応じ修正してください。
1 void shokika()
2 {
3 int x, y, x2, y2, w, cnt;
4
5 for (x = 0; x < 4; x++)
6 for (y = 0; y < 4; y++)
7 ban[x][y] = x + y*4;
8 for (cnt = 0; cnt < 50; cnt++)
9 {
10 x = (int)(Math.random() * 3);
11 y = (int)(Math.random() * 3);
12 if(Math.random() < 0.5)
13 {
14 x2 = x;
15 y2 = y + 1;
16 }
17 else
18 {
19 x2 = x + 1;
20 y2 = y;
21 }
22 w = ban[x][y];
23 ban[x][y] = ban[x2][y2];
24 ban[x2][y2] = w;
25 }
26 }
プログラムの解説
８～２２行目が１つの互換を行う処理です。
その外側のforループを偶数回繰り返すことで偶置換の問題を作り出しています。
１つ１つの互換は ban[x][y]にある内容を、その右隣または直下の内容と入れ替える操作にします。
入れ替え元の位置を(x,y)、入れ替え先の位置を(x2,y2)とすると 入れ換えの操作は２０～２２行目のように書けます。
右隣と入れ換えるときは
- x2 = x + 1
- y2 = y
直下と入れ換えるときは
- x2 = x
- y2 = y + 1
となっていればよい。
１０～１９行目で乱数の値により、そのどちらかを行っています。
８，９行目ではｘとｙの値を乱数で決めています。 乱数は横の数、縦の数より１つ小さい範囲に制限しています。 この結果、互換は下図のどれかが行われることになります。
矢印で示した互換を乱数で選び何度も繰り返すと、右下隅以外のピースがばらばらに配置されます。
右下隅のピースは入れ換えられないことに注意してください。
右下隅のピースはゲーム中は取り除くので、このピースを除いた他のピースの置換(互換)だけを考えなければなりません。
演習
前回作成したプログラムを複製(名前を変えて保存)した後、 次を行いなさい。
（１）クラス名を Game2 に修正しなさい。
- それに伴い修正が必要な箇所が、ファイル名を含め数箇所あります。
（２）メソッドshokikaに上で示した処理を追加し、動作を確認しなさい。