welcome: please sign in
location: "解のある配置を作る"の差分
36と41のリビジョン間の差分 (その間の編集: 5回)
2012-01-11 11:55:37時点のリビジョン36
サイズ: 6507
編集者: masahiko
コメント:
2012-01-25 00:55:25時点のリビジョン41
サイズ: 5718
編集者: masahiko
コメント:
削除された箇所はこのように表示されます。 追加された箇所はこのように表示されます。
行 1: 行 1:
## page was renamed from ばらばらにする
行 101: 行 100:
互換を偶数回行うことで問題を作成します。

メソッドshokikaに次の処理を追加してください。
 . ... で示した箇所は、前回作成したものです。
 . ... の箇所で、正しい位置に配置しています。(前回作成)
 . 6行目以下が互換を偶数回行う処理です。
 . 3行目は変数宣言です。必要に応じ修正してください。
互換を偶数回(50回)行うことで問題を作成します。
行 113: 行 106:
  ... // この部分は前回のまま
  ... // 数行あります
  for (cnt = 0; cnt < (tate*yoko*2); 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++)
行 117: 行 112:
   x = (int)(Math.random() * (yoko-1));
   y = (int)(Math.random() * (tate-1));
   x = (int)(Math.random() * 3);
   y = (int)(Math.random() * 3);
行 138: 行 133:
8~22行目が1つの互換を行う処理です。 5~7行目でもとの配置にしています。。
行 140: 行 135:
その外側のforループを偶数回繰り返すことで偶置換の問題を作り出しています。 10~24行目が1つの互換を行う処理です。

その外側のforループを偶数回(50回)繰り返すことで偶置換の問題を作り出しています。
行 144: 行 141:
 . {{attachment:tikan1.png}} 10,11行目ではxとyの値を乱数で決めています。
乱数は横の数、縦の数より1つ小さい範囲に制限しています。
互換は下図のどれかが行われ、右下のピースの位置だけは変わりません。
行 146: 行 145:
入れ替え元の位置を(x,y)、入れ替え先の位置を(x2,y2)とすると
入れ換えの操作は20~22行目のように書けます。
右下隅のピースはゲーム中は取り除くので、このピースを除いた他のピースの置換(互換)だけを考えなければならないからです。
行 149: 行 147:
 . {{attachment:tikan2.png}}

12~21行目で乱数の値により、x2,y2の位置をx,yの右か下かのどちらかに決めています。
行 157: 行 158:
10~19行目で乱数の値により、そのどちらかを行っています。 22~24行目が入れ換えの操作です。
入れ替え元の位置が(x,y)、入れ替え先の位置が(x2,y2)です。
行 159: 行 161:
8,9行目ではxとyの値を乱数で決めています。
乱数は横の数、縦の数より1つ小さい範囲に制限しています。
この結果、互換は下図のどれかが行われることになります。
 . {{attachment:tikan1.png}}
行 163: 行 163:
矢印で示した互換を乱数で選び何度も繰り返すと、右下隅以外のピースがばらばらに配置されます。

 . {{attachment:tikan2.png}}

右下隅のピースは入れ換えられないことに注意してください。

右下隅のピースはゲーム中は取り除くので、このピースを除いた他のピースの置換(互換)だけを考えなければなりません。
行 172: 行 165:
前回作成したプログラムを複製(名前を変えて保存)した後、
次を行いなさい。
行 175: 行 166:
(1)クラス名を Game2 に修正しなさい。
 * それに伴い修正が必要な箇所が、ファイル名を含め数箇所あります。

(2)メソッドshokikaに上で示した処理を追加し、動作を確認しなさい。
メソッドshokikaを上で示したものに変更し、動作を確認しなさい。

解のある配置を作る

右下の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ゲームでは 偶置換の問題は解けますが、奇置換の問題は解けません。

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


プログラム

最初に正しい位置に配置した後で 互換を偶数回(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         }

プログラムの解説

5~7行目でもとの配置にしています。。

10~24行目が1つの互換を行う処理です。

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

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

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

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

  • tikan2.png

12~21行目で乱数の値により、x2,y2の位置をx,yの右か下かのどちらかに決めています。 右隣と入れ換えるときは

  • x2 = x + 1
  • y2 = y

直下と入れ換えるときは

  • x2 = x
  • y2 = y + 1

となっていればよい。

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

  • tikan1.png


演習

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

解のある配置を作る (最終更新日時 2012-01-25 00:55:25 更新者 masahiko)