前回の続きです。今回は 9 パズルを反復深化と下限値枝刈り法で解いてみましょう。
拙作のページ「経路の探索」で説明したように、反復深化は最短手数を求めることができるアルゴリズムです。幅優先探索と違って局面を保存する必要が無いため、必要となるメモリは深さ優先探索と同程度で済みます。また、プログラムも深さ優先探索と同じくらい簡単に作成することができます。
ただし、同じ探索を何度も繰り返すため実行時間が増大する、という欠点があります。ようするに、使用するメモリは少ないが実行時間が長くなるアルゴリズムなのです。実行時間が長くなるといっても、枝刈りを工夫することでパズルを高速に解くことができます。メモリ不足になる場合には、積極的に使ってみたいアルゴリズムといえるでしょう。
幅優先探索では全ての局面を保存しましたが、反復深化ではその必要はありません。盤面は配列 board で表し、駒の移動は board を書き換えて、バックトラックする時は元に戻すことにします。動かした駒はスライス movePiece に格納します。動かした駒がわかれば局面を再現できるので、それで移動手順を表すことにしましょう。
なお、単純な反復深化では時間がかかるので、拙作のページ「反復深化と下限値枝刈り法」で説明した「下限値枝刈り法」を使うことにします。
さて、9 パズルの下限値ですが、これにはいろいろな方法が考えられます。今回は、各駒が正しい位置へ移動するまでの手数 (移動距離) [*1] を下限値として利用することにしましょう。次の図を見てください。
┌──┬──┬──┬──┬──┐ ┌─┬─┬─┬─┬─┐
│ │5(3)│3(0)│2(2)│1(4)│ │１│２│３│４│５│
├──┼──┼──┼──┼──┤ ├─┼─┼─┼─┼─┤
│9(3)│4(3)│8(0)│7(2)│6(4)│ │６│７│８│９│ │
└──┴──┴──┴──┴──┘ └─┴─┴─┴─┴─┘
スタート (21 手) 完成形
図 : 下限値の求め方
たとえば、右上にある 1 の駒を左上の正しい位置に移動するには、最低でも 4 手必要です。もちろん、ほかの駒との関連で、それ以上の手数が必要になる場合もあるでしょうが、4 手より少なくなることは絶対にありません。同じように、各駒について最低限必要な手数を求めることができます。そして、その合計値はパズルを解くのに最低限必要な手数となります。これを下限値として利用することができます。ちなみに、上図左の下限値は 21 手になります。
下限値枝刈り法を使う場合、下限値の計算を間違えると正しい解を求めることができなくなります。たとえば、10 手で解ける問題の下限値を 11 手と計算すれば、最短手数を求めることができなくなります。それどころか、10 手の解しかない場合は、答えを求めることすらできなくなります。下限値の計算には十分に注意してください。
9 パズルや 15 パズルの場合、スタートの空き場所の位置とゴールの空き場所の位置から、解の手数が偶数になるのか奇数になるのか簡単に判定することができます。この場合、探索の上限値を 1 手ずつではなく 2 手ずつ増やすことができます。これで実行時間を大幅に短縮することができます。
判定は簡単です。次の図を見てください。
┌─┬─┬─┬─┬─┐
│１│０│１│０│１│
├─┼─┼─┼─┼─┤
│０│１│０│１│０│
└─┴─┴─┴─┴─┘
パリティ
┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
│ │５│３│２│１│ │１│２│３│４│５│
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│９│４│８│７│６│ │６│７│９│８│ │
└─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
スタート ゴール
空場所のパリティ : 1 空場所のパリティ : 0
パリティが異なる場合 : 手数は奇数回
パリティが同じ場合 : 手数は偶数回
図 : 手数の偶奇性
盤面を市松模様に塗り分けます。上図のパリティでは 0 と 1 で表しています。スタートからゴールに到達するまで、空き場所はいろいろな位置に移動しますが、同じパリティの位置に移動する場合は偶数回かかり、異なるパリティの位置に移動する場合は奇数回かかります。
たとえば、スタートで駒 9 を 1 回動かすと、空き場所は下の位置に移動しますね。この場合、移動回数は奇数でパリティの値は 1 から 0 に変わります。スタートから駒 9 と 4 を動かすと、移動回数は偶数でパリティの値は 0 のままです。このように、同じパリティの位置に移動する場合は偶数回、異なるパリティの位置に移動する場合は奇数解となるのです。上図のスタートとゴールの場合、空き場所のパリティが異なるので、奇数回かかることがわかります。
それでは、プログラムを作りましょう。最初にデータ型と大域変数を定義します。
リスト : データ型と大域変数の定義
// 盤面の型
type Board [10]int
// ゴール
var goal Board = Board{1,2,3,4,5,6,7,8,9,0}
var gSpace int = 9
// 手数の偶奇性
var parity Board = Board{
1, 0, 1, 0, 1,
0, 1, 0, 1, 0,
}
盤面を表す配列には Board という別名を付けます。ゴールの盤面は変数 goal に、その空き場所の位置は変数 gSpace にセットします。配列 parity は手数の偶奇性を判定するために使用します。
下限値の求め方ですが、駒を動かすたびに各駒の移動距離を計算していたのでは時間がかかります。9 パズルの場合、1 回に一つの駒しか移動しないので、初期状態の下限値を求めておいて、動かした駒の差分だけ計算すればいいでしょう。また、駒の移動距離はいちいち計算するのではなく、あらかじめ計算した結果を配列に格納しておきます。この配列を distance とすると、盤面から移動距離を求めるプログラムは次のようになります。
リスト : 移動距離を求める
// 距離
var distance [10][10]int = [10][10]int {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 0 dummy
{0, 1, 2, 3, 4, 1, 2, 3, 4, 5}, // 1
{1, 0, 1, 2, 3, 2, 1, 2, 3, 4}, // 2
{2, 1, 0, 1, 2, 3, 2, 1, 2, 3}, // 3
{3, 2, 1, 0, 1, 4, 3, 2, 1, 2}, // 4
{4, 3, 2, 1, 0, 5, 4, 3, 2, 1}, // 5
{1, 2, 3, 4, 5, 0, 1, 2, 3, 4}, // 6
{2, 1, 2, 3, 4, 1, 0, 1, 2, 3}, // 7
{3, 2, 1, 2, 3, 2, 1, 0, 1, 2}, // 8
{4, 3, 2, 1, 2, 3, 2, 1, 0, 1}, // 9
}
// 距離を求める
func getDistance(board *Board) int {
d := 0
for x, p := range board {
d += distance[p][x]
}
return d
}
distance は 2 次元配列で「駒の種類×駒の位置」を表しています。空き場所は関係ないので、distance[0] はダミーとなります。関数 getDistance は盤面 board にある駒と位置から移動距離を求めます。変数 v を 0 に初期化して、駒の移動距離を distance から求めて v に足し算するだけです。
次は反復深化で解を探索する関数 idSearch を作ります。
リスト : 反復深化 + 下限値枝刈り法
func idSearch(board *Board, limit, move, space, lower int, movePiece []int) {
if move == limit {
if goal == *board {
fmt.Println(movePiece[1:])
panic("finish")
}
} else {
for _, x := range adjacent[space] {
p := board[x]
if movePiece[move] == p { continue }
board[space] = p
board[x] = 0
newLower := lower - distance[p][x] + distance[p][space]
if newLower + move <= limit {
idSearch(board, limit, move + 1, x, newLower, append(movePiece, p))
}
board[space] = 0
board[x] = p
}
}
}
関数 idSearch の引数 board が盤面、limit が上限値、move が手数、space が空き場所の位置、lower が board の下限値、movePiece が動かした駒を格納するスライスです。手数が上限値に達したら、パズルが解けたかチェックします。goal に到達したら、fmt.println で手順を表示して、panic で大域脱出します。上限値に達していない場合は、駒を移動して新しい局面を作ります。
9 パズルのように、元の局面に戻すことが可能（可逆的）なパズルの場合、単純な深さ優先探索では同じ移動手順を何度も繰り返すことがあります。そうなると、とんでもない解を出力するだけではなく、再帰呼び出しが深くなるとスタックがオーバーフローしてプログラムの実行が停止してしまいます。
このような場合、局面の履歴を保存しておいて同じ局面がないかチェックすることで、解を求めることができるようになります。ただし、同一局面をチェックする分だけ時間が余分にかかりますし、最初に見つかる解が最短手数とは限りません。
反復深化では深さが制限されているため、同一局面のチェックを行わなくてもスタックオーバーフローが発生することはありません。そのかわり、無駄な探索はどうしても避けることができません。9 パズルの場合、1 手前に動かした駒を再度動かすと 2 手前の局面に戻ってしまいます。完全ではありませんが、このチェックを入れるだけでもかなりの無駄を省くことができます。
プログラムでは、スライス movePiece に移動した駒を格納しているので、1 手前と同じ駒は動かさないようにチェックしています。なお、movePiece[0] はダミーデータで 0 になります。movePiece[1] 以降のデータが実際に動かした駒になります。
駒を動かしたら差分を計算して、新しい下限値 newLower を求めます。そして、newLower + move が上限値 limit を越えたら枝刈りを行います。limit 以下であれば idSearch を再帰呼び出しします。下限値枝刈り法の実装はこれだけです。とても簡単ですね。
最後に、関数 idSearch を呼び出すプログラムを作ります。
リスト : 反復深化の実行
func main() {
start := Board{0,5,3,2,1,9,4,8,7,6}
s := time.Now()
defer func(){
recover()
e := time.Now().Sub(s)
fmt.Println(e)
}()
sSpace := 0
low := getDistance(&start)
if parity[sSpace] != parity[gSpace] {
if low % 2 == 0 { low++ }
} else if low % 2 == 1 {
low++
}
for i := low; i <= 55; i += 2 {
fmt.Println(i)
idSearch(&start, i, 0, 0, low, make([]int, 1, 56))
}
}
変数 start にスタートの盤面を格納します。idSearch は panic で大域脱出するので、それを捕捉するために defer 文の中で recover を呼び出します。次に、関数 getDistance で初期状態の下限値 low を求めます。そして、parity をチェックして、手数が奇数回で low が偶数の場合、または手数が偶数で low が奇数の場合は low の値を +1 します。あとは for ループで、上限値 i を low から 2 手ずつ増やして関数 idSearch を呼び出します。
あとのプログラムは簡単なので説明は割愛します。詳細はプログラムリスト１をお読みください。
それでは実行結果を示します。
21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 [5 3 2 1 6 7 8 4 3 2 1 6 7 8 4 1 2 5 9 3 1 2 6 7 8 4 2 6 5 9 3 1 6 2 7 5 9 3 1 6 2 7 5 8 4 5 8 9 3 2 7 8 9 4 5] 1.614519037s
実行時間は約 1.61 秒 (Go 言語 ver 1.23.2, Ubunts 22.04 (WSL), Intel Core i5-6200U 2.30GHz) でした。幅優先探索よりも少々時間はかかりますが、省メモリで解を求めることができます。なお、手数の偶奇性を使わずに上限値を 1 手ずつ増やすと、実行時間はとても遅くなります。ご注意くださいませ。
次は 1 から 11 までの数字を並べる 11 パズル (3 行 4 列盤) を反復深化で解いてみましょう。高橋謙一郎さんの「１１パズルの最適解が最長手数となる面の探索」によると、11 パズルの最長手数は 53 手で、局面は全部で 18 通りあるそうです。そのうちの一つを下図に示します。
┌─┬─┬─┬─┐ ┌─┬─┬─┬─┐
│ │３│２│１│ │１│２│３│４│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│８│７│６│５│ │５│６│７│８│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│４│11│10│９│ │９│10│11│ │
└─┴─┴─┴─┘ └─┴─┴─┴─┘
完成形
図 : 11 パズル (最長手数局面)
(出典 : １１パズルの最適解が最長手数となる面の探索)
11 パズルも 9 パズルと同じ方法で解くことができます。詳細はプログラムリスト２をお読みください。
実行結果は次のようになりました。
23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 [3 2 6 5 1 6 2 7 5 1 9 10 11 4 8 5 1 9 10 11 4 8 5 1 9 10 11 4 8 9 10 2 7 3 1 5 9 10 2 11 4 8 11 7 6 4 7 6 3 2 6 7 8] 15.639989735s
当然ですが手数は 53 手、実行時間は約 15 秒でした。これ以上の高速化は下限値の精度を上げないと無理かもしれません。
マンハッタン距離のほかには、高橋謙一郎さんが考案された ID (Invert Distance) や WD (Walking Distance) という方法があります。それらを使った 15 パズルの解法プログラムは抜群の性能を発揮しているようです。興味のある方は高橋さんのページ「１５パズル自動解答プログラムの作り方」をご覧くださいませ。
//
// nineid.go : 9 パズル (反復深化＋下限値枝刈り法)
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import (
"fmt"
"time"
)
// 隣接リスト
var adjacent[10][]int = [10][]int{
{1, 5}, // 0
{0, 2, 6}, // 1
{1, 3, 7}, // 2
{2, 4, 8}, // 3
{3, 9}, // 4
{0, 6}, // 5
{1, 5, 7}, // 6
{2, 6, 8}, // 7
{3, 7, 9}, // 8
{4, 8}, // 9
}
// 距離
var distance [10][10]int = [10][10]int {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 0 dummy
{0, 1, 2, 3, 4, 1, 2, 3, 4, 5}, // 1
{1, 0, 1, 2, 3, 2, 1, 2, 3, 4}, // 2
{2, 1, 0, 1, 2, 3, 2, 1, 2, 3}, // 3
{3, 2, 1, 0, 1, 4, 3, 2, 1, 2}, // 4
{4, 3, 2, 1, 0, 5, 4, 3, 2, 1}, // 5
{1, 2, 3, 4, 5, 0, 1, 2, 3, 4}, // 6
{2, 1, 2, 3, 4, 1, 0, 1, 2, 3}, // 7
{3, 2, 1, 2, 3, 2, 1, 0, 1, 2}, // 8
{4, 3, 2, 1, 2, 3, 2, 1, 0, 1}, // 9
}
// 盤面の型
type Board [10]int
// 距離を求める
func getDistance(board *Board) int {
d := 0
for x, p := range board {
d += distance[p][x]
}
return d
}
// ゴール
var goal Board = Board{1,2,3,4,5,6,7,8,9,0}
var gSpace int = 9
// 手数の偶奇性
var parity Board = Board{
1, 0, 1, 0, 1,
0, 1, 0, 1, 0,
}
// 反復深化 + 下限値枝刈り法
func idSearch(board *Board, limit, move, space, lower int, movePiece []int) {
if move == limit {
if goal == *board {
fmt.Println(movePiece[1:])
panic("finish")
}
} else {
for _, x := range adjacent[space] {
p := board[x]
if movePiece[move] == p { continue }
board[space] = p
board[x] = 0
newLower := lower - distance[p][x] + distance[p][space]
if newLower + move <= limit {
idSearch(board, limit, move + 1, x, newLower, append(movePiece, p))
}
board[space] = 0
board[x] = p
}
}
}
func main() {
start := Board{0,5,3,2,1,9,4,8,7,6}
s := time.Now()
defer func(){
recover()
e := time.Now().Sub(s)
fmt.Println(e)
}()
sSpace := 0
low := getDistance(&start)
if parity[sSpace] != parity[gSpace] {
if low % 2 == 0 { low++ }
} else if low % 2 == 1 {
low++
}
for i := low; i <= 55; i += 2 {
fmt.Println(i)
idSearch(&start, i, 0, 0, low, make([]int, 1, 56))
}
}
//
// elevenid.go : 11 パズル (反復深化＋下限値枝刈り法)
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import (
"fmt"
"time"
)
// 隣接リスト
var adjacent[12][]int = [12][]int{
{1, 4}, // 0
{0, 2, 5}, // 1
{1, 3, 6}, // 2
{2, 7}, // 3
{0, 5, 8}, // 4
{1, 4, 6, 9}, // 5
{2, 5, 7, 10}, // 6
{3, 6, 11}, // 7
{4, 9}, // 8
{5, 8, 10}, // 9
{6, 9, 11}, // 10
{7, 10}, // 11
}
// 距離
var distance [12][12]int = [12][12]int {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 0 dummy
{0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5}, // 1
{1, 0, 1, 2, 2, 1, 2, 3, 3, 2, 3, 4}, // 2
{2, 1, 0, 1, 3, 2, 1, 2, 4, 3, 2, 3}, // 3
{3, 2, 1, 0, 4, 3, 2, 1, 5, 4, 3, 2}, // 4
{1, 2, 3, 4, 0, 1, 2, 3, 1, 2, 3, 4}, // 5
{2, 1, 2, 3, 1, 0, 1, 2, 2, 1, 2, 3}, // 6
{3, 2, 1, 2, 2, 1, 0, 1, 3, 2, 1, 2}, // 7
{4, 3, 2, 1, 3, 2, 1, 0, 4, 3, 2, 1}, // 8
{2, 3, 4, 5, 1, 2, 3, 4, 0, 1, 2, 3}, // 9
{3, 2, 3, 4, 2, 1, 2, 3, 1, 0, 1, 2}, // 10
{4, 3, 2, 3, 3, 2, 1, 2, 2, 1, 0, 1}, // 11
}
// 盤面の型
type Board [12]int
// 距離を求める
func getDistance(board *Board) int {
d := 0
for x, p := range board {
d += distance[p][x]
}
return d
}
// ゴール
var goal Board = Board{1,2,3,4,5,6,7,8,9,10,11,0}
var gSpace int = 11
// 手数の偶奇性
var parity [12]int = [12]int{
1, 0, 1, 0,
0, 1, 0, 1,
1, 0, 1, 0,
}
// 反復深化 + 下限値枝刈り法
func idSearch(board *Board, limit, move, space, lower int, movePiece []int) {
if move == limit {
if goal == *board {
fmt.Println(movePiece[1:])
panic("finish")
}
} else {
for _, x := range adjacent[space] {
p := board[x]
if movePiece[move] == p { continue }
board[space] = p
board[x] = 0
newLower := lower - distance[p][x] + distance[p][space]
if newLower + move <= limit {
idSearch(board, limit, move + 1, x, newLower, append(movePiece, p))
}
board[space] = 0
board[x] = p
}
}
}
func main() {
start := Board{0,3,2,1,8,7,6,5,4,11,10,9}
s := time.Now()
defer func(){
recover()
e := time.Now().Sub(s)
fmt.Println(e)
}()
sSpace := 0
low := getDistance(&start)
if parity[sSpace] != parity[gSpace] {
if low % 2 == 0 { low++ }
} else if low % 2 == 1 {
low++
}
for i := low; i <= 55; i += 2 {
fmt.Println(i)
idSearch(&start, i, 0, 0, low, make([]int, 1, 56))
}
}