今回の「14 パズル」は、前回の「10 パズル」の解説の続きです。 今回の解説の主眼は、14 パズルでの長手数問題の作成です。次の図は、14 パズルの最長手数である 54 手問題の１つとゴール図です。
| 54 手問題 | ゴール図 | |||||||||||||||||||||||||||||||||
|
|
ルールを簡単におさらいしておくと、空きマス目２つは離ればなれになることなく、 一緒に盤面内を動き回ることだけです。数字マス目側から見ると、次の２つとなります。
14 パズルの盤面数は、15 パズルの盤面数 (10,461,394,944,000) よりもはるかに少ないとはいえ、76,204,800 あります。10 パズルの盤面数は 32,400 ですので全盤面探索ができましたが、14 パズルの盤面数は 10 パズルの 2,352 倍あり、全盤面探索は難しいものがあります。そこで、14 パズルでは、できるところまで探索するという方針で行いました。プログラムは 10 パズルとほとんど違わないので、見ていただけると分かると思います。なお、２桁の数字 10, 11, 12, 13, 14 のマス目は、プログラムでは a, b, c, d, e の１文字で扱っています。
14 パズルの盤面生成プログラム use strict; 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, 12], 9 => [5, 8, 10, 13], 10 => [6, 9, 14], 12 => [8, 13], 13 => [9, 12, 14], 14 => [10, 13]); my @search = (join '', 1 .. 9, 'a' .. 'e', '__:0:'); my @board = @search; my $fno = 19; my $generated = {}; push @{$generated->{1234}->{5678}}, '9abcde__'; while (@search) { my ($board, $step, $pp) = split /:/, shift(@search); my $cp = index $board, '__'; foreach my $np (@{$move{$cp}}) { next if $np == $pp; my $work = $board; 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, '__'); } my ($k_1, $k_2, $tail) = $work =~ /^(....)(....)(.+)$/; next if grep { $tail eq $_ } @{$generated->{$k_1}->{$k_2}}; push @{$generated->{$k_1}->{$k_2}}, $tail; push @search, join('', $work, ':', $step + 1, ':', $np); if ($fno < $step) { # 手数毎にファイルに保存 $fno++; open OUT, ">b4x4_$fno.dat" or die "Can't open b4x4_$fno.dat: $!"; print OUT join("\n", @board), "\n"; close OUT; @board =(); } push @board, join('', $work, ':', $step + 1, ':', $board); } }
10 パズルのプログラムと違うのは、探索途中でファイルに保存しているところです。0 手目から 20 手までの盤面を b4x4_20.dat というファイルに保存し、それ以降は１手ごとにファイル名に手数を含んだ (b4x4_21.dat, b4x4_22.dat, ...) 別ファイルに保存します。 このようにすることで、プログラムの実行途中で中止したとしても、生成した盤面データを残すことができます。 実際、プログラムは様子を見ながら実行したのですが、35 手まで実行して中止することとなりました。 以下は、各手数で生成した盤面数、要した時間などです。
手数 盤面数(末尾__) 時間(秒) 手数 盤面数 (末尾__) 時間(秒)
0 - 20: 192,322(17,486) 5s 28: 1,131,668(175,566) 40s
21: 99,566 3s 29: 1,509,283 54s
22: 146,138(21,831) 4s 30: 1,979,841(309,180) 74s
23: 212,767 7s 31: 2,594,927 98s
24: 305,101(45,981) 10s 32: 3,200,047(505,055) 129s
25: 433,163 14s 33: 3,931,564 162s
26: 665,432(93,059) 20s 34: 4,706,126(754,195) 211s
27: 883.715 28s 35: 5,475,866 9,704s
35 までで生成した盤面数は 27,305,577 で全盤面 76,204,800 の 35.8% に止まり、かかった時間は 34 手までで859 秒 (14 分 19 秒) です。34 手までは順調に進んだのですが、35 手目の生成に 9,704 秒もかかりました。パソコンには 2GB の RAM が積んであったのですが、スラッシングが発生してしまいました。 こうなるとプログラムの処理は遅々として進まなくなり、これ以上は無理と判断してして中止しました。
35 手までの盤面はファイルに保存してあるので、簡単なスクリプトを書くことで 34 手までの問題を作成することができます。 各手数の丸カッコ内が、問題として出題できる右下が空きマス目の盤面数です。この中から盤面を選んで、 ゴール図までの手順を求めると問題を作成できます。10 パズルの最長手数は 34 手ですので、盤のサイズの大きい 14 パズルでは、10 パズルの最長手数よりも長い問題を出題したいものです。長い手数の問題を作成する方法として、 双方向探索があります。双方向探索とは、ゴールの盤面と問題の盤面の両方から探索して結合させるものです。
双方向探索のメリットは、少ない盤面の生成で長手数の問題を作成できることです。34 手問題を例にすると、ゴール図からの探索では 33 手までの全盤面 17,123,585 を生成した後に 34 手目を生成することができます。これに対して双方向探索では、ゴール図とランダムに生成した問題図から盤面を生成し 17 手目で照合して合致するものがあれば 34 手問題を作成することができます。17 手目までに生成する盤面数は 51,560 で、合計しても 103,120 に過ぎません。ゴール図からの探索と比較すると、盤面の生成数は実に 1/166 ですみます。むろん双方向探索にも、デメリットがあります。 ゴール図からの探索では１度の盤面の生成で済むのに対して、 双方向探索では繰り返し問題図の生成をしなければなりません。 それでも、メモリ不足によるスラッシングを避けて長手数問題を作成することができのです。
双方向探索を行うには、正解のある盤面配置の問題図を生成する必要があります。 数字マス目を偶数回入れ替えて問題図をランダムに生成する方法があるのですが、 すべての問題図を網羅的に探索することはできません。問題図を網羅的に生成するには、 順列の生成プログラムを応用することができます。次のプログラムは、一風変わった順列生成プログラムです。
順列生成プログラム use strict; my @perm; my @list = 'a' .. 'd'; my @order = (0) x @list; $order[-2] = -1; for (my $limit = 1, my $i = $#order - 1; $i >= 0; $limit++, $i--) { if ($order[$i] < $limit) { # 各桁のインクリメント $order[$i]++; # my @list = 'a' .. 'd'; # push @work, splice(@work, $_, 1) foreach @order; # push @perm, join('', @list); @list[$i .. $#list] = sort @list[$i .. $#list]; splice @list, $i, 0, splice(@list, $i + $order[$i], 1); push @perm, join('', @list); $limit = 1; $i = $#order - 1; redo; } else { # 桁上がり $order[$i] = 0; } } my $line = eval join('*', 2 .. @list - 1); foreach my $i (0 .. $line - 1) { print join(' ', @perm[grep { $_ % $line == $i } 0 .. $#perm]), "\n"; }
上のプログラムを実行すると、a, b, c, d の４文字の順列を画面に表示します。 なお、my @list = 'a' .. 'd'; の 'd' を 'e', 'f' などに変更すると、何文字の順列でも生成します。 今までの解法プログラムでは順列の生成に再帰呼び出しを使ったものが多かったのですが、 今回は少し違ったものを考えてみました。Higher-Order と呼ばれる方法をを参考に実装してみたものです。 プログラムの中で重要な役割を果たすのが、@order 配列です。@order 配列は、@list から要素を取り出す順番を示しています。for ループによって @order は、(0, 0, 0, 0), (0, 0, 1, 0) ... (3, 2, 0, 0), (3, 2, 1, 0) のリストを生成します。
@order (0, 0, 0, 0) a, b, c, d (0, 0, 1, 0) a, b, d, c (0, 1, 0, 0) a, c, b, d (0, 1, 1, 0) a, c, d, b (0, 2, 0, 0) a, d, b, c (0, 2, 1, 0) a, d, c, b (1, 0, 0, 0) b, a, c, d ・・・ (2, 2, 1, 0) c, d, b, a (3, 0, 0, 0) d, a, b, c (3, 0, 1, 0) d, a, c, b (3, 1, 0, 0) d, b, a, c (3, 1, 1, 0) d, b, c, a (3, 2, 0, 0) d, c, a, b (3, 2, 1, 0) d, c, b, a
最初の (0, 0, 0, 0) を使って、@list からの要素の取り出しを見てみましょう。 (0, 0, 0, 0) の各数字は、@list から取り出す要素の添字の数字を示しています。 ここで注意を要するのは、各数字は取り出された後の配列に適用されることです。まず、(0, 0, 0, 0) の１番目の 0 によって、@list から 'a' が取り出され、@list は ('b', 'c', 'd') になり、次の２番目の 0 は ('b', 'c', 'd') から 'b' を取り出し @list は ('c', 'd') になり、３番目の 0 は ('c', 'd') から 'c' を取り出し、最後の 0 が残っている 'd' を取り出します。このようにして、順番に取り出していきます。なお、@order の最後の要素は、必ず 0 であり省略することもできます。最後の (3, 2, 1, 0) では、逆順に取り出すことになるので d, c, b, a となります。
@order の各リストは、@list の初期の固定された要素 ('a', 'b', 'c', 'd') からの取り出す順番を示しています。基本原理に忠実に書くとコメント化してある３行になるのですが、@list の要素数が多くなると効率が悪くなるため、直前の結果を受け継ぎつつ次々に順列を生成するように改めています。
上のプログラムを使って盤面配置を生成できるのですが、１つ問題があります。 「正解のある盤面配置」と「不可能な盤面配置」の両方が生成されてしまうことです。 不可能な盤面配置を判定するには、転倒数を数えるという方法があります。 ここでは、理解のしやすい空きマス目が１つの 8 パズルを例に説明してみましょう。 次の図は、適当に数字を配置したものです。
|
1: 3 2: 1 3: 3 4: 0 5: 0 6: 2 7: 1 8: 0 |
転倒数とは、各数字の左側または上側に配置されている自身よりも大きな数字の数のことです。3 を例にすると、左側または上側に配置されている 4, 2, 5, 1, 8 のうち 4, 5, 8 が 3 より大きいので転倒数は 3 ということになります。各数字の転倒数は、図の右側に記しています。 スライドパズルでは、この転倒数の合計値が奇数か偶数かによって、「正解のある盤面配置」かまたは 「不可能な盤面配置」かを判定することができます。 転倒数の判定は盤面の大きさや空きマス目の列の位置によって異なるのですが、 空きマス目を右下に限定すれば、偶数の場合は「正解のある盤面配置」、 奇数の場合は「不可能な盤面配置」ということになります。上の図は、転倒数の合計値が 10 で偶数ですので正解のある盤面配置です。実は、プログラムの @order は転倒数を表しています。@order の各数字は右側または下側にある自身より小さな数字の数を意味していますが、転倒数の合計値と同じ数になります。 参考までに、8 パズルの「正解のある盤面配置」の生成プログラムは次のようになります。
8 パズルの「正解のある盤面配置」生成プログラム use strict; my @ques; my @list = 1 .. 8; my @order = (0) x @list; $order[-2] = -1; for (my $limit = 1, my $i = $#order - 1; $i >= 0; $limit++, $i--) { if ($order[$i] < $limit) { $order[$i]++; @list[$i .. $#list] = sort @list[$i .. $#list]; splice @list, $i, 0, splice(@list, $i + $order[$i], 1); push @ques, join('', @list, '_') unless eval(join '+', @order) % 2; # 転倒数の合計値をチェック $limit = 1; $i = $#order - 1; redo; } else { $order[$i] = 0; } }
ごく簡単なプログラムですが、これで「正解のある盤面配置」の問題図がすべて配列 @ques に格納されます。順列生成プログラムと異なるのは、転倒数をチェックしている１行のみです。この 8 パズルのプログラムを、空きマス目が２つのスライドパズルにはそのまま使用できません。 転倒数の数え方が異なるためです。 14 パズルの転倒数は、次の図のように数えます。
| 奇数列 | 偶数列 1: 5 3: 1 | 2: 0 4: 4 5: 4 7: 0 | 6: 0 8: 0 9: 2 11: 0 | 10: 2 12: 0 13: 0 | 14: 0 |
空きマス目２つのスライドパズルの各数字は、同じ列か１列間をおいた列にしか移動できません。 そのため 14 パズルの転倒数は、奇数列と偶数列を別々に数えてそれぞれの合計値が偶数になる必要があります。 上の図は、奇数列の転倒数の合計値が 12 で、偶数値の合計値が 6 なので「正解のある盤面配置」になります。 14 パズルの「正解のある盤面配置」生成プログラムは、奇数列と偶数列を別々に順列を生成して組み合わせたものになります。
14 パズルの「正解のある盤面配置」生成プログラム use strict; my @ques; my @odd = (1, 3, 5, 7, 9, 'b', 'd'); my @o_order = (0, 0, 0, 0, 0, -1, 0); for (my $o_limit = 1, my $i = $#o_order - 1; $i >= 0; $o_limit++, $i--) { if ($o_order[$i] < $o_limit) { $o_order[$i]++; @odd[$i .. $#odd] = sort @odd[$i .. $#odd]; splice @odd, $i, 0, splice(@odd, $i + $o_order[$i], 1); unless (eval(join '+', @o_order) % 2) { # 奇数列の転倒数をチェック my @even = (2, 4, 6, 8, 'a', 'c', 'e'); my @e_order = (0, 0, 0, 0, 0, -1, 0); for (my $e_limit = 1, my $j = $#e_order - 1; $j >= 0; $e_limit++, $j--) { if ($e_order[$j] < $e_limit) { $e_order[$j]++; @even[$j .. $#even] = sort @even[$j .. $#even]; splice @even, $j, 0, splice(@even, $j + $e_order[$j], 1); unless (eval(join '+', @e_order) % 2) { # 偶数列の転倒数をチェック push @ques, join('', map( { $odd[$_], $even[$_] } 0 .. 6), '__'); } $e_limit = 1; $j = $#e_order - 1; redo; } else { $e_order[$j] = 0; } } } $o_limit = 1; $i = $#o_order - 1; redo; } else { $o_order[$i] = 0; } }
外側の for ループで奇数列の順列を生成し、内側の for ループで偶数列の順列を生成し、 奇数列と偶数列を交互に並べて末尾に空きマス目２つを加えて盤面を作成しています。 生成される盤面数は、空きマス目が末尾に固定されているので 6,350,400 (7! / 2 * 7! / 2) になります。実行時間は、私のパソコンで 508 秒かかりました。
いま手元には、最初のプログラムで作成したディスクに保存してある 35 手までの盤面データと、前節の「正解のある盤面配置」を生成するプログラムがあります。 次が、この２つを使って双方向探索をするプログラムです。プログラムの実行には、私のパソコンで 1,101,337 秒 (30h 5m 33s) かかりました。
14 パズルの長手数問題作成プログラム use strict; my (@generated, %skip, @connect, %long_q, %analyze); my $f_max = 31; # 生成済み盤面データの読み込み foreach my $fno (20 .. $f_max) { open IN, "b4x4_$fno.dat" or die "Can't open b4x4_$fno.dat: $!"; while (my $line = <IN>) { chomp $line; my ($board, $step, $pre_board) = split /:/, $line; my ($k_1, $k_2, $rest) = $board =~ /^(....)(....)(.+)/; push @{$generated[$step]->{$k_1}->{$k_2}}, join(':', $rest, $pre_board); push @{$skip{$k_1}->{$k_2}}, $rest if $board =~ /__$/; push @connect, join(':', $board, $step) if $step % 2 and $fno < $f_max; } close IN; } # 「正解のある盤面配置」の生成 my @odd = (1, 3, 5, 7, 9, 'b', 'd'); my @o_order = (0, 0, 0, 0, 0, -1, 0); for (my $o_limit = 1, my $i = $#o_order - 1; $i >= 0; $o_limit++, $i--) { if ($o_order[$i] < $o_limit) { $o_order[$i]++; @odd[$i .. $#odd] = sort @odd[$i .. $#odd]; splice @odd, $i, 0, splice(@odd, $i + $o_order[$i], 1); unless (eval(join '+', @o_order) % 2) { my @even = (2, 4, 6, 8, 'a', 'c', 'e'); my @e_order = (0, 0, 0, 0, 0, -1, 0); for (my $e_limit = 1, my $j = $#e_order - 1; $j >= 0; $e_limit++, $j--) { if ($e_order[$j] < $e_limit) { $e_order[$j]++; @even[$j .. $#even] = sort @even[$j .. $#even]; splice @even, $j, 0, splice(@even, $j + $e_order[$j], 1); unless (eval(join '+', @e_order) % 2) { search(join('', map( { $odd[$_], $even[$_] } 0 .. 6), '__')); } $e_limit = 1; $j = $#e_order - 1; redo; } else { $e_order[$j] = 0; } } } $o_limit = 1; $i = $#o_order - 1; redo; } else { $o_order[$i] = 0; } } sub search { my $ques = shift; my ($k_1, $k_2, $rest) = $ques =~ /^(....)(....)(.+)/; # 生成済みか否かのチェック if (grep { $rest eq $_ } @{$skip{$k_1}->{$k_2}}) { $analyze{skip}++; return; } my %convert = map { substr("123456789abcde", $_, 1) => substr($ques, $_, 1) } 0 .. 13; my %reconvert = reverse %convert; for (my $i = 0; $i <= $#connect; $i++) { my ($board, $step) = split /:/, $connect[$i]; $board = join('', map { $_ eq '_' ? '_' : $convert{$_} } split //, $board); my ($sk_1, $sk_2, $srest) = $board =~ /^(....)(....)(.+)/; next unless defined $generated[$f_max]->{$sk_1}->{$sk_2}; # 照合に成功 if (grep { $srest eq substr($_, 0, 8) } @{$generated[$f_max]->{$sk_1}->{$sk_2}}) { my $q_step = $step + $f_max; $analyze{$q_step}++; my @route = (index $board, "__"); # ゴールまでの手順 my $work = $board; foreach my $idx (reverse 1 .. $f_max) { my ($nk_1, $nk_2, $nrest) = $work =~ /^(....)(....)(.+)/; ($work) = grep { $nrest eq substr($_, 0, 8) } @{$generated[$idx]->{$nk_1}->{$nk_2}}; $work = substr($work, 9); push @route, index($work, "__"); } # 問題図までの手順 $work = join('', map { $_ eq '_' ? '_' : $reconvert{$_} } split //, $board); foreach my $idx (reverse 2 .. $step) { my ($nk_1, $nk_2, $nrest) = $work =~ /^(....)(....)(.+)/; ($work) = grep { $nrest eq substr($_, 0, 8) } @{$generated[$idx]->{$nk_1}->{$nk_2}}; $work = substr($work, 9); unshift @route, index($work, "__"); } # 問題図の保存 push @{$long_q{$q_step}}, join(':', $ques, $q_step, join('|', @route)); splice @{$long_q{$q_step}}, int(rand 201), 1 if @{$long_q{$q_step}} > 200; return; } } $analyze{over}++; print "step > ", $f_max * 2 - 2, "\n"; } open OUT, ">long_q.dat" or die "Can't open long_q.dat: $!"; foreach my $key (sort keys %long_q) { print OUT join("\n", @{$long_q{$key}}), "\n"; } close OUT; foreach my $key (sort keys %analyze) { print "$key => $analyze{$key}\n"; }
プログラムの冒頭で、ディスク保存してある盤面データを読み込みます。 保存してある盤面数は、35 手までの 27,305,577 になります。最初に全部読み込んでみたのですが、 メモリを使いきって作業領域が残らないため、31 手までの 9,993,974 を読み込みました。 ここで、プログラムで使用する主要な配列とハッシュの役割について説明しておきます。
@generated = ({...}, {1234 => {5678 => ["9a__debc:123456789abcde__"]}}, ....)
このハッシュは、正解手順を求めるために使用します。生成元の盤面をたどることで、 ゴール図までの手順を得ることができます。
%skip = ({1234 => {5678 => ["9abcde__"]}}, .....)双方向探索の一方はファイルから読み込んだゴール図からの盤面データ、 もう一方は前節で説明した順列生成プログラムが生成した「正解のある盤面配置」になります。 順列生成のコードが問題図の盤面を１つ生成したら、search サブルーチンを呼び出して探索を始めます。search サブルーチンは、次の順序で処理を進めます。
生成済みか否かのチェック
引数として渡された問題図の盤面が
%skip ハッシュに含まれている場合は、$analyze{skip} をインクリメントしてスキップします。
問題図からの盤面の生成
問題図からの盤面の生成は、改めて空きマス目を動かしながら生成する必要はありません。
ゴールの盤面と問題図の盤面との対応テーブルを作成して、ゴールからの盤面を変換するすることで生成できます。
次の図は、実際の 44 手の問題です。
| ゴール図 | 44 手問題図 | |||||||||||||||||||||||||||||||||
|
|
my %convert = map { substr("123456789abcde", $_, 1) => substr($ques, $_, 1) } 0 .. 13;
# 作成されるハッシュ (プログラムでは２桁の数字は記号化されています)
%convert = ( 1 => 9, 2 => 8, 3 => 5, 4 => 12, 5 => 1, 6 => 10, 7 => 7, 8 => 14,
9 => 3, 10 => 2, 11 => 13, 12 => 6, 13 => 11, 14 => 4);
問題図から１手目の盤面を生成するには、ゴール図からの１手目の盤面を取り出して %convert を通すことで行えます。同じように２手目以降も %convert ハッシュを通すことで生成できます。
照合の進め方
問題図から生成した１手目の盤面の照合は、
奇数手と偶数手では空きマス目の位置が違うため、ゴールからの奇数手の盤面と行うことになります。
そのうち 29 手以下の奇数手とは照合を行う必要はなく、最後の 31 手目と照合すれば済みます。１手目の盤面が
29 手以下に含まれていると仮定した場合、次の手数目に問題図が含まれていることになるからです。問題図が
30 手以下に含まれていないことは、%skip ハッシュで確認済みです。
また、問題図から生成した偶数手は照合の必要がありません。例えば１手目から生成した２手目が 30
手に含まれていると仮定した場合、１手目が 31 手目に含まれることになるからです。
結局、問題図から生成した奇数手を、ゴール図から生成した最後の 31 手目と照合すればよいことになります。
@connect 配列には「盤面:手数」という形式で、ゴール盤面から生成された 29 までの奇数手の盤面が手数順にすべて格納されています。この @connect 配列の盤面を１つずつ取り出して、%convert ハッシュで変換しながら 31 手目と照合を進めます。@connect 配列のすべてが照合が失敗した場合は、62 手以上かかる問題図であったことになります。照合が成功して同じ盤面があった場合は、 １つの長手数問題が生成できたことになります。配列の要素には手数が含まれていますので、その手数に 31 を加えたものが問題図の手数ということになります。
正解手順の求め方と問題図の保存
正解手順は、空きマス目の移動軌跡という形式で表します。
照合が成功した場合に、ゴール図までの手順は、@generated の生成元の盤面をたどることで求めることができます。
また、問題図までの手順は記録していませんが、照合に成功した盤面を %reconvert
ハッシュを通して戻すことで @generated から盤面を見つけることができます。
そして、見つけた盤面からゴール図までの手順が、問題図までの手順になります。
この２つの手順を繋げることで、正解手順を得ることができます。
これで、１つの長手数問題の作成ができたことになります。問題図、手数、正解手順を : (コロン) で繋いで、%long_q ハッシュに手数毎に保存しておきます。すべての問題を保存しておくと膨大な数になりますので、 手数毎に最大 200 にしています。
プログラムの実行が終了すると、%long_q ハッシュに保存してある長手数問題が long_q.dat という名前のファイルに書き出されています。long_q.dat は、「14 パズル」でそのまま使用できる次のようなフォーマットになっています。
14ba5e729cd638__:32:13|9|5|6|2|1|0|4|8|9|5|4|8|12|13|9|8|4|5|6|10|14|13|9|8|4|0|1|5|6|10|14 12ba7cd436985e__:32:13|9|5|6|10|9|5|6|2|1|0|4|8|12|13|14|10|6|5|4|0|1|2|6|5|4|8|12|13|9|10|14 3e541cd6b89a72__:32:13|12|8|4|5|1|2|6|10|14|13|9|8|4|5|6|10|14|13|12|8|4|5|6|2|1|0|4|5|6|10|14 329e5478dc16ba__:32:13|12|8|4|5|6|10|9|8|4|5|6|2|1|0|4|5|6|10|9|8|4|5|1|2|6|10|14|13|9|10|14 941a3c567eb2d8__:32:13|9|10|6|2|1|5|6|10|9|5|4|0|1|2|6|10|14|13|9|8|4|5|6|2|1|5|6|10|9|13|14
「14 パズル」では、データファイルから１行を読み出してパズルを出題します。 コロンで区切られた最初のデータから盤面を配置し、２番目の手数データを最小手数として表示します。 ３番目の正解手順はパズルの表面には現れませんが、ブラウザの「ページのソース」で見ることができます。 「ページのソース」の 28 行目あたりに var ans = "13, 9, 5, 6, ..." がありますので、 正解手順を知りたい場合は見てください。
プログラムの最後に、%analyze に記録してある手数毎の盤面数を表示します。 総盤面数 6,350,400 の各手数毎の内訳は、次のようになりました。なお、skip は、30 手以下の合計数です。
32 => 505,055 44 => 336,080
34 => 754,195 46 => 95,763
36 => 1,006,354 48 => 16,248
38 => 1,160,058 50 => 1,778
40 => 1,071,792 52 => 87
42 => 739,880 54 => 7
skip => 663,103
プログラムは最長で 60 手までしか探索できできないので、62 手以上かかるものがあるのを心配したのですが、結果的に最長手数は 54 手でした。もっとも盤面の多い手数は、38 手で 1,160,058 ありました。他の空きマス目も含めると、 約６倍になりますので、38 手だけで 696 万くらいの盤面数があることになります。14 パズルの最長手数は探索していませんが、空きマス目を右下に限定しない全盤面でも、最長手数は 54, 55 手あたりになるのではないかと思われます。最長の 54 手の問題図は、次の７つがありました。
b4d2 9678 5c3a 1e__ d4b2 5678 9c3a 1e__ d4b2 7698 5c3a 1e__ d4b2 7698 5e3c 1a__ d4b2 9658 7c3a 1e__ d4b2 9658 7e3c 1a__ d4b2 9678 5c1a 3c__
残念ながら、盤面配置はどれも似通ったものです。１列目は１つを除いて同じですし、 他の列も似たようなものです。もう少しバラエティに富んでいればすべて出題できたのですが、 同じような配置が続いてしまうので実際のパズルでは２題のみにしました。