M.Hiroi's Home Page

Puzzle DE Go!

入れ替えパズルと幅優先探索


Copyright (C) 2014-2021 Makoto Hiroi
All rights reserved.

はじめに

今回は「幅優先探索」を使って「入れ替えパズル」の最短手数を求めてみましょう。

●おしどりの遊び

おしどりの遊びは囲碁の白石と黒石を交互に並べ、それをペアで動かしながら黒石と白石とに分けるというパズルです。 

┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│●│○│●│○│●│○│●│○│  │  │  初期状態  
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘

┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│  │  │○│○│○│○│●│●│●│●│  ゴール
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘

        図 : おしどりの遊び

石はペアで空いている場所に動かすことができます。このときペアの順番を変えることはできません。たとえば、先頭にある黒白を動かすときに、白黒というように石の順番を逆にすることは許されません。この条件で並べ替えるまでの最短手順を求めてください。

●嫉妬深い夫の問題

「嫉妬深い夫の問題」は「川渡りの問題」と呼ばれる古典的なパズルの一種です。このパズルにはたくさんのバリエーションがありますが、その中で 「農夫と山羊と狼とキャベツの問題」 や「宣教師と人食い人」という危険な名前のパズルが有名です。それでは問題です。

三組の夫婦が川を渡ることになりました。ボートには二人しか乗ることができません。どの夫も嫉妬深く、彼自身が一緒にいない限り、ボートでも岸でも妻が他の男といることを許しません。なお、六人ともボートをこぐことができます。この条件で、三組の夫婦が川を渡る最短手順を求めてください。

●蛙跳びゲーム

蛙跳びゲームは簡単そうに見えて、おしどりの遊びよりも難しいパズルです。 

┌─┬─┬─┬─┬─┬─┬─┐
│●│●│●│  │○│○│○│ スタート  
└─┴─┴─┴─┴─┴─┴─┘

┌─┬─┬─┬─┬─┬─┬─┐
│○│○│○│  │●│●│●│ ゴール
└─┴─┴─┴─┴─┴─┴─┘

        図 : 蛙跳びゲーム

上図のように、蛙跳びゲームは黒石と白石を入れ替えることができれば成功です。スタートからゴールまでの最短手順を求めてください。

石を動かす規則は次のとおりです。

石の跳び越しは次の図を参考にしてください。 

   ┌───┐                ┌───┐
   ↓      │                │      ↓
 ┬─┬─┬─┬─┬    ┬─┬─┬─┬─┬ 
 │  │●│○│  │    │  │●│○│  │
 ┴─┴─┴─┴─┴    ┴─┴─┴─┴─┴
    白石の移動              黒石の移動

            図 : 石の跳び越し

●おしどりの遊びの解答

最初に定数とデータ型を定義します。 

リスト : 定数とデータ型の定義

// 定数
const (
    S = iota
    B
    W
    SIZE = 10
)

// 盤面
type Board [SIZE]int

黒石、白石、空き場所をそれぞれ const で B, W, S と定義します。盤面は配列で表します。大きさは SIZE で、型名は Board としました。

次は局面を表す構造体を定義します。 

リスト : 局面の定義

type State struct {
    board Board
    space int
    prev  *State
}

// 局面の生成
func newState(board *Board, space int, state *State) *State {
    st := new(State)
    st.board = *board
    st.space = space
    st.prev  = state
    return st
}

型名は State としました。board が盤面で、space が空き場所の位置、prev が 1 手前の局面です。prev をたどっていくことで、移動手順を再現することができます。関数 newState は局面を生成します。引数 board は盤面へのポインタ、space が空き場所の位置、state が 1 手前の局面です。組み込み関数 new で State のメモリを確保し、フィールド変数に値をセットします。フィールド変数 board は配列なので、st.board = *board とすることで配列の要素をコピーすることができます。

