解のある配置を作る
右下の１つを除いた他のピースをばらばらに入れ替えた後、 スライドするだけで元の位置に戻すのがこのパズル(１５ゲーム)の問題です。
どんなにばらばらに配置しても元の位置にもどせるのかというと、そうではありません。
元にもどせる配置と、元にもどせない配置があります。
どんな配置だと元にもどせるかを解説した後、 元にもどせる配置だけを作成するメソッドを示します。
ちょっと数学的な説明
- 並び、置換、互換とその関係の説明をします。
並び
並べるものの一つ一つを数で表すことにすると、 例えば５つのものの並びは
- (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回)行うことで問題を作成します。
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ループを偶数回(50回)繰り返すことで偶置換の問題を作り出しています。
１つ１つの互換は ban[x][y]にある内容を、その右隣または直下の内容と入れ替える操作にします。
１０，１１行目ではｘとｙの値を乱数で決めています。 乱数は横の数、縦の数より１つ小さい範囲に制限しています。 互換は下図のどれかが行われ、右下のピースの位置だけは変わりません。
右下隅のピースはゲーム中は取り除くので、このピースを除いた他のピースの置換(互換)だけを考えなければならないからです。
１２～２１行目で乱数の値により、x2,y2の位置をx,yの右か下かのどちらかに決めています。 右隣と入れ換えるときは
- x2 = x + 1
- y2 = y
直下と入れ換えるときは
- x2 = x
- y2 = y + 1
となっていればよい。
２２～２４行目が入れ換えの操作です。 入れ替え元の位置が(x,y)、入れ替え先の位置が(x2,y2)です。
演習
メソッドshokikaを上で示したものに変更し、動作を確認しなさい。