|
サイズ: 712
コメント:
|
サイズ: 2723
コメント:
|
| 削除された箇所はこのように表示されます。 | 追加された箇所はこのように表示されます。 |
| 行 3: | 行 3: |
| ピースを１つ取り除いてできた空白部分を使って 移動するための処理を記述します。 |
|
| 行 6: | 行 4: |
| {{{ int spx, spy; }}} |
右下の１つを除いた他のピースをばらばらに入れ替えた後、 スライドするだけで元の位置に戻すのがこのパズル(１５ゲーム)の問題です。 |
| 行 10: | 行 7: |
| {{{ public void paintComponent(Graphics g) { for(...) for(...) { ... } g.setColor(Color.lightGray); g.fillRect(spx*haba, spy*haba, haba, haba); } }}} |
どんなにばらばらに配置しても元の位置にもどせるのかというと、そうではありません。 |
| 行 23: | 行 9: |
| . '''元にもどせる配置と、元にもどせない配置があります。''' どんな配置だと元にもどせるかを解説した後、 元にもどせる配置だけを作成するメソッドを示します。 ---- === ちょっと数学的な説明 === 並び、置換、互換とその関係の説明をします。 ==== 並び ==== 並べるものの一つ一つを数で表すことにすると、 例えば５つのものの'''並び'''は . (1,2,3,4,5) や . (1,3,5,4,2) や . (4,3,2,5,1) のように書けます。 並び(4,3,2,5,1)は . ４という目印のものが１番目に . ３という目印のものが２番目に . ２という目印のものが３番目に . ５という目印のものが４番目に . １という目印のものが５番目に 並んでいることを表しています。 ==== 置換 ==== . ものの並びの順番を入れ替える操作を(数学の用語では)'''置換'''と言います。 1番目の並びを２番目の並びに変える操作は置換の１つで (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回の互換で上の置換ができました。 他の方法もあります。 しかしどの方法をとっても、互換の回数は偶数回か奇数回のどちらかになります。 偶置換、奇置換といいます。 ---- １５ゲームでは 偶置換の問題は解けるが、奇置換の問題は解けません。 偶置換の問題だけを作るようにプログラムを作成します。 最初に正しい位置に配置した後 互換を偶数回行うことで問題を作成します。 ---- |
|
| 行 26: | 行 73: |
| int x, y, x2, y2, w, cnt; | |
| 行 27: | 行 75: |
| spx = yoko-1; spy = tate-1; for (cnt = 0; cnt < (tate*yoko*2); ) // 偶数回置換 |
... for (cnt = 0; cnt < (tate*yoko*2); cnt++) |
| 行 31: | 行 78: |
| x = (int)(Math.random() * yoko); y = (int)(Math.random() * tate); if(x != spx || y != spy) |
x = (int)(Math.random() * (yoko-1)); y = (int)(Math.random() * (tate-1)); if(Math.random() < 0.5) |
| 行 35: | 行 82: |
| ban[spx][spy] = ban[x][y]; spx = x; spy = y; cnt++; |
x2 = x; y2 = y + 1; |
| 行 40: | 行 85: |
| else { x2 = x + 1; y2 = y; } w = ban[x][y]; ban[x][y] = ban[x2][y2]; ban[x2][y2] = w; |
ばらばらにする
右下の１つを除いた他のピースをばらばらに入れ替えた後、 スライドするだけで元の位置に戻すのがこのパズル(１５ゲーム)の問題です。
どんなにばらばらに配置しても元の位置にもどせるのかというと、そうではありません。
元にもどせる配置と、元にもどせない配置があります。
どんな配置だと元にもどせるかを解説した後、 元にもどせる配置だけを作成するメソッドを示します。
ちょっと数学的な説明
- 並び、置換、互換とその関係の説明をします。
並び
並べるものの一つ一つを数で表すことにすると、 例えば５つのものの並びは
- (1,2,3,4,5) や
- (1,3,5,4,2) や
- (4,3,2,5,1)
のように書けます。
並び(4,3,2,5,1)は
- ４という目印のものが１番目に
- ３という目印のものが２番目に
- ２という目印のものが３番目に
- ５という目印のものが４番目に
- １という目印のものが５番目に
並んでいることを表しています。
置換
ものの並びの順番を入れ替える操作を(数学の用語では)置換と言います。
1番目の並びを２番目の並びに変える操作は置換の１つで (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回の互換で上の置換ができました。
他の方法もあります。
しかしどの方法をとっても、互換の回数は偶数回か奇数回のどちらかになります。
偶置換、奇置換といいます。
１５ゲームでは 偶置換の問題は解けるが、奇置換の問題は解けません。
偶置換の問題だけを作るようにプログラムを作成します。
最初に正しい位置に配置した後 互換を偶数回行うことで問題を作成します。
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 }