## page was renamed from ばらばらにする == ばらばらにする == 右下の1つを除いた他のピースをばらばらに入れ替えた後、 スライドするだけで元の位置に戻すのがこのパズル(15ゲーム)の問題です。 どんなにばらばらに配置しても元の位置にもどせるのかというと、そうではありません。 . '''元にもどせる配置と、元にもどせない配置があります。''' どんな配置だと元にもどせるかを解説した後、 元にもどせる配置だけを作成するメソッドを示します。 ---- === ちょっと数学的な説明 === 並び、置換、互換とその関係の説明をします。 ==== 並び ==== 並べるものの一つ一つを数で表すことにすると、 例えば5つのものの'''並び'''は . (1,2,3,4,5) や . (1,3,5,4,2) や . (4,3,2,5,1) のように書けます。 並び(4,3,2,5,1)は . 4という目印のものが1番目に . 3という目印のものが2番目に . 2という目印のものが3番目に . 5という目印のものが4番目に . 1という目印のものが5番目に 並んでいることを表しています。 ==== 置換 ==== . ものの並びの順番を入れ替える操作を(数学の用語では)'''置換'''と言います。 たとえば . 並び(1,2,3,4,5)を . 並び(1,3,5,4,2)に変える操作 も置換の1つです。 ==== 互換 ==== . 置換のうち2つの要素を互いに入れ替えるものを互換といいます。 たとえば . 並び(1,2,3,4,5)を . 並び(2,1,3,4,5)に変える操作 は互換の1つです。 交換される2つ以外の要素の位置は変わりません。 ==== 互換の積 ==== . 置換は互換の積で表すことができます。 どんな置換(入れ替え)も、互換(2つの入れ替え)を繰り返すことで行うことができるという意味です。 たとえば、並び(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)に変えるには 互換の回数は偶数回になります。 . '''どんな置換も互換を繰り返すことでできるが、互換の回数は偶数回か奇数回のどちらかに決まる。''' 奇数回の互換で表される置換を'''偶置換'''といいます。 偶数回の互換で表せれる置換を'''奇置換'''といいます。 ---- === 15ゲームが解ける条件 === 15ゲームでは 偶置換の問題は解けますが、奇置換の問題は解けません。 偶置換の問題だけを作るようにプログラムを作成します。 ---- === プログラム === 最初に正しい位置に配置した後で 互換を偶数回行うことで問題を作成します。 メソッドshokikaに次の処理を追加してください。 . ... で示した箇所は、前回作成したものです。 . ... の箇所で、正しい位置に配置しています。(前回作成) . 6行目以下が互換を偶数回行う処理です。 . 3行目は変数宣言です。必要に応じ修正してください。 {{{#!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; } } }}} ==== プログラムの解説 ==== 8~22行目が1つの互換を行う処理です。 その外側のforループを偶数回繰り返すことで偶置換の問題を作り出しています。 1つ1つの互換は ban[x][y]にある内容を、その右隣または直下の内容と入れ替える操作にします。 . {{attachment:tikan1.png}} 入れ替え元の位置を(x,y)、入れ替え先の位置を(x2,y2)とすると 入れ換えの操作は20~22行目のように書けます。 右隣と入れ換えるときは . x2 = x + 1 . y2 = y 直下と入れ換えるときは . x2 = x . y2 = y + 1 となっていればよい。 10~19行目で乱数の値により、そのどちらかを行っています。 8,9行目ではxとyの値を乱数で決めています。 乱数は横の数、縦の数より1つ小さい範囲に制限しています。 この結果、互換は下図のどれかが行われることになります。 矢印で示した互換を乱数で選び何度も繰り返すと、右下隅以外のピースがばらばらに配置されます。 . {{attachment:tikan2.png}} 右下隅のピースは入れ換えられないことに注意してください。 右下隅のピースはゲーム中は取り除くので、このピースを除いた他のピースの置換(互換)だけを考えなければなりません。 ---- === 演習 === 前回作成したプログラムを複製(名前を変えて保存)した後、 次を行いなさい。 (1)クラス名を Game2 に修正しなさい。 * それに伴い修正が必要な箇所が、ファイル名を含め数箇所あります。 (2)メソッドshokikaに上で示した処理を追加し、動作を確認しなさい。