ところで、最短手順を求める場合、すべての手順を記憶しておく必要はありません。n 手目の移動で作られた局面が、n 手目以前の局面で出現しているのであれば、n 手より短い手数で到達する移動手順があるはずです。したがって、この n 手の手順を記憶しておく必要はなく、キューに追加するのは新しい局面だけになります。

●石の移動

次は石を移動する関数 moveStone を作ります。 

リスト : 石の移動

func moveStone(state *State, dest int) *State {
    st := newState(&state.board, dest, state)
    s := state.space
    st.board[s] = st.board[dest]
    st.board[s + 1] = st.board[dest + 1]
    st.board[dest] = S
    st.board[dest + 1] = S
    return st
}

引数 state は元の局面、dest は移動する石の位置を表します。最初に newState で新しい局面を生成します。次に、空き場所の位置を変数 s にセットし、dest の石を s に、dest + 1 の石を s + 1 に移動します。そして、dest と dest + 1 に S を書き込みます。これで石を移動した新しい局面を生成することができます。

●同一局面のチェック

次は同一局面のチェックを行う関数 checkSameState を作ります。今回のプログラムはスライスを使ってキューを表すことにします。局面はスライスの末尾に追加していくので、同一局面のチェックはスライスを線形探索すればいいでしょう。プログラムは次のようになります。 

リスト : 同じ状態をチェックする

func checkSameState(xs []*State, state *State) bool {
    for _, x := range xs {
        if x.board == state.board {
            return true
        }
    }
    return false
}

引数 xs が局面を格納しているスライス (キュー) です。for ループで局面 x を取り出して、x.board と state.board を比較します。配列の場合、同じ型であれば演算子 (==, !=) で等値を判定することができます。同じ盤面が見つかれば true を返し、見つからなければ false を返します。

●移動手順の表示

次は移動手順を表示する printAnswer を作ります。 

リスト : 移動手順の表示

func printAnswer(state *State) {
    if state != nil {
        printAnswer(state.prev)
        fmt.Println(state.board)
    }
}

state.prev を順番にたどって出力すると、手順は逆順に表示されてしまいます。そこで、再帰呼び出しを使って最初の状態に戻り、そこから局面を順番に出力させます。

●おしどりの遊びを解く

最後に、幅優先探索で解を求める関数 solver を作ります。 

リスト : おしどりの遊びの解法

// 幅優先探索
func solver() {
    start := Board{B, W, B, W, B, W, B, W, S, S}
    goal  := Board{S, S, W, W, W, W, B, B, B, B}
    que   := make([]*State, 0)
    que = append(que, newState(&start, 8, nil))
    for front := 0; front < len(que); front++ {
        state := que[front]
        for i := 0; i < SIZE - 1; i++ {
            if state.board[i] != S && state.board[i + 1] != S {
                st := moveStone(state, i)
                if st.board == goal {
                    printAnswer(st)
                    return
                } else if !checkSameState(que, st) {
                    que = append(que, st)
                }
            }
        }
    }
}

start, goal はスタートとゴールを表す配列です。que は *State を格納するスライスで、キューとして使います。最初に newState でstart を格納した局面を生成して、append でキューに追加します。あとは、キューにデータがある間、幅優先探索を続行します。

最初の for ループの中で、front の位置にある局面を取り出して変数 state にセットします。次の for ループで石を移動します。石は 2 ついっしょに移動させるので、state.board の i 番目と i + 1 番目の要素が空き場所でないことを確認します。それから、moveStone で石を動かして新しい局面を生成し、それを変数 st にセットします。st.board が goal と等しければ、解を見つけることができました。printAnswer で手順を表示して、return で探索を終了します。そうでなければ、checkSameState で同一局面がないことを確認して、append でキューに st を追加します。

●実行結果

実行結果は次のようになります。 

$ go run oshidori.go
[1 2 1 2 1 2 1 2 0 0]
[1 0 0 2 1 2 1 2 2 1]
[1 1 2 2 0 0 1 2 2 1]
[1 1 2 2 2 2 1 0 0 1]
[0 0 2 2 2 2 1 1 1 1]

