10 パズル
10 パズルの遊び方
空きマス目２つのスライドパズルを思いついたのは、15 パズルの全盤面探索を考えているときでした。
実際にパズルを作成してみて、空きマス目２つのスライドパズルは、
パズルとしても空きマス目１つのスライドパズルとは違った味があるのではないかと思っています。
下の図は、１つの８手問題の問題図から完成図までを示したものです。
(1) 7, 10 を下に
|
-> |
(2) 4 を右に
|
-> |
(3) 8, 3 を下に
| -> |
(4) 2 を左に
|
-> |
(5) 3, 4 を上に
|
-> |
(6) 8 を右に
| -> |
(7) 6, 7 を上に
|
-> |
(8) 10 を左に
|
-> |
完成
| |
各図の上には、動かす数字マス目を記しています。10
パズルでは、単に左から順番に数字順に並べようとしてもうまく行きません。図 (5) や (7)
のように、１手前の時点で次に上に移動すると列が並ぶように、下の列で準備しなければなりません。
例えば図 (5) で、空きマス目の下に 3, 4 が並んでいないと、せっかく並べた 1, 2
も崩さなければならなくなります。１番上の列の 1, 2, 3, 4 を並べるにも、3
手前のパターンが次の６つあります。なお、* は任意の数字マス目を表しています。
上の６つのパターンを覚えておくことが、「10 パズル」を解くための１つのコツとなります。(3)
と (6) のパターンは分かりやすいのですが、(1), (2), (3), (4)
のパターンも覚えておかないとと最短手数で解くことができなくなってしまいます。
１列目を並べ終わったら、２列目も同様の方法で並べることができます。
慣れないうちは難しいと感じるかもしれませんが、「10
パズル」には手数の短い易しい問題が最初に並んでいますので、遊んでいただけらと思います。
8 パズルの探索
10 パズルのプログラムを取り上げる前に、空きマス目１つの 8
パズルの盤面の探索を取り上げます。スライドパズルと言えば、サム・ロイドが考案した「15
パズル」が有名です。下図は、「15 パズル」と盤面のサイズを１回り小さくした「8
パズル」のゴールの盤面です。
| 15 パズル | | 8 パズル |
| 1 |
2 |
3 |
4 |
| 5 | 6 |
7 | 8 |
| 9 | 10 |
11 | 12 |
| 13 | 14 |
15 | |
| |
|
15 パズルの系統のパズルは、単にランダムに数字を配置しただけでは、
ゴールに到達しない場合があります。よく知られているように、上の 15 パズルのゴールの盤面から 14 と 15
を入れ換えた盤面は、ゴールに到達できない不可能な盤面です。ランダムに数字を配置して問題を出題する方法では、1/2
の確率で正解のない問題になってしまいます。
ゴールの盤面から２つの数字マス目を (スライドさせるのではなく)
持ち上げて偶数回入れ換えると、正解のある問題を作ることができます。
しかし、この方法では、最短手数と正解手順を知ることができません。問題を出題する立場としては、
不満の残るところです。もう１つの方法は、全盤面の探索して問題を作成する方法です。
全盤面探索では、ゴールの盤面から１つずつ数字マス目を動かしながら盤面を生成して記録していきます。
(というのはパズルを遊ぶ立場からの表現で、プログラムとしては空きマス目を動かしていきます。)
同じ盤面はたくさんの経路で生成されますが、記録するのは最短手数で生成したものだけです。
このようにして生成すると、手数順に全盤面のデータを得ることができます。
まずは、3 x 3 盤面の 8 パズルの全盤面を生成するプログラムを取り上げます。プログラムは、8
パズルの全盤面 181,440 (9! / 2) を生成して、単に @board 配列に入れるだけのものです。
8 パズルの全盤面生成プログラム (その１)
1. use strict;
2. my %move = (0 => [1, 3], 1 => [0, 2, 4], 2 => [1, 5],
3 => [0, 4, 6], 4 => [1, 3, 5, 7], 5 => [2, 4, 8],
6 => [3, 7], 7 => [4, 6, 8], 8 => [5, 7]);
3. my @search = (join '', 1 .. 8, '_:'); my @board = (join '', 1 .. 8, '_');
4. while (@search) {
5. my ($board, $pp) = split /:/, shift(@search);
6. my $cp = index $board, '_'; # $pp 前の位置, $cp 現在の位置, $np 次の位置
7. foreach my $np (@{$move{$cp}}) {
8. next if $np == $pp;
9. my $work = $board;
10. substr($work, $cp, 1) = substr($work, $np, 1, '_');
11. next if grep { $work eq $_ } @board;
12. push @search, "$work:$cp";
13. push @board, $work;
15. }
16. }
- Line 2, 3: 空きマス目の移動リストの生成
- 盤面は、単なる文字列として表現します。ゴールの盤面は "12345678_" になり、空きマス目である "_"
を次々に移動させて新しい盤面を生成していきます。その "_" の移動の際に参照するのが、%move
ハッシュです。ハッシュのキーが文字列内における "_" の位置であり、値が移動先リストです。
盤面の位置 (文字列の位置も) はゴールの盤面の数字から１引いたものであり、左上が 0
でその右が１で、右下が 8 になります。
- Line 4 〜 16: while ループの基本動作
- スライドパズルで全盤面を生成するには、while ループと配列の組み合わせで行うのが効果的です。while
ループの開始時点では、@search 配列に入っているのはゴールの盤面だけです。Line 5
でそれを取り出し、内側の foreach ループですべての１手目を生成します。生成された盤面は、@search
に格納しておきます。２手目以降も同様の繰り返しで生成され、生成する盤面がなくなると終了します。
- Line 9: ３つの空きマス目の位置
- $pp は空きマス目の移動元の位置、$cp は現在の位置、$np は次の位置になります。$pp と $np
が同じ場合は、前の盤面に戻ってしまうのでスキップします。
- Line 10: 新しい盤面の生成
- 新しい盤面の生成は、substr() 関数を使って行います。substr()
関数は一般的に部分文字列を取得するために使いますが、文字列の置き換えにも使うことができます。
文字列の置き換えにも、２つの方法があります。４引数の substr() を使う方法と、代入を使う方法です。
substr($work, $cp, 1) = substr($work, $np, 1, '_');
上の文では、右側の substr() が先に実行されます。$np は次の空きマス目の位置であり、それを '_'
に置き換えたら元の文字を返します。右側の sbustr() は、４引数によって置き換えています。
次に、左側の substr() が実行されます。$cp は現在の '_' の位置であり、それを右側の substr()
返した文字を代入によって置き換えます。
- Line 11: 新しい盤面か否かのチェック
- @board 配列には、すでに生成された盤面が格納されています。新しく生成された盤面を @board
配列にあるかないかをチェックして、生成済みである場合はスキップします。
実はこの文には、効率面で問題があります。説明は後ほど行います。
プログラムは全盤面の生成のみで、ほかに何もしていないので 16 行と短いものです。
このプログラムを実行すると、8 パズルの全盤面 181,440 が手数順に配列 @board
に保存されます。配列の最初の５要素と最後の５要素は、次のようになっています。
カッコ内の数字は、何手目かを表しています。
12345678_(0)
12345_786(1)
1234567_8(1)
12_453786(2)
1234_5786(2)
・・・
281354_67(30)
68725134_(30)
64_857321(30)
64785_321(31)
8672543_1(31)
プログラムの実行には、私のパソコン (PentiumM 1.8Gz, RAM 2GB, OS Vine Linux, Perl ver
5.8.2) で 7,747 秒 (2 時間 9 分 7 秒) も要しました。今回のメインテーマである 4 x 3 盤面の 10 パズルや
4 x 4 の 14 パズルの探索のことも考えていたものですから、お先真っ暗の気分になってしまいました。
コードを見直してみましたが、特に問題があるようには思えませんでした。それでも、速度的な改善を見込めるのは、
生成済み盤面をチェックしている Line 11 の grep だけです。この部分を工夫したのが、次のプログラムです。
8 パズルの全盤面生成プログラム (その２)
1. use strict;
2. my %move = (0 => [1, 3], 1 => [0, 2, 4], 2 => [1, 5],
3 => [0, 4, 6], 4 => [1, 3, 5, 7], 5 => [2, 4, 8],
6 => [3, 7], 7 => [4, 6, 8], 8 => [5, 7]);
3. my @search = (join '', 1 .. 8, '_:'); my @board = (join '', 1 .. 8, '_');
4. my %generated = (1234 => ['5678_']);
5. while (@search) {
6. my ($board, $pp) = split /:/, shift(@search);
7. my $cp = index $board, '_';
8. foreach my $np (@{$move{$cp}}) {
9 next if $np == $pp;
10. my $work = $board;
11. substr($work, $cp, 1) = substr($work, $np, 1, '_');
12. my ($head, $tail) = $work =~ /^(....)(.+)$/;
13. next if grep { $tail eq $_ } @{$generated{$head}};
14. push @{$generated{$head}}, $tail;
15. push @search, "$work:$cp";
16. push @board, $work;
17. }
18. }
- Line 4: grep 用のハッシュを用意する
- 前のプログラムでは単一の配列を対象に grep していましたが、このプログラムでは配列を小分けにしています。
盤面データの最初の４文字をハッシュのキーとして使い、残りの５文字のみを配列に入れています。
この方法ではハッシュのキーは 3,024 (9 * 8 * 7 * 6) となり、個々の配列の要素数は最大で 60
(5! / 2) となります。
- Line 12,13,14: 新しい盤面か否かのチェックと保存
- 新しく生成した盤面は、２つに分割して２つの変数 ($head, $tail) に入れます。
次に、生成済みであるか否かをチェックし、生成済みである場合はスキップし、
生成済みでない場合はハッシュに保存します。
このプログラムを実行して、自分でもビックリしてしまいました。
何と、4 秒で実行が終了したのです。前のプログラムが 7,747 秒ですから、比べようがありません。
原因として考えられるのは、配列の要素数が一定数以上になると grep の走査が急激に時間がかかるようになる、
以外にありません。私のほかのパソコン、OS/2 の Perl var 5.005_53 や Ubuntu の Perl var 5.8.8
でも同様の結果でした。まったく同じことをするプログラムで、ほんの少しのコードの違いで、
これほど実行時間に違いがあるのは珍しいと思い２つのプログラムを紹介しました。
この後のプログラムでは、(その２) のプログラムを改造したものを使います。
次は 15 パズルの探索と行きたいところですが、そうは簡単には行きません。
１つ目は、時間のかかることです。4 (秒) * 10 * 11 * 12 * 13 * 14 * 15 * 16
という単純な掛け算をしても、230,630,400
秒 (7 年 114 日 8 時間) になります。実際は、これよりもはるかに多くかかります。２つ目は、リソースの問題です。
現在のパソコンでは、メモリなどが不足し膨大な盤面数を扱いきれません。という訳で、15
パズルの探索はあきらめました。
10 パズルの探索
ここから、今回のメインのスライドパズルである 10 パズルに話を移します。なお、7
パズルと後の機会に取り上げる予定の 14 パズルに共通する部分は、ここの説明で触れています。
7, 10, 14 パズルは、空きマス目を２つに増やして、２つのルールを追加しています。
| 14 パズル | | 10 パズル |
| 7 パズル |
| 1 |
2 |
3 |
4 |
| 5 | 6 |
7 | 8 |
| 9 | 10 |
11 | 12 |
| 13 | 14 |
| |
| |
| |
|
- ２つの空きマス目に左右に隣接する数字マス目は、２マス移動する
- ２つの空きマス目に上下に隣接する数字マス目は、２つの数字マス目が一緒に空きマス目に移動する
上のルールは数字マス目側から見たもので、空きマス目側から見ると、
２つの空きマス目が離ればなれになることはなく、一緒に盤面内を移動するということです。
空きマス目を２つにしてルールを２つ追加しただけすが、これで盤面数が劇的に減少します。3 x 3, 4 x 3,
4 x 4 盤面での全盤面数は、次のようになります。
3 x 3 4 x 3 4 x 4
空きマス目１ 181,440 239,500,800 10,461,394,944,000
空きマス目２ 360 32,400 76,204,800
空きマス目２つを１つのマス目と数えることができるので、7 パズルでは 8!/2、10
パズルでは 11!/2、14 パズルでは 15!/2 と思うかもしれませんが、そうではありません。15
パズルでは数字マス目はどのマス目にも移動できますが、7, 10, 14
パズルでは数字マス目は同じ列か１列間をおいた列にしか移動できません。下図のように同じ色のマス目にだけ、
数字マス目は移動できます。右側の式が、それぞれの盤面の全盤面数の計算式です。
| 1 |
2 |
3 |
4 |
| 5 | 6 |
7 | 8 |
| 9 | 10 |
11 | 12 |
| 13 | 14 |
| |
| |
3 x 3: 5!/2 * 2!/2 * 6 (末尾の数字は空きマス目の位置数)
4 x 3: 5!/2 * 5!/2 * 9
4 x 4: 7!/2 * 7!/2 * 12 |
7, 10, 14 パズルは２つの盤面が組み合わさったものと考えることができ、
数字マス目の移動が制限されるため盤面数が少なくなっているのです。特に 7 パズルは、中央列の計算式が 2!/2
のため、2, 5 が他の列に移動できません。そのためパズルでは、出題の盤面でもゴールの盤面でも 2 と 5
の位置が同じになってしまいます。
パズルとして「7 パズル」を作ったのですが、
その点が気になり公式には公開していません。サーバーにアップしてありますので、よかったら遊んでみてください。
10 パズルの全盤面数は 32,400 で 8 パズルの 181,440 よりはるかに少ないので、
パソコンで楽々と探索することができます。次が、10
パズルの全盤面とパズルの問題集生成プログラムです。なお、２桁の数字マス目 10 は、アルファベットの１文字 a
で扱っています。
10 パズルの問題集生成プログラム
1. use strict;
2. my %move = (0 => [1, 4], 1 => [0, 2, 5], 2 => [1, 6],
4 => [0, 5, 8], 5 => [1, 4, 6, 9], 6 => [2, 5, 10],
8 => [4, 9], 9 => [5, 8, 10], 10 => [6, 9]);
3. my @search = (join('', 1 .. 9, 'a__', ':0')); my @ques;
4. my %board = ('123456789a__' => 0); my %generated = (12345 => ['6789a__']);
5. while (@search) {
6. my ($board, $level, $pp) = split /:/, shift @search;
7. my $cp = index $board, '__';
8. foreach my $np (@{$move{$cp}}) {
9. next if $np == $pp;
10. my $work = $board;
11. if ($np + 1 == $cp) {
12. substr($work, $cp + 1, 1) = substr($work, $np, 1, '_');
13. } elsif ($np == $cp + 1) {
14. substr($work, $cp, 1) = substr($work, $np + 1, 1, '_');
15. } else {
16. substr($work, $cp, 2) = substr($work, $np, 2, '__');
17. }
18. my ($head, $tail) = $work =~ /^(.....)(.+)$/;
19. next if grep { $tail eq $_ } @{$generated{$head}};
20. push @{$generated{$head}}, $tail;
21. $board{$work} = $board;
22. if ($work =~ /__$/) {
23. my $pre_board = $board;
24. my @order = ();
25. while ($pre_board) {
26. push @order, index($pre_board, "__");
27. $pre_board = $board{$pre_board};
28. }
29. push @ques, join(':', $work, $level + 1, join('|', @order));
30. }
31. push @search, join(':', $work, $level + 1, $cp);
32. }
33. }
34. open OUT, ">b4x3_ques.dat" or die "Can't open b4x3_ques.dat: $!";
35. print OUT join("\n", @ques), "\n";
36. close OUT;
- Line 2: 空きマス目の移動リストの生成
- 8 パズルと違い 10 パズルでは２つのマス目が一緒に動くため、２つの空きマス目をセットとして扱い、
先頭の空きマス目の位置のみをハッシュのキーに登録します。そのため、マス目位置 3, 7, 11
の移動リストはありません。
- Line 3,4: 必要な変数の宣言
- @search に格納する盤面データの形式は、「盤面:現在の手数:元の空きマス目の位置」にしています。8
パズルでは「盤面:現在の空きマス目の位置」でしたが、10 パズルの出題で手数を明示するために「現在の手数」を
増やしています。@ques は、パズルの問題を格納します。全盤面の保存に 8 パズルでは配列を利用しましたが、10
パズルではハッシュに変更しました。ハッシュのキーに新しく生成した盤面を値に生成元の盤面を格納し、
正解手順の生成に利用します。
- Line 11〜17: 新しい盤面の生成
- 8 パズルでの新しい盤面の生成は１行の substr() でできましたが、10 パズルでは少し複雑になります。
現在の空きマス目の位置 $cp と次の位置 $np の関係を調べ、条件分岐の中で文字列を置き換えます。
if ($np + 1 == $cp) { # 空きマス目を左に移動
substr($work, $cp + 1, 1) = substr($work, $np, 1, '_');
} elsif ($np == $cp + 1) { # 空きマス目を右に移動
substr($work, $cp, 1) = substr($work, $np + 1, 1, '_');
} else { # 空きマス目を上下に移動
substr($work, $cp, 2) = substr($work, $np, 2, '__');
}
- Line 22〜30: パズルの問題の生成
- 新しく生成した盤面の末尾が空きマス目 (if ($work =~ /__$/))
の場合は、パズルの問題として出題することができます。パズル問題用のデータ形式は、次のようにしています。
16329a5478__:8:9|8|4|5|1|2|6|10
上のデータは、コロンで区切られたの３つの部分からなります。最初が出題用の盤面、２番目が手数、
３番目が正解手順です。正解手順は空きマス目の移動軌跡で、縦棒で区切られています。
生成したパズル問題用のデータは、その都度 @ques 配列に保存しておきます。
- Line 35: パズルの問題集をファイルに書き出す
公開している CGI パズル「10 パズル」は、上のプログラムで問題集を作成しました。10
パズルの全盤面数は 32,400 で、末尾が空きマス目の盤面数はゴールの盤面を含めて 3,600 あります。
その中から、ゴールの盤面と最初からほとんど並んでいるのものを除いた 3,591 問を出題しています。
ほとんど選別なく全部出題しているので、問題数が多いかもしれません。
多すぎるのもよくないように思えるので、将来的には少なくしようと思っています。なお、10
パズルの手数別の盤面数は次のようになっています。カッコ内の数字は、末尾が空きマス目の盤面数です。
0: 1 (1)
1: 2 11: 248 21: 2557 31: 41
2: 4 12: 418 (76) 22: 3321 (670) 32: 52 (12)
3: 8 13: 489 23: 2650 33: 12
4: 16 (2) 14: 793 (144) 24: 3082 (631) 34: 4 (3)
5: 20 15: 890 25: 2075
6: 39 (8) 16: 1407 (297) 26: 2189 (441)
7: 60 17: 1453 27: 1254
8: 107 (24) 18: 2131 (423) 28: 1075 (229)
9: 124 19: 2037 29: 430
10: 210 (40) 20: 2854 (534) 30: 297 (67)
通常、盤面数は、手数が増えるにしたがい増加し、やがて頂点に達して、
その後減っていって収束します。上の手数別の盤面数を見てみると、２つのことに気がつきます。
１つ目は末尾が空きマス目の盤面はすべて偶数手であること、
２つ目が奇数手の盤面数と偶数手の盤面数に凸凹があることです。例えば盤面数増加中の 18 手目が 2,131 で次の 19
手目が 2,037 になっていて、その次の 20 手目が 2,854 になっているところなどです。
この２つは、空きマス目の移動できるマス目が奇数手と偶数手で決まっていて、
その数が異なっていることに起因します。次の図は、橙色で奇数手の空きマス目の位置、
水色で偶数手の空きマス目の位置を示したものです。
| 8 パズル | | 10 パズル (偶数手) |
| 10 パズル (奇数手) |
|
| |
| |
|
参考までに図示してある 8 パズルは、空きマス目が１つのためきれいな市松模様になります。
10 パズルは 8 パズルと違って１つの図で示すことができないため、２つに分けてあります。
図を見ると、奇数手の空きマス目の位置数が偶数手の位置数より１つ少ないことがわかります。10
パズルの奇数手の盤面数は 14,400 で、偶数手の盤面数 18,000 より 3,600 少ないことになります。
このため、奇数手の盤面数と偶数手の盤面数に凸凹が発生します。ちなみに、4 x 4 盤面の 15 パズルや 14
パズルでは、奇数手の空きマス目の位置数と偶数手の空きマス目の位置数が同じなので、
盤面数の凸凹は発生しません。
(2008/01/01)
TopPage