パズル問題解法のアルゴリズム講座
実践編
バックトラック
１．バックトラックの考え
人が行う「試行錯誤という行為」を忠実に実行するように考え出されたアルゴリズムで利用範囲は広範です。もちろん不得意分野もあります。
複数の未知のものを上手く組み合わせて、ある条件を満たす全体を得るのに、その未知のものを
ひとつずつ許される範囲内で「もし、こう仮定して」さらにこの状態から「次に、こう仮定して」
というように仮定から仮定へと強引に突き進みます。
そんなことをすれば大抵は途中で行き詰ってしまいます。その時は1歩戻って(バックトラッキング)
仮定を立て直して、また、突き進みます。総ての仮定に失敗したら、そこからまた1歩戻って新たな仮定
を立て直して同様に進行すれば、やがては解に到達することになります。
２．バックトラック例題「2枚のカードの間には？」
ここでは例題として「2枚のカードの間には？」(Ｃマガ電脳クラブ91年4月号より)に挑戦してみます。
1から7の数字を書いたカードが2枚ずつ計14枚ある。
そしてこれを1列に並べ，2枚の1の間にはカードが1枚，
2枚の2の間にはカードが2枚はさまれていて,同様に，
3の間には3枚,4の間には4枚,5の間には5枚,6の間には
6枚,7の間には7枚のカードがはさまれるように14枚の
カードを並べて下さい。
３．例題をバックトラックで解く。
次の２つを基本方針として考えることにする。
１．[１]のカードからペアで順番に配置していく。
２．仮定は左側への可能な配置から順次試していく。
この方針で強引に仮定から仮定へと突き進むと、右上図のようになる。
ここで行き詰まったので、５を取り除き、１歩戻って４の配置を変更する。
こんなことの繰り返しをプログラムに実行させようとすると次のようになります。
|
Ｃ言語ソースリスト
Javaアプレットの実行 |
尚、1のカードから順に配置するようにしていますが、本当は
7のカードから順に配置した方が無駄な探索を少なく出来ます。
backtrack()を最初に呼び出すのは、backtrack(1)です。
int LETSU[]; /* カードを置いていく列テーブル */
/* No.pのカードをいろいろ置いてみる(バックトラック) */
void backtrack(int p) {
int i; /* 左カードの位置 */
int j; /* 右カードの位置 */
if (p > 7) { /* 総てのカードが置かれている */
(配置を表示する等の処理:省略);
} else {
for (i=0, j=p+1; j < 14; i++, j++) {
if (LETSU[i]==0 && LETSU[j]==0) { /* カードを置けるなら */
LETSU[i] = LETSU[j] = p; /* カードを置く(仮定) */
backtrack(p+1); /* 再帰で次のNo.カードへ */
LETSU[i] = LETSU[j] = 0; /* 状態を元に戻す */
}
}
}
}