今回は基本的な探索手法である幅優先探索 (breadth-first search) を使って、15 パズルで有名なスライドパズルを解いてみましょう。
参考文献『世界のパズル百科イラストパズルワンダーランド』によると、15 パズルはアメリカのサム・ロイドが 1870 年代に考案したパズルで、彼はパズルの神様と呼ばれるほど有名なパズル作家だそうです。
┌─┬─┬─┬─┐ │１│２│３│４│ ├─┼─┼─┼─┤ │５│６│７│８│ ├─┼─┼─┼─┤ │９│10│11│12│ ├─┼─┼─┼─┤ │13│14│15│ │ └─┴─┴─┴─┘ 図 : 15 パズル
15 パズルは上図に示すように、1 から 15 までの駒を並べるパズルです。駒の動かし方は、1 回に 1 個の駒を空いている隣の場所に滑らせる、というものです。駒を跳び越したり持ち上げたりすることはできません。
15 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、16! (約 2e13) 通りもあります。実際には、15 パズルの性質からその半分になるのですが、それでもパソコンで扱うにはあまりにも大きすぎる数です。そこで、盤面を一回り小さくした、1 から 9 までの数字を並べる「9 パズル」を考えることにします。
┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
│１│２│３│４│５│ │１│２│３│４│５│
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│６│７│８│９│ │ │６│７│９│８│ │
└─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
(１) 完成形 (２) 不可能な局面
図 : 9 パズル
15 パズルは 4 行 4 列の盤ですが、9 パズルは 2 行 5 列と盤を小さくしたパズルです。9 パズルの場合、駒の配置は空き場所がどこでもいいことにすると、10! = 3628800 通りあります。
15 パズルや 9 パズルの場合、参考文献『特集コンピュータパズルへの招待 スライディングブロック編』によると 『適当な 2 つの駒をつまみ上げて交換する動作を偶数回行った局面にしか移行できない』 とのことです。
上図 (2) は 8 と 9 を入れ替えただけの配置です。この場合、交換の回数が奇数回のため完成形に到達することができない、つまり解くことができないのです。
このような性質を「偶奇性 (パリティ)」といいます。詳しい説明は拙作のページ Puzzle DE Programming 「偶奇性 (パリティ) のお話」をお読みください。9 パズルの場合、完成形に到達する局面の総数は 10! / 2 = 1814400 個となります。
それでは、プログラムを作りましょう。下図に示すスタートから完成形 (ゴール) に到達するまでの最短手数を幅優先探索で求めます。
┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
│ │５│３│２│１│ │１│２│３│４│５│
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│９│４│８│７│６│ │６│７│９│８│ │
└─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
スタート ゴール
図 : 9 パズル
9 パズルの盤面は配列を使って表します。盤面の位置と配列の添字の対応は下図を見てください。
┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
│１│２│３│４│５│ │０│１│２│３│４│
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│６│７│８│９│ │ │５│６│７│８│９│
└─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
盤面:[1, 2, 3, 4, 5, 盤面と配列の対応
6, 7, 8, 9, 0]
図 : 9 パズルの盤面
隣接リストの定義は次のようになります。
リスト : 隣接リスト
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
}
次は局面を表す構造体を定義します。
リスト : 局面の定義
// 盤面の型
type Board [10]int8
// 局面
type State struct {
board Board
space int
prev *State
}
盤面を表す配列 [10]int8 に Board という別名を付けます。局面を表す構造体の名前は State としました。board は盤面を表す配列、space は空き場所の位置、prev は 1 手前の局面へのポインタを格納します。ゴールに到達したら、prev をたどって手順を表示します。
次は幅優先探索のプログラムを作ります。
リスト : 幅優先探索
func solver(start *Board, goal *Board) {
check := make(map[Board]bool)
q := newQueue()
q.enqueue(newState(start, position(0, start), nil))
check[*start] = true
for !q.isEmpty() {
st, _ := q.dequeue()
s := st.space
for _, n := range adjacent[s] {
work := st.board
work[s] = work[n]
work[n] = 0
_, ok := check[work]
if !ok {
newSt := newState(&work, n, st)
q.enqueue(newSt)
check[work] = true
if work == *goal {
printAnswer(newSt)
return
}
}
}
}
}
プログラムの骨格は「経路の探索」で説明した幅優先探索と同じです。幅優先探索はキューを使うと簡単にプログラムできます。今回使用するキューは「構造体 (2)」で作成したものとほぼ同じです。関数 solver の引数 start はスタートの盤面を表す配列です。スタートの局面を関数 newState で生成し、メソッド enqueue でキューに登録します。
変数 check は同一局面をチェックするためのマップを格納します。マップの型は map[Board]bool としました。Go 言語のマップは、演算子 ==, != で等値を判定できる型であればキーとして用いることができます。Go 言語の場合、スライス同士の等値は演算子 == で判定できませんが、同じ型の配列であれば、== で等値を判定することができます。
幅優先探索の場合、手数 を 1 つずつ増やしながら探索を行います。このため、n 手目の移動で作られた局面が n 手以前の局面で出現している場合、n 手より短い手数で到達する移動手順が必ず存在します。最短手順を求めるのであれば、この n 手の手順を探索する必要はありません。check をチェックして新しい局面だけキューに登録します。
次の for ループで、ゴール (goal) に到達するまで探索を繰り返します。キューが空になり for ループが終了する場合、start は goal に到達できない、つまり解くことができなかったことになります。キューから局面を取り出して変数 st に、空き場所の位置 st.space を変数 s にセットします。そして、駒を動かして新しい局面を生成します。盤面は元の局面 st.board をコピーして変数 work にセットします。動かせる駒の位置は空き場所の隣なので、adjacent[s] で求めることができます。あとは、work[s] に work[n] の駒をセットし、work[x] に空き場所を表すデータ 0 を書き込みます。
新しい盤面を作ったら、同一局面がないかマップ check でチェックします。同一局面がない場合は、newState で新しい局面を生成して変数 newSt にセットし、局面 newSt をキューに登録して、check[work] に true をセットします。このとき、空き場所の位置は x で、1 手前の局面は st になります。そして、work が goal に到達したら関数 printAnswer で手順を表示して処理を終了します。
あとのプログラムは簡単なので説明は割愛します。詳細はプログラムリスト１をお読みください。
それでは実行してみましょう。
[0 5 3 2 1 9 4 8 7 6] [5 0 3 2 1 9 4 8 7 6] [5 3 0 2 1 9 4 8 7 6] ・・・省略・・・ [1 2 3 0 4 6 7 8 9 5] [1 2 3 4 0 6 7 8 9 5] [1 2 3 4 5 6 7 8 9 0] 1.319829192s
55 手で解くことができました。生成した局面は全部で 1814400 通りで、実行時間は 1.32 秒 (Go 言語 ver 1.23.2, Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz) かかりました。9 パズルの場合、最長手数は 55 手で、下図に示す 2 通りの局面があります。スタートの局面はその一つです。
┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
│ │５│３│２│１│ │ │９│３│７│１│
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│９│４│８│７│６│ │５│４│８│２│６│
└─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
図 : 55 手で解ける局面
最長手数の局面は、幅優先探索を使って求めることができます。これはあとで試してみましょう。
ところで、今回の 9 パズルようにゴールの状態が明確な場合、スタートから探索するだけではなくゴールからも探索を行うことで、幅優先探索を高速化することができます。これを「双方向探索 (bi-directional search)」といいます。
その理由を説明するために、簡単なシミュレーションをしてみましょう。たとえば、1 手進むたびに 3 つの局面が生成され、5 手で解けると仮定します。すると、n 手目で生成される局面は 3 の n 乗個になるので、初期状態から単純に探索すると、生成される局面の総数は、3 + 9 + 27 + 81 + 243 = 363 個となります。
これに対し、初期状態と終了状態から同時に探索を始めた場合、お互い 3 手まで探索した時点で同じ局面に到達する、つまり、解を見つけることができます。この場合、生成される局面の総数は 3 手目までの局面数を 2 倍した 78 個となります。
生成される局面数はぐっと少なくなりますね。局面数が減少すると同一局面の探索処理に有利なだけではなく、「キューからデータを取り出して新しい局面を作る」という根本的な処理のループ回数を減らすことになるので、処理速度は大幅に向上するのです。
それではプログラムを作りましょう。単純に考えると、2 つの探索処理を交互に行うことになりますが、そうするとプログラムの大幅な修正が必要になります。ここは、探索方向を示すフラグを用意することで、一つのキューだけで処理することにしましょう。局面を表す構造体に方向を格納するフィールド変数 dir を追加します。
リスト : 局面の定義 (双方向からの探索)
const (
SIZE = 10
FORE = 0
BACK = 1
)
// 局面
type State struct {
board Board
space int
prev *State
dir int // FORE or BACK
}
スタートからの探索を FORE で、ゴールからの探索を BACK で表ます。双方向探索のプログラムは次のようになります。
リスト : 双方向探索
func solver(start *Board, goal *Board) {
check := make(map[Board]*State)
a := newState(start, position(0, start), nil, FORE)
b := newState(goal, position(0, goal), nil, BACK)
q := newQueue()
q.enqueue(a)
q.enqueue(b)
check[*start] = a
check[*goal] = b
for !q.isEmpty() {
st, _ := q.dequeue()
s := st.space
for _, n := range adjacent[s] {
work := st.board
work[s] = work[n]
work[n] = 0
st1, ok := check[work]
if !ok {
newSt := newState(&work, n, st, st.dir)
q.enqueue(newSt)
check[work] = newSt
} else if st.dir != st1.dir {
if st.dir == FORE {
printAnswerFore(st)
printAnswerBack(st1)
} else {
printAnswerFore(st1)
printAnswerBack(st)
}
fmt.Println(len(check))
return
}
}
}
}
スタートとゴールの局面を生成してキューにセットします。スタートの局面は FORE をセットし、ゴールの局面は BACK をセットします。最初に、スタートの状態から 1 手目の局面が生成され、次にゴールの状態から 1 手目の局面が生成されます。あとは、交互に探索が行われます。それから、同一局面を見つけたとき、その局面の方向 dir を比較する必要があるので、マップ check には局面 (*State) をセットするように変更します。
駒の移動と局面の生成処理は幅優先探索と同じです。同じ局面を見つけたとき、check から局面を取り出して変数 st1 にセットします。そして、st.dir と st1.dir を比較して探索方向が異なっていれば、双方向の探索で同一局面に到達したことがわかります。見つけた最短手順を関数 printAnswerFore と printAnswerBack で出力します。同じ探索方向であれば、キューへの追加は行いません。
あとのプログラムは簡単なので説明は割愛いたします。詳細はプログラムリスト２をお読みください。
さっそく実行してみると、生成された局面数は 387239 個で、実行時間は 0.25 秒でした。局面数は約 1 / 5 になり、実行時間も約 5.2 倍と高速になりました。
今度は最長手数の局面を求めてみましょう。最長手数の求め方ですが、1814400 通りの配置の最短手数がすべてわかれば、最長の手数となる配置を求めることができます。しかし、この方法では時間がとてもかかりそうです。そこで、完成形から始めていちばん長い手数の局面を生成することにします。
まず、完成形から駒を動かして 1 手で到達する局面をすべて作ります。次に、これらの局面から駒を動かして新しい局面を作れば、完成形から 2 手で到達する局面となります。このように、手数を 1 手ずつ伸ばしていき、新しい局面が生成できなくなった時点での手数が求める最長手数となります。この処理は幅優先探索を使えばぴったりです。
このプログラムの目的は、いちばん長い手数となる配置を求めることなので、その手順を表示することは行いません。このため、一つ前の局面を格納するフィールド変数 prev は削除します。そのかわり、その局面までの手数を格納するフィールド変数 move を用意します。一つ前の局面の手数を move から求め、それに 1 を足せば現在の局面の手数となります。
それではプログラムを作ります。次のリストを見てください。
リスト : 9 パズルの最長手数を求める
func solver(start *Board) {
check := make(map[Board]bool)
prevSt := make([]*State, 0)
prevSt = append(prevSt, newState(start, position(0, start), 0))
check[*start] = true
for {
nextSt := make([]*State, 0)
for _, st := range prevSt {
s := st.space
for _, n := range adjacent[s] {
work := st.board
work[s] = work[n]
work[n] = 0
_, ok := check[work]
if !ok {
nextSt = append(nextSt, newState(&work, n, st.move + 1))
check[work] = true
}
}
}
if len(nextSt) == 0 {
for _, st := range prevSt {
fmt.Println(st)
}
return
}
prevSt = nextSt
}
}
関数 solver にはゴールをチェックする処理がないことに注意してください。生成できる局面がなくなるまで処理を繰り返します。また、このプログラムはキューを使わずに、1 手前の局面をスライス prevSt に格納し、生成した新しい局面をスライス nextSt に格納します。prevSt から局面を取り出して、新しい局面を生成できたら nextSt に追加します。もしも、nextSt が空のスライスであれば、prevSt に格納されている局面が最長手数の局面となります。
あとのプログラムは簡単なので説明は割愛します。詳細はプログラムリスト３をお読みください。
それでは実行してみましょう。
&{[0 9 3 7 1 5 4 8 2 6] 0 55}
&{[0 5 3 2 1 9 4 8 7 6] 0 55}
1.189987936s
最長手数は 55 手で、その配置は全部で 2 通りになります。実行時間は 1.19 秒になりました。
今回はここまでです。次回は「反復深化」で 9 パズルを解いてみましょう。
//
// nine.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
}
// 盤面の型
type Board [10]int8
// 局面
type State struct {
board Board
space int
prev *State
}
// キュー
type Cell struct {
item *State
next *Cell
}
func newCell(item *State, next *Cell) *Cell {
return &Cell{item, next}
}
type Queue struct {
front *Cell
rear *Cell
}
func newQueue() *Queue {
return &Queue{}
}
func (q *Queue) enqueue(st *State) {
if q.rear == nil {
q.front = newCell(st, nil)
q.rear = q.front
} else {
q.rear.next = newCell(st, nil)
q.rear = q.rear.next
}
}
func (q *Queue) dequeue() (*State, bool) {
if q.front == nil {
return nil, false
}
st := q.front.item
q.front = q.front.next
if q.front == nil {
q.rear = nil
}
return st, true
}
func (q *Queue) isEmpty() bool {
return q.front == nil
}
// 局面の生成
func newState(board *Board, s int, st *State) *State {
p := new(State)
p.board = *board
p.space = s
p.prev = st
return p
}
// 手順の表示
func printAnswer(st *State) {
if st != nil {
printAnswer(st.prev)
fmt.Println(st.board)
}
}
// 位置を求める
func position(x int8, board *Board) int {
for i, n := range board {
if x == n { return i }
}
return -1
}
// 幅優先探索
func solver(start *Board, goal *Board) {
check := make(map[Board]bool)
q := newQueue()
q.enqueue(newState(start, position(0, start), nil))
check[*start] = true
for !q.isEmpty() {
st, _ := q.dequeue()
s := st.space
for _, n := range adjacent[s] {
work := st.board
work[s] = work[n]
work[n] = 0
// k := makeKey(&work)
_, ok := check[work]
if !ok {
newSt := newState(&work, n, st)
q.enqueue(newSt)
check[work] = true
if work == *goal {
printAnswer(newSt)
return
}
}
}
}
}
func main() {
start := Board{0,9,3,7,1,5,4,8,2,6}
goal := Board{1,2,3,4,5,6,7,8,9,0}
s := time.Now()
solver(&start, &goal)
e := time.Now().Sub(s)
fmt.Println(e)
}
//
// ninebi.go : 9 パズル (双方向探索)
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import (
"fmt"
"time"
)
const (
SIZE = 10
FORE = 0
BACK = 1
)
// 隣接リスト
var adjacent[SIZE][]int = [SIZE][]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
}
// 盤面の型
type Board [SIZE]int8
// 局面
type State struct {
board Board
space int
prev *State
dir int // FORE or BACK
}
// キュー
type Cell struct {
item *State
next *Cell
}
func newCell(item *State, next *Cell) *Cell {
return &Cell{item, next}
}
type Queue struct {
front *Cell
rear *Cell
}
func newQueue() *Queue {
return &Queue{}
}
func (q *Queue) enqueue(st *State) {
if q.rear == nil {
q.front = newCell(st, nil)
q.rear = q.front
} else {
q.rear.next = newCell(st, nil)
q.rear = q.rear.next
}
}
func (q *Queue) dequeue() (*State, bool) {
if q.front == nil {
return nil, false
}
st := q.front.item
q.front = q.front.next
if q.front == nil {
q.rear = nil
}
return st, true
}
func (q *Queue) isEmpty() bool {
return q.front == nil
}
// 局面の生成
func newState(board *Board, s int, st *State, d int) *State {
p := new(State)
p.board = *board
p.space = s
p.prev = st
p.dir = d
return p
}
// 手順の表示
func printAnswerFore(st *State) {
if st != nil {
printAnswerFore(st.prev)
fmt.Println(st.board)
}
}
func printAnswerBack(st *State) {
for ; st != nil; st = st.prev {
fmt.Println(st.board)
}
}
// 位置を求める
func position(x int8, board *Board) int {
for i, n := range board {
if x == n { return i }
}
return -1
}
// 幅優先探索
func solver(start *Board, goal *Board) {
check := make(map[Board]*State)
a := newState(start, position(0, start), nil, FORE)
b := newState(goal, position(0, goal), nil, BACK)
q := newQueue()
q.enqueue(a)
q.enqueue(b)
check[*start] = a
check[*goal] = b
for !q.isEmpty() {
st, _ := q.dequeue()
s := st.space
for _, n := range adjacent[s] {
work := st.board
work[s] = work[n]
work[n] = 0
// k := makeKey(&work)
st1, ok := check[work]
if !ok {
newSt := newState(&work, n, st, st.dir)
q.enqueue(newSt)
check[work] = newSt
} else if st.dir != st1.dir {
if st.dir == FORE {
printAnswerFore(st)
printAnswerBack(st1)
} else {
printAnswerFore(st1)
printAnswerBack(st)
}
fmt.Println(len(check))
return
}
}
}
}
func main() {
start := Board{0,5,3,2,1,9,4,8,7,6}
goal := Board{1,2,3,4,5,6,7,8,9,0}
s := time.Now()
solver(&start, &goal)
e := time.Now().Sub(s)
fmt.Println(e)
}
//
// ninemax.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
}
// 盤面の型
type Board [10]int8
// 局面
type State struct {
board Board
space, move int
}
// 局面の生成
func newState(board *Board, s, m int) *State {
p := new(State)
p.board = *board
p.space = s
p.move = m
return p
}
// 位置を求める
func position(x int8, board *Board) int {
for i, n := range board {
if x == n { return i }
}
return -1
}
// 幅優先探索
func solver(start *Board) {
check := make(map[Board]bool)
prevSt := make([]*State, 0)
prevSt = append(prevSt, newState(start, position(0, start), 0))
check[*start] = true
for {
nextSt := make([]*State, 0)
for _, st := range prevSt {
s := st.space
for _, n := range adjacent[s] {
work := st.board
work[s] = work[n]
work[n] = 0
_, ok := check[work]
if !ok {
nextSt = append(nextSt, newState(&work, n, st.move + 1))
check[work] = true
}
}
}
if len(nextSt) == 0 {
for _, st := range prevSt {
fmt.Println(st)
}
return
}
prevSt = nextSt
}
}
func main() {
start := Board{1,2,3,4,5,6,7,8,9,0}
s := time.Now()
solver(&start)
e := time.Now().Sub(s)
fmt.Println(e)
}