4 手で解くことができました。生成した局面は 125 通りになりました。なお、ゴールを次のように変更すると最短手順は 1 手増えます。 

goal := Board{B, B, B, W, W, W, S, S}

興味のある方はいろいろ試してみてください。

●プログラムリスト

//
// oshidori.go : おしどりの遊び
//
//               Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import "fmt"

const (
    S = iota
    B
    W
    SIZE = 10
)

// 盤面の型
type Board [SIZE]int

// 局面
type State struct {
    board Board
    space int
    prev  *State
}

// 局面の生成
func newState(board *Board, space int, state *State) *State {
    st := new(State)
    st.board = *board
    st.space = space
    st.prev  = state
    return st
}

// 石を動かす
func moveStone(state *State, dest int) *State {
    st := newState(&state.board, dest, state)
    s := state.space
    st.board[s] = st.board[dest]
    st.board[s + 1] = st.board[dest + 1]
    st.board[dest] = S
    st.board[dest + 1] = S
    return st
}

// 同じ局面があるか
func checkSameState(xs []*State, state *State) bool {
    for _, x := range xs {
        if x.board == state.board {
            return true
        }
    }
    return false
}

// 手順の表示
func printAnswer(state *State) {
    if state != nil {
        printAnswer(state.prev)
        fmt.Println(state.board)
    }
}

// 幅優先探索
func solver() {
    start := Board{B, W, B, W, B, W, B, W, S, S}
    goal  := Board{S, S, W, W, W, W, B, B, B, B}
    que   := make([]*State, 0)
    que = append(que, newState(&start, 8, nil))
    for front := 0; front < len(que); front++ {
        state := que[front]
        for i := 0; i < SIZE - 1; i++ {
            if state.board[i] != S && state.board[i + 1] != S {
                st := moveStone(state, i)
                if st.board == goal {
                    printAnswer(st)
                    return
                } else if !checkSameState(que, st) {
                    que = append(que, st)
                }
            }
        }
    }
}

func main() {
    solver()
}

●嫉妬深い夫の問題の解答

最初に大域変数を定義します。次のリストを見てください。 

リスト：定数と大域変数の定義

const (
    Boat = 0x01
    Ha   = 0x02    // Hx 夫
    Wa   = 0x04    // Wx 妻
    Hb   = 0x08
    Wb   = 0x10
    Hc   = 0x20
    Wc   = 0x40
)

// ボートに乗る組み合わせ
var boatTable = []int{
    Boat | Ha,
    Boat | Wa,
    Boat | Hb,
    Boat | Wb,
    Boat | Hc,
    Boat | Wc,
    Boat | Ha | Wa,
    Boat | Hb | Wb,
    Boat | Hc | Wc,
    Boat | Ha | Hb,
    Boat | Ha | Hc,
    Boat | Hb | Hc,
    Boat | Wa | Wb,
    Boat | Wa | Wc,
    Boat | Wb | Wc,
}

今回のプログラムは三組の夫婦とボートをビットで定義して、左右の岸を整数値で表すことにします。ボートに乗る組み合わせは、二人（三組の夫婦、男性二人、女性二人）で乗る場合と一人で乗る場合があるので、合計で 15 通りになります。これをスライス boatTable に定義します。

次は局面を表す構造体を定義します。 

リスト : 局面の定義

type State struct {
    left, right int
    prev *State
}

// 局面の生成
func newState(left, right int, state *State) *State {
    st := new(State)
    st.left  = left
    st.right = right
    st.prev  = state
    return st
}

型名は State としました。left が左岸の状態、right が右岸の状態を表します。prev は 1 手前の局面です。関数 newState は新しい局面を生成します。引数 left, right が左右の岸、state が 1 手前の局面です。

●安全確認

次は、局面が安全な状態かチェックする関数 safe を作ります。 

リスト：安全な状態かチェックする

