前の記事の続き.

<解けない盤面の存在>
 初期盤面は作り方のよって,ゴール状態に移動できないものも数多く(正確にはちょうど半分)存在する.15パズルに関し,懸賞問題も歴史的にあったらしいが,結局それが解けないことは後ほど証明されてしまった.

解答可能かどうかの判定に「転倒数」をまず数える.つまり,ゴール状態に比べ,盤面の1次元配列記述において,位置が前後に転倒してしまった数を累計する.

前の記事トップの盤面を例に取って「転倒数」を計算しよう.

数字の2が,ゴール状態では数字11の前に来るはずなので,転倒数は1となる.数字8の転倒数も1.数字5は数字11と8の前に来るべきなので,転倒数は2となる.以下は残りの数字すべてを列挙する.

 数字 11(に対応する転倒数は 0),数字 2(転倒数 1),数字 8(1),数字 5(2),13(0),14(0),10(3),12(2),4(7),3(8),1(10),7(6),9(5),15(0),6(9)

転倒数の合計は 0+1+1+2+0+0+3+2+7+8+10+6+5+9 = 54.

つぎに,その合計数と空白箇所(スペース)の行番号との和が偶数かどうかを見る.偶数であれば解答可能,奇数であれば解答不可能になる.

今の例では,転倒数の合計は54,空白位置の行番号は4なので,和は58,偶数である.従って解答可能な初期盤面といえよう.

また,歴史的に有名な解答不可能懸賞問題 14-15パズルでは,数字14だけが転倒しているので,その転倒数は1,転倒数の合計も1.空白位置の行番号4と合わせると和は5となり,奇数である.従って解答不可能である.いくら頑張っても,ゴール状態に決して辿りつけない訳で,懸賞金をもらうはずはない.

われわれのプログラムでも,まず解答可能かどうかを判定し,解答不可能な入力データをはじけておかないといけない.

以下はその判定部分に関わるプログラム.関数の引数 r0 は空白の行番号(C言語では習慣として 0からカウントするので,実際の行番号よりは1だけ数字が小さい).関数 solvable() のリターン値が1であれば解答可能,0であれば解答不可能のことを示す.

(プログラムの説明) 変数 n に転倒数の合計が入る.layout は盤面の1次元配列.r0 は空白位置の行番号(0~3).

<プログラムを組み立てる>
 すべての盤面やその盤面に関係するパラメータを管理しているのは move テーブル.その構造体は以下の通り.

以下は解答プログラム.キタナイ書き方をしていて,申し訳ない.とくに上下左右の移動に関する部分.テーブルにすれば4方向重複しなくて済むはずだが.

C言語解答プログラム: Solution for UVa 10181 15-Puzzle Problem (C program)
計算時間: 0.078秒

計算時間のランキング表に,0.000秒のような,極限にまで高速に計算できた解答も見受けられる.IDA*アルゴリズムをつかおうかな.あるいは,もっと凄いアルゴリズムが存在しているかも.

Comments are closed.

Post Navigation