welcome: please sign in
location: "解のある配置を作る"の差分
1と21のリビジョン間の差分 (その間の編集: 20回)
2009-12-04 06:16:15時点のリビジョン1
サイズ: 689
編集者: masahiko
コメント:
2010-01-05 01:55:02時点のリビジョン21
サイズ: 4745
編集者: masahiko
コメント:
削除された箇所はこのように表示されます。 追加された箇所はこのように表示されます。
行 3: 行 3:
{{{
 void mazeru()

右下の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()
行 6: 行 112:
  int i, j, x1, y1, x2, y2, w;
  
  ban = new int[nx][ny];
  for(i = 0; i < nx; i++) // 元の位置
   for(j = 0; j < ny; j++)
    ban[i][j] =i + j * nx;
  spx = nx-1; // 空白の位置
  spy = ny-1;
  for(i = 0; i < (nx*ny*2); i++) // 偶数回置換
  int x, y, x2, y2, w, cnt;
  ...
  ...
  for (cnt = 0; cnt < (tate*yoko*2); cnt++)
行 16: 行 117:
   do    x = (int)(Math.random() * (yoko-1));
   y = (int)(Math.random() * (tate-1));
   if(Math.random() < 0.5)
行 18: 行 121:
    x1 = (int)(Math.random() * nx);
    y1 = (int)(Math.random() * ny);
    x2 = (int)(Math.random() * nx);
    y2 = (int)(Math.random() * ny);
   } while ( (x1 == x2 && y1 == y2) ||
    (x1 == spx && y1 == spy) || (x2 == spx && y2 == spy) );
   w = ban[x1][y1];
   ban[x1][y1] = ban[x2][y2];
    x2 = x;
    y2 = y + 1;
   }
   else
   {
    x2 = x + 1;
    y2 = y;
   }
   w = ban[x][y];
   ban[x][y] = ban[x2][y2];
行 30: 行 135:

==== プログラムの解説 ====

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

 . {{attachment:tikan1.png}}

ばらばらにする

右下の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行目は変数宣言です。必要に応じ修正してください。

   1         void shokika()
   2         {
   3                 int x, y, x2, y2, w, cnt;
   4                 ...
   5                 ...
   6                 for (cnt = 0; cnt < (tate*yoko*2); cnt++)
   7                 {
   8                         x = (int)(Math.random() * (yoko-1));
   9                         y = (int)(Math.random() * (tate-1));
  10                         if(Math.random() < 0.5)
  11                         {
  12                                 x2 = x;
  13                                 y2 = y + 1;
  14                         }
  15                         else
  16                         {
  17                                 x2 = x + 1;
  18                                 y2 = y;
  19                         }
  20                         w = ban[x][y];
  21                         ban[x][y] = ban[x2][y2];
  22                         ban[x2][y2] = w;
  23                 }
  24         }

プログラムの解説

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

  • tikan1.png

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