// 岸は安全か
func safeSide(side int) bool {
    wa, wb, wc := true, true, true
    if side & Wa != 0 {
        wa = side & Ha != 0 || side & (Hb | Hc) == 0
    }
    if side & Wb != 0 {
        wb = side & Hb != 0 || side & (Ha | Hc) == 0
    }
    if side & Wc != 0 {
        wc = side & Hc != 0 || side & (Ha | Hb) == 0
    }
    return wa && wb && wc
}

// 安全確認
func safe(state *State) bool {
    return safeSide(state.left) && safeSide(state.right)
}

実際の処理は関数 safeSide で行います。引数 side は岸の状態を表します。最初に、変数 wa, wb, wc を true で初期化します。これらの変数は Wa, Wb, Wc が安全であれば true に、そうでなければ false に書き換えます。side に Wa がいる場合、夫 Ha がいる (side & Ha != 0) か、もしくは他の男性 Hb と Hc がいない (side & (Hb | Hc) == 0) 場合は安全です。この結果を wa にセットします。Wb, Wc も同様にチェックして、結果を wb, wc にセットします。あとは、wa && wb && wc を返すだけです。

●嫉妬深い夫の問題を解く

最後に、幅優先探索でパズルを解く関数 solver を作ります。 

リスト：幅優先探索

func solver() {
    all := Boat | Ha | Wa | Hb | Wb | Hc | Wc
    que := make([]*State, 0)
    que = append(que, newState(all, 0, nil))
    for front := 0; front < len(que); front++ {
        state := que[front]
        for _, person := range boatTable {
            if !check(state, person) { continue }
            st := newState(state.left, state.right, state)
            if isLeft(st) {
                st.left  &= ^person
                st.right |= person
            } else {
                st.right &= ^person
                st.left  |= person
            }
            if st.right == all {
                printAnswer(st)
                return
            } else if safe(st) && !checkSameState(que, st) {
                que = append(que, st)
            }
        }
    }
}

まず最初にキューを生成して変数 que にセットします。そして、最初の状態 (左岸に全員がいる状態) を newState で生成して append でキューに追加します。あとは、キューにデータがある間、幅優先探索を続行します。

最初の for ループの中で、キューから局面を取り出して変数 state にチェックします。次の for ループで、boatTable からボートに乗り込む人を順番に取り出して、変数 person にセットします。関数 check は person がボートのある岸にいるかチェックします。いない場合はボートに乗ることができないので、continue であとの処理をスキップします。

person がボートに乗ることができる場合、newState で新しい局面を生成して変数 st にセットします。関数 isLeft はボートが左岸にある場合は true を返します。左岸から右岸へ移動する場合、st.left から person を取り除きます。Go 言語の場合、整数の否定 (ビットの反転) は演算子 ^ で行います。Ｃ言語のように演算子 ~ ではないので注意してください。そして、person を st.right に加えます。ボートが右岸にある場合は逆になります。

そして、st.right が all と等しい場合は、全員が右岸へ移動したので、printAnswer で手順を表示します。そうでなければ、新しい局面 st が安全か safe で確認し、同一局面がなければキューに追加します。

あとは特に難しいところはないでしょう。詳細はプログラムリスト２をお読みくださいませ。

●実行結果

それでは実行結果を示します。最短手数は 11 手で、次のようになります。 

$ go run husband.go
[Boat Ha Wa Hb Wb Hc Wc] []
[Hb Wb Hc Wc] [Boat Ha Wa]
[Boat Ha Hb Wb Hc Wc] [Wa]
[Ha Hb Hc] [Boat Wa Wb Wc]
[Boat Ha Wa Hb Hc] [Wb Wc]
[Ha Wa] [Boat Hb Wb Hc Wc]
[Boat Ha Wa Hb Wb] [Hc Wc]
[Wa Wb] [Boat Ha Hb Hc Wc]
[Boat Wa Wb Wc] [Ha Hb Hc]
[Wc] [Boat Ha Wa Hb Wb Hc]
[Boat Wa Wc] [Ha Hb Wb Hc]
[] [Boat Ha Wa Hb Wb Hc Wc]

ところで、夫婦が四組に増えると、二人乗りのボートで川を渡ることはできません。三人乗りのボートにするか、川の中に小島がひとつあれば二人乗りのボートでも渡ることができます。興味のある方は拙作のページ uzzle DE Programming 「嫉妬深い夫の問題 (四組の場合)」をお読みください。

●プログラムリスト２

//
// husband.go : 嫉妬深い夫の問題
//
//              Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import "fmt"

// 定数
const (
    Boat = 0x01
    Ha   = 0x02
    Wa   = 0x04
    Hb   = 0x08
    Wb   = 0x10
    Hc   = 0x20
    Wc   = 0x40
)

// ボートに乗る組み合わせ
var boatTable = []int{
    Boat | Ha,
    Boat | Wa,
    Boat | Hb,
    Boat | Wb,
    Boat | Hc,
    Boat | Wc,
    Boat | Ha | Wa,
    Boat | Hb | Wb,
    Boat | Hc | Wc,
    Boat | Ha | Hb,
    Boat | Ha | Hc,
    Boat | Hb | Hc,
    Boat | Wa | Wb,
    Boat | Wa | Wc,
    Boat | Wb | Wc,
}

// 局面
type State struct {
    left, right int
    prev *State
}

// 局面の生成
func newState(left, right int, state *State) *State {
    st := new(State)
    st.left  = left
    st.right = right
    st.prev  = state
    return st
}

// 岸は安全か
func safeSide(side int) bool {
    wa, wb, wc := true, true, true
    if side & Wa != 0 {
        wa = side & Ha != 0 || side & (Hb | Hc) == 0
    }
    if side & Wb != 0 {
        wb = side & Hb != 0 || side & (Ha | Hc) == 0
    }
    if side & Wc != 0 {
        wc = side & Hc != 0 || side & (Ha | Hb) == 0
    }
    return wa && wb && wc
}

// 安全確認
func safe(state *State) bool {
    return safeSide(state.left) && safeSide(state.right)
}

// 同一局面のチェック
func checkSameState(xs []*State, state *State) bool {
    for _, x := range xs {
        if x.left == state.left && x.right == state.right {
            return true
        }
    }
    return false
}

// 騎士にいる人の名前を求める
func toName(side int) []string {
    xs := make([]string, 0)
    if side & Boat != 0 { xs = append(xs, "Boat") }
    if side & Ha != 0 { xs = append(xs, "Ha") }
    if side & Wa != 0 { xs = append(xs, "Wa") }
    if side & Hb != 0 { xs = append(xs, "Hb") }
    if side & Wb != 0 { xs = append(xs, "Wb") }
    if side & Hc != 0 { xs = append(xs, "Hc") }
    if side & Wc != 0 { xs = append(xs, "Wc") }
    return xs
}

// 移動手順の表示
func printAnswer(state *State) {
    if state != nil {
        printAnswer(state.prev)
        fmt.Println(toName(state.left), toName(state.right))
    }
}

// ボートは左岸にあるか
func isLeft(state *State) bool {
    return state.left & Boat != 0
}

// ボートに乗れるか
func check(state *State, person int) bool {
    if isLeft(state) {
        return state.left & person == person
    }
    return state.right & person == person
}

// 幅優先探索
func solver() {
    all := Boat | Ha | Wa | Hb | Wb | Hc | Wc
    que := make([]*State, 0)
    que = append(que, newState(all, 0, nil))
    for front := 0; front < len(que); front++ {
        state := que[front]
        for _, person := range boatTable {
            if !check(state, person) { continue }
            st := newState(state.left, state.right, state)
            if isLeft(st) {
                st.left  &= ^person
                st.right |= person
            } else {
                st.right &= ^person
                st.left  |= person
            }
            if st.right == all {
                printAnswer(st)
                return
            } else if safe(st) && !checkSameState(que, st) {
                que = append(que, st)
            }
        }
    }
}

func main() {
    solver()
}

●蛙跳びゲームの解答

最初に必要となるデータ型を定義します。 

リスト : 定数とデータ型の定義

// 定数
const (
    S = iota
    B
    W
    SIZE = 7
)

// 盤面
type Board [SIZE]int

// 局面
type State struct {
    board Board
    space int
    prev  *State
}

// 局面の生成
func newState(board *Board, space int, state *State) *State {
    st := new(State)
    st.board = *board
    st.space = space
    st.prev  = state
    return st
}

盤面は型 Board で表します。局面を表す構造体は State で、board が盤面を、space が空き場所の位置、prev が 1 手前の局面を表します。局面の生成は関数 newState で行います。引数 board は盤面へのポインタ、space が空き場所の位置、state が 1 手前の局面です。

●石の移動

次は石を移動する関数を作ります。 

リスト : 石の移動

// 白石の移動１
func moveW1(state *State) *State {
    var p *State
    s := state.space
    if s + 1 < SIZE && state.board[s + 1] == W {
        p = newState(&state.board, s, state)
        p.board[s] = W
        p.board[s + 1] = S
        p.space = s + 1
    }
    return p
}

// 白石の移動２
func moveW2(state *State) *State {
    var p *State
    s := state.space
    if s + 2 < SIZE && state.board[s + 2] == W && state.board[s + 1] == B {
        p = newState(&state.board, s, state)
        p.board[s] = W
        p.board[s + 2] = S
        p.space = s + 2
    }
    return p
}

関数 moveW1 は白石を左へ 1 つ動かします。最初に、局面を表す変数 p を宣言します。p は nil に初期化されることに注意してください。次に、空き場所の位置を変数 s にセットします。そして、state.board[s + 1] が白石ならば、その石を空き場所へ動かします。newState で新しい局面を生成して変数 p にセットします。そしで、p.board と p.space の値を書き換えます。最後に変数 p を返します。

関数 moveW2 は白石を左へ 2 つ動かします。空き場所の位置を s とすると、S + 2 の位置に白石があり、s + 1 の位置に黒石があれば、白石を動かすことができます。あとの処理は moveW1 と同じです。

同様に、黒石を動かす関数 moveB1 と moveB2 を定義して、それらの関数をスライス moveTbl にセットします。 

リスト : 移動関数表

var moveTbl = []func(*State) *State {
    moveW1, moveW2, moveB1, moveB2,
}

moveTbl から関数を取り出して局面に適用すれば、石を動かして新しい局面を生成することができます。

●蛙跳びゲームを解く

最後に蛙跳びゲームを解く関数 solver を作ります。 

リスト：幅優先探索

func solver() {
    start := Board{B, B, B, S, W, W, W}
    goal  := Board{W, W, W, S, B, B, B}
    que   := make([]*State, 0)
    que = append(que, newState(&start, 3, nil))
    for front := 0; front < len(que); front++ {
        state := que[front]
        for _, move := range moveTbl {
            st := move(state)
            if st != nil {
                if st.board == goal {
                    printAnswer(st)
                    return
                } else if !checkSameState(que, st) {
                    que = append(que, st)
                }
            }
        }
    }
}

キューを生成する処理と初期化は今までと同じです。for ループの中で、キューから局面を取り出して変数 state にセットします。そして、moveTbl から移動関数ををとりだして state に適用し、生成した新しい局面を変数 st にセットします。st が nil でなければ、石を動かすことができました。st.board が goal と等しい場合、解を見つけたので printAnswer で手順を表示します。そうでなければ、関数 checkSameState で同一局面があるかチェックし、新しい局面であれば st をキューに追加します。

あとは特に難しいところないでしょう。説明は割愛するので、詳細はプログラムリスト３をお読みください。

●実行結果

それでは実行結果を示します。移動する石を太字で表しています。 

$ go run kaeru.go
[1 1 1 0 2 2 2]
[1 1 1 2 0 2 2]
[1 1 0 2 1 2 2]
[1 0 1 2 1 2 2]
[1 2 1 0 1 2 2]
[1 2 1 2 1 0 2]
[1 2 1 2 1 2 0]
[1 2 1 2 0 2 1]
[1 2 0 2 1 2 1]
[0 2 1 2 1 2 1]
[2 0 1 2 1 2 1]
[2 2 1 0 1 2 1]
[2 2 1 2 1 0 1]
[2 2 1 2 0 1 1]
[2 2 0 2 1 1 1]
[2 2 2 0 1 1 1]

15 手で解くことができました。この手順は白石から動かしていますが、黒石から動かしても解くことができます。ところで、今回はアルゴリズムに幅優先探索を使いましたが、黒石と白石は後戻りできないことから、バックトラックでも簡単に最短手順を求めることができます。興味のある方は、実際に試してみてください。

●プログラムリスト３

//
// kaeru.go : 蛙跳びゲーム
//
//            Copyright (C) 2014-2021 Makoto Hiroi
//
package main
import "fmt"

const (
    S = iota
    B
    W
    SIZE = 7
)

// 盤面
type Board [SIZE]int

// 局面
type State struct {
    board Board
    space int
    prev  *State
}

// 局面の生成
func newState(board *Board, space int, state *State) *State {
    st := new(State)
    st.board = *board
    st.space = space
    st.prev  = state
    return st
}

// 白石の移動１
func moveW1(state *State) *State {
    var p *State
    s := state.space
    if s + 1 < SIZE && state.board[s + 1] == W {
        p = newState(&state.board, s, state)
        p.board[s] = W
        p.board[s + 1] = S
        p.space = s + 1
    }
    return p
}

// 白石の移動２
func moveW2(state *State) *State {
    var p *State
    s := state.space
    if s + 2 < SIZE && state.board[s + 2] == W && state.board[s + 1] == B {
        p = newState(&state.board, s, state)
        p.board[s] = W
        p.board[s + 2] = S
        p.space = s + 2
    }
    return p
}

// 黒石の移動１
func moveB1(state *State) *State {
    var p *State
    s := state.space
    if s - 1 >= 0 && state.board[s - 1] == B {
        p = newState(&state.board, s, state)
        p.board[s] = B
        p.board[s - 1] = S
        p.space = s - 1
    }
    return p
}

// 黒石の移動２
func moveB2(state *State) *State {
    var p *State
    s := state.space
    if s - 2 >= 0 && state.board[s - 2] == B && state.board[s - 1] == W {
        p = newState(&state.board, s, state)
        p.board[s] = B
        p.board[s - 2] = S
        p.space = s - 2
    }
    return p
}

// 移動関数表
var moveTbl = []func(*State) *State {
    moveW1, moveW2, moveB1, moveB2,
}

// 手順の表示
func printAnswer(state *State) {
    if state != nil {
        printAnswer(state.prev)
        fmt.Println(state.board)
    }
}

// 同一局面のチェック
func checkSameState(xs []*State, state *State) bool {
    for _, x := range xs {
        if x.board == state.board {
            return true
        }
    }
    return false
}

// 幅優先探索
func solver() {
    start := Board{B, B, B, S, W, W, W}
    goal  := Board{W, W, W, S, B, B, B}
    que   := make([]*State, 0)
    que = append(que, newState(&start, 3, nil))
    for front := 0; front < len(que); front++ {
        state := que[front]
        for _, move := range moveTbl {
            st := move(state)
            if st != nil {
                if st.board == goal {
                    printAnswer(st)
                    return
                } else if !checkSameState(que, st) {
                    que = append(que, st)
                }
            }
        }
    }
}

func main() {
    solver()
}
初版 2014 年 3 月 16 日
改訂 2021 年 12 月 11 日