今回は「幅優先探索」を使って「入れ替え (並べ替え) パズル」の最短手数を求めてみましょう。
おしどりの遊びは囲碁の白石と黒石を交互に並べ、それをペアで動かしながら黒石と白石とに分けるというパズルです。
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│●│○│●│○│●│○│●│○│ │ │ 初期状態
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│ │ │○│○│○│○│●│●│●│●│ ゴール
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
図 : おしどりの遊び
石はペアで空いている場所に動かすことができます。このときペアの順番を変えることはできません。たとえば、先頭にある黒白を動かすときに、白黒というように石の順番を逆にすることは許されません。この条件で並べ替えるまでの最短手順を求めてください。
蛙跳びゲームは簡単そうに見えて、おしどりの遊びよりも難しいパズルです。
┌─┬─┬─┬─┬─┬─┬─┐
│●│●│●│ │○│○│○│ スタート
└─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┐
│○│○│○│ │●│●│●│ ゴール
└─┴─┴─┴─┴─┴─┴─┘
図 : 蛙跳びゲーム
上図のように、蛙跳びゲームは黒石と白石を入れ替えることができれば成功です。スタートからゴールまでの最短手順を求めてください。
石を動かす規則は次のとおりです。
石の跳び越しは次の図を参考にしてください。
┌───┐ ┌───┐
↓ │ │ ↓
┬─┬─┬─┬─┬ ┬─┬─┬─┬─┬
│ │●│○│ │ │ │●│○│ │
┴─┴─┴─┴─┴ ┴─┴─┴─┴─┴
白石の移動 黒石の移動
図 : 石の跳び越し
「嫉妬深い夫の問題」は「川渡りの問題」と呼ばれる古典的なパズルの一種です。このパズルにはたくさんのバリエーションがありますが、その中で 「農夫と山羊と狼とキャベツの問題」 や「宣教師と原住民」という名前のパズルが有名です。それでは問題です。
三組の夫婦が川を渡ることになりました。ボートには二人しか乗ることができません。どの夫も嫉妬深く、彼自身が一緒にいない限り、ボートでも岸でも妻が他の男といることを許しません。なお、六人ともボートをこぐことができます。この条件で、三組の夫婦が川を渡る最短手順を求めてください。
┌─┬─┬─┬─┬─┬─┬─┐
│１│２│３│４│５│６│ │スタート
└─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┐
│ │６│５│４│３│２│１│ゴール
└─┴─┴─┴─┴─┴─┴─┘
図 : 数字の並べ替え
上図のスタートのように並んでいる数字を、ゴールのように逆順に並べ替える最短手順を求めてください。数字を動かす規則は次のとおりです。
数字をひとつ跳び越すことができるのは「蛙跳びゲーム」と似ていますね。スタートの状態では、6 は隣が空き場所なので移動することができます。また、5 は隣に 6 がありますが、それを跳び越して空き場所へ移動することができます。ほかの数字は空き場所へ移動できません。
なお、このパズルは、高木茂男氏の著書「パズル遊びへの招待」(PHP研究所 1994) のオンライン版にある「おしどりの遊びと入れ替え問題」を参考にさせていただきました。関係各位に深く感謝いたします。
騎士（ナイト）はチェスの駒のひとつで、下図に示すように将棋の桂馬の動きを前後左右にとることができます。今回は黒騎士 ● と白騎士 ○ の位置を交換するパズルです。それでは問題です。
下図の START から GOAL までの最短手順を求めてください。
┌─┬─┬─┬─┬─┐
│ │◎│ │◎│ │
├─┼─┼─┼─┼─┤ ┌─┬─┬─┐ ┌─┬─┬─┐
│◎│ │ │ │◎│ │●│●│●│ │○│○│○│
├─┼─┼─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤
│ │ │Ｋ│ │ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┤ => ├─┼─┼─┤
│◎│ │ │ │◎│ │ │ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤
│ │◎│ │◎│ │ │○│○│○│ │●│●│●│
└─┴─┴─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘
◎ : ナイト (K) が動ける位置 ＳＴＡＲＴ ＧＯＡＬ
図 : 騎士の交換
おしどりの遊びは、空き場所の位置が 9 通りで、黒石の配置が 8Ｃ4 = 70 通りあるので、局面数は最大でも 630 通りしかありません。幅優先探索の場合、堂々巡りの手順を検出するため、同一局面のチェックが必要になりますが、今回は単純な線形探索で十分でしょう。
まず最初に、定数とデータ型を定義します。
リスト : 定数とデータ型の定義
# 定数
const space = 0
const black = 1
const white = 2
# 盤面
const Board = Vector{Int}
# 局面
struct State
board::Board
pos::Int
prev
end
# 手順の表示
function printanswer(state, printer=println)
if state.prev !== nothing
printanswer(state.prev, printer)
end
printer(state.board)
end
黒石、白石、空き場所をそれぞれ const で space, black, white と定義します。盤面は 1 次元配列 (Vector{Int}) で表します。今回のプログラムでは別名 Board を付けています。局面を表す型名は State としました。board が盤面で、pos が空き場所の位置、prev が 1 手前の局面です。prev をたどっていくことで、移動手順を再現することができます。これを関数 printanswer() で行います。
ところで、最短手順を求める場合、すべての手順を記憶しておく必要はありません。n 手目の移動で作られた局面が、n 手目以前の局面で出現しているのであれば、n 手より短い手数で到達する移動手順があるはずです。したがって、この n 手の手順を記憶しておく必要はなく、キューに追加するのは新しい局面だけになります。
次は石を移動する関数 movestone() を作ります。
リスト : 石の移動
function movestone(state::State, dest::Int)
newboard = copy(state.board)
s = state.pos
newboard[s] = newboard[dest]
newboard[s + 1] = newboard[dest + 1]
newboard[dest] = space
newboard[dest + 1] = space
State(newboard, dest, state)
end
引数 state は元の局面、dest は移動する石の位置を表します。最初に copy() で盤面をコピーします。次に、空き場所の位置を変数 s にセットし、dest の石を s に、dest + 1 の石を s + 1 に移動します。そして、dest と dest + 1 に space を書き込みます。あとは State() で新しい局面を生成して返します。
最後に、幅優先探索で解を求める関数 oshidori() を作ります。
リスト : おしどりの遊びの解法
function oshidori()
start::Board = [black, white, black, white, black, white, black, white, space, space]
goal::Board = [space, space, white, white, white, white, black, black, black, black]
state1 = State(start, 9, nothing)
que = State[state1]
chk = Board[start]
while !isempty(que)
state = popfirst!(que)
for i = 1 : length(start) - 1
if state.board[i] != space && state.board[i + 1] != space
newstate = movestone(state, i)
if newstate.board == goal
printanswer(newstate)
return
elseif findfirst(isequal(newstate.board), chk) === nothing
push!(que, newstate)
push!(chk, newstate.board)
end
end
end
end
end
start と goal はスタートとゴールを表す配列です。que は State を格納する配列で、これをキューとして使用します。最初に State() で start を格納した局面 state1 を生成し、配列 [state1] を変数 que にセットします。chk は盤面 Board を格納する配列で、同一局面をチェックするために使用します。あとは、キューにデータがある間、幅優先探索を続行します。
while ループの最初で、que の先頭データを popfirst!() で取り出して変数 state にセットします。次の for ループで石を移動します。石は 2 ついっしょに移動させるので、state.board の i 番目と i + 1 番目の要素が空き場所でないことを確認します。それから、movestone() で石を動かして新しい局面を生成し、それを変数 newstate にセットします。
newstate.board が goal と等しければ、解を見つけることができました。printanswer() で手順を表示して、return で探索を終了します。そうでなければ、findfirst() で同一局面がないことを確認して、que に newstate を、chk に newstate.board を追加します。
実行結果は次のようになります。
julia> oshidori() [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 = [space, space, black, black, black, black, white, white, white, white]
興味のある方はいろいろ試してみてください。
それではプログラムを作りましょう。定数とデータ型はおしどりの遊びで作成したものを流用します。次は石を移動する関数を作ります。
リスト : 石の移動
# 白石の移動 (右から左へ)
function movewhite1(state::State)
s = state.pos
b = state.board
if s < length(b) && b[s + 1] == white
newboard = copy(b)
newboard[s] = white
newboard[s + 1] = space
State(newboard, s + 1, state)
else
nothing
end
end
# 白石の移動 (黒石を跳び越える)
function movewhite2(state::State)
s = state.pos
b = state.board
if s < length(b) - 1 && b[s + 1] == black && b[s + 2] == white
newboard = copy(b)
newboard[s] = white
newboard[s + 2] = space
State(newboard, s + 2, state)
else
nothing
end
end
関数 movewhite1() は白石を左へ 1 つ動かします。最初に、空き場所の位置を変数 s に、盤面を変数 b にセットします。次の if 文で石を移動できるかチェックします。s + 1 が配列の範囲内で、b[s + 1] が white なら移動することができます。b をコピーして石を移動し、State() で新しい局面を生成して返します。そうでなければ nothing を返します。
関数 movewhite2() は白石を左へ 2 つ動かします。空き場所の位置を s とすると、s + 2 が配列の範囲内で、s + 2 の位置に白石があり、s + 1 の位置に黒石があれば、白石を動かすことができます。あとの処理は movewhite1() と同じです。同様に、黒石を動かす関数 moveblack1() と moveblack2() を定義します。説明は省略するので、詳細はプログラムリストをお読みください。
最後に蛙跳びゲームを解く関数 kaeru() を作ります。
リスト : 蛙跳びゲーム
function kaeru()
start::Board = [black, black, black, space, white, white, white]
goal::Board = [white, white, white, space, black, black, black]
state1 = State(start, 4, nothing)
que = State[state1]
chk = Board[start]
while !isempty(que)
state = popfirst!(que)
for movefunc = [moveblack1, moveblack2, movewhite1, movewhite2]
newstate = movefunc(state)
if newstate !== nothing
if newstate.board == goal
printanswer(newstate)
return
elseif findfirst(isequal(newstate.board), chk) === nothing
push!(que, newstate)
push!(chk, newstate.board)
end
end
end
end
end
基本的な処理は「おしどりの遊び」と同じです。for ループで移動関数を順番に取り出し、state に適用して新しい局面 newstate を作ります。その値が nothing でなければ石を動かすことができました。newstate.board が goal と等しい場合、解を見つけたので printanswer() で手順を表示します。そうでなければ、関数 findfirst() で同一局面があるかチェックし、新しい局面であれば、それを que と chk に追加します。
それでは実行結果を示します。
julia> kaeru() [1, 1, 1, 0, 2, 2, 2] [1, 1, 0, 1, 2, 2, 2] [1, 1, 2, 1, 0, 2, 2] [1, 1, 2, 1, 2, 0, 2] [1, 1, 2, 0, 2, 1, 2] [1, 0, 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, 1, 2, 1, 0] [2, 1, 2, 1, 2, 0, 1] [2, 1, 2, 0, 2, 1, 1] [2, 0, 2, 1, 2, 1, 1] [2, 2, 0, 1, 2, 1, 1] [2, 2, 2, 1, 0, 1, 1] [2, 2, 2, 0, 1, 1, 1]
15 手で解くことができました。この手順は黒石から動かしていますが、白石から動かしても解くことができます。ところで、このパズルは黒石と白石が後戻りできないことから、同一局面はチェックしなくても動作します。また、バックトラックでも簡単に最短手順を求めることができます。興味のある方は実際に試してみてください。
それではプログラムを作りましょう。最初に定数を定義します。次のリストを見てください。
リスト : 定数の定義
const ha = 0x01
const wa = 0x02
const hb = 0x04
const wb = 0x08
const hc = 0x10
const wc = 0x20
const boat = 0x40
const men = ha | hb | hc
const leftside = 1
const rightside = 2
# ボートに乗る組み合わせ
const riders = [
ha, hb, hc, wa, wb, wc,
ha | hb, ha | hc, hb | hc,
wa | wb, wa | wc, wb | wc,
ha | wa, hb | wb, hc | wc
]
このプログラムでは、三組の夫婦とボートをビットで定義して、左右の岸を整数値で表しています。局面を表すデータ型は State を流用します。board[leftside] が左岸の状態を、board[rightside] が右岸の状態を表します。pos にはボートの位置 (leftside or rightside) を格納します。ボートに乗る組み合わせは、二人（三組の夫婦、男性二人、女性二人）で乗る場合と一人で乗る場合があるので、合計で 15 通りになります。これを配列 riders に定義します。
次は、局面が安全な状態かチェックする関数 issafe() を作ります。
リスト : 安全な状態かチェックする
function issafe(side)
for (w, h) in [(wa, ha), (wb, hb), (wc, hc)]
if side & w > 0 && side & h == 0 && side & men > 0
return false
end
end
true
end
for ループで夫婦の組 (h, w) を順番に取り出します。婦人 w がいて、夫 h がいなくて、他の夫がいる場合は安全ではありません。return で false を返します。3 組の夫婦がすべて安全であれば true を返します。
最後に、幅優先探索でパズルを解く関数 husband() を作ります。
リスト : 幅優先探索
# 岸の状態を表示
function printside(side)
xs = [(boat, "Boat"), (ha, "Ha"), (wa, "Wa"), (hb, "Hb"), (wb, "Wb"), (hc, "Hc"), (wc, "Wc")]
[n for (r, n) = xs if r & side > 0]
end
function printhusband(board)
@printf "%s %s\n" printside(board[1]) printside(board[2])
end
# 幅優先探索
function husband()
allmembers = ha | hb | hc | wa | wb | wc | boat
start::Board = [allmembers, 0]
goal::Board = [0, allmembers]
state1 = State(start, leftside, nothing)
que = State[state1]
chk = Int[start[leftside]]
while !isempty(que)
state = popfirst!(que)
src = state.pos
dst = src == leftside ? rightside : leftside
for rs = riders
if state.board[src] & rs != rs continue end
b = copy(state.board)
b[src] -= rs + boat
b[dst] += rs + boat
if !issafe(b[src]) || !issafe(b[dst]) || findfirst(isequal(b[leftside]), chk) !== nothing
continue
end
newstate = State(b, dst, state)
if b == goal
printanswer(newstate, printhusband)
return
else
push!(que, newstate)
push!(chk, b[1])
end
end
end
end
allmembers は全員がそろった状態を表します。start は [allmembes, 0] に、goal は [0, allmembers] に初期化します。そして、キュー que とチェック用の配列 chk を初期化します。岸の状態は片側がわかればもう一方の状態もわかるので、同一局面のチェックには左側だけを使っています。
while ループの中では、キューの先頭の局面を popfirst!() で取り出し、ボートがある岸を変数 src に、対岸を変数 dst にセットします。その次の for ループで riders から順番に乗り手 rs を取り出します。src 側に乗り手がいない場合は continue でスキップします。
乗り手がいる場合は state.board をコピーして、b[src] から rs + boat を引き算し、b[dst] に rs + boat を足し算します。これでボートと乗り手を移動した新しい盤面を作ることができます。そのあと、issafe() で安全を確認して、findfirst() で同一局面のチェックを行います。安全ではない、または同一局面がある場合は continue でスキップします。あとは、State() で newstate を作成し、今までと同様の処理を行うだけです。
それでは実行結果を示します。最短手数は 11 手で、次のようになりました。
julia> husband() ["Boat", "Ha", "Wa", "Hb", "Wb", "Hc", "Wc"] String[] ["Ha", "Hb", "Hc", "Wc"] ["Boat", "Wa", "Wb"] ["Boat", "Ha", "Wa", "Hb", "Hc", "Wc"] ["Wb"] ["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", "Hc", "Wc"] ["Ha", "Wa", "Hb", "Wb"] String[] ["Boat", "Ha", "Wa", "Hb", "Wb", "Hc", "Wc"]
ところで、夫婦が四組に増えると、二人乗りのボートで川を渡ることはできません。三人乗りのボートにするか、川の中に小島がひとつあれば二人乗りのボートでも渡ることができます。興味のある方は拙作のページ「Puzzle DE Programming: 嫉妬深い夫の問題 (四組の場合)」をお読みくださいませ。
昔々、拙作のページ「Puzzle DE Programming: 続・数字の並べ替え」で調べたことがあるのですが、このパズルは盤面の大きさを n とすると、局面の総数は n! 通りあります。盤面が大きくなると局面の総数は爆発的に増えるので、ここでは線形探索ではなく Julia の辞書を使うことにしましょう。あとは今までのプログラムとほぼ同じです。説明は省略するので、以下のプログラムリストをお読みくださいませ。
リスト : 数字の並び替え
function changenumber(start::Board, goal::Board)
que = State[State(start, findfirst(isequal(0), start), nothing)]
chk = Dict{Board, Bool}(start => true)
while !isempty(que)
state = popfirst!(que)
s = state.pos
for x = [-2, -1, 1, 2]
if 0 < s + x <= length(start)
b = copy(state.board)
b[s] = b[s + x]
b[s + x] = space
if haskey(chk, b) continue end
newstate = State(b, s + x, state)
if b == goal
printanswer(newstate)
return
else
push!(que, newstate)
chk[b] = true
end
end
end
end
end
それでは実行結果を示します。
julia> changenumber([1, 2, 3, 4, 5, 6, 0], [0, 6, 5, 4, 3, 2, 1]) [1, 2, 3, 4, 5, 6, 0] [1, 2, 3, 4, 0, 6, 5] [1, 2, 0, 4, 3, 6, 5] [0, 2, 1, 4, 3, 6, 5] [2, 0, 1, 4, 3, 6, 5] [2, 1, 0, 4, 3, 6, 5] [2, 1, 4, 0, 3, 6, 5] [2, 0, 4, 1, 3, 6, 5] [0, 2, 4, 1, 3, 6, 5] [4, 2, 0, 1, 3, 6, 5] [4, 2, 3, 1, 0, 6, 5] [4, 2, 3, 1, 6, 0, 5] [4, 2, 3, 0, 6, 1, 5] [4, 0, 3, 2, 6, 1, 5] [4, 3, 0, 2, 6, 1, 5] [4, 3, 6, 2, 0, 1, 5] [4, 3, 6, 2, 5, 1, 0] [4, 3, 6, 2, 5, 0, 1] [4, 3, 6, 0, 5, 2, 1] [4, 0, 6, 3, 5, 2, 1] [0, 4, 6, 3, 5, 2, 1] [6, 4, 0, 3, 5, 2, 1] [6, 4, 5, 3, 0, 2, 1] [6, 4, 5, 0, 3, 2, 1] [6, 0, 5, 4, 3, 2, 1] [0, 6, 5, 4, 3, 2, 1]
25 手で解くことができました。実をいうと、スタートが [1, 2, 3, 4, 5, 6, 0] の場合、[0, 6, 5, 4, 3, 2, 1] が最長手数の局面になります。興味のある方は最長手数の局面も調べてみてください。
それではプログラムを作りましょう。次の図を見てください。
┌─┬─┬─┐
│１│２│３│ １──８──３ ●──８──●
├─┼─┼─┤ │ │ │ │
│４│５│６│ ６──11──４ ６──○──４
├─┼─┼─┤ │ │ │ │
│７│８│９│ ７──２──９ ７──●──９
├─┼─┼─┤ │ │ │ │
│10│11│12│ 12──５──10 ○──５──○
└─┴─┴─┘
(Ａ) 盤面 (Ｂ) 騎士の移動 (Ｃ) ＳＴＡＲＴ
図 : 騎士の移動
図 (A) のように、盤面の各マスに番号を付けて表します。すると、騎士の移動は図 (B) のようなグラフで表すことができます。START の局面は図 (C) のようになるので、黒騎士と白騎士を交換できることは簡単にわかりますが、最短手数となる移動手順を求めるのが今回の問題です。
幅優先探索でパズルを解く場合、同一局面の検索処理が重要になります。このパズルは 12 マスに 3 個の黒騎士を置き、残りの 9 マスに白騎士を置くわけですから、局面の総数は次のようになります。
12Ｃ3 * 9Ｃ3 = 220 * 84 = 18480 通り
それほど多くありませんが、線形探索では時間がかかるかもしれません。とりあえず、同一局面のチェックには Julia の辞書を使いましょう。
騎士の移動には隣接リストを使うと簡単です。プログラムは次のようになります。
リスト : 騎士の交換
# 隣接リスト
const adjacent = [
[6, 8], # 1
[7, 9], # 2
[4, 8], # 3
[3, 9, 11], # 4
[10, 12], # 5
[1, 7, 11], # 6
[2, 6, 12], # 7
[1, 3], # 8
[2, 4, 10], # 9
[5, 9], # 10
[4, 6], # 11
[5, 7] # 12
]
# 幅優先探索
function changeknight()
start::Board = [black, black, black, space, space, space,
space, space, space, white, white, white]
goal::Board = [white, white, white, space, space, space,
space, space, space, black, black, black]
que = State[State(start, 0, nothing)]
chk = Dict{Board, Bool}(start => true)
while !isempty(que)
state = popfirst!(que)
for (i, x) = enumerate(state.board)
if x == space continue end
for p = adjacent[i]
if state.board[p] != space continue end
b = copy(state.board)
b[p] = b[i]
b[i] = space
if haskey(chk, b) continue end
newstate = State(b, 0, state)
if newstate.board == goal
printanswer(newstate)
return
else
push!(que, newstate)
chk[b] = true
end
end
end
end
end
局面を生成する State() を呼び出すとき、第 2 引数にはダミーで 0 を渡しています。それから、動かす駒を求めるとき、enumerate() を使って添字 i と駒の種類 (配列の要素) x を求めています。駒 x があるとき、隣接リスト adjacent から移動先の位置 p を求め、p が空き場所であれば駒を動かします。あとは今までとほとんど同じなので、説明は割愛いたします。
それでは実行してみましょう。
julia> changeknight() [1, 1, 1, 0, 0, 0, 0, 0, 0, 2, 2, 2] [0, 1, 1, 0, 0, 1, 0, 0, 0, 2, 2, 2] [0, 1, 0, 1, 0, 1, 0, 0, 0, 2, 2, 2] [0, 1, 0, 0, 0, 1, 0, 0, 1, 2, 2, 2] [0, 1, 0, 2, 0, 1, 0, 0, 1, 2, 0, 2] [0, 1, 2, 0, 0, 1, 0, 0, 1, 2, 0, 2] [0, 1, 2, 0, 0, 0, 0, 0, 1, 2, 1, 2] [0, 1, 2, 1, 0, 0, 0, 0, 0, 2, 1, 2] [0, 1, 2, 1, 0, 0, 0, 0, 2, 0, 1, 2] [0, 1, 2, 1, 0, 0, 2, 0, 2, 0, 1, 0] [0, 1, 2, 1, 0, 2, 0, 0, 2, 0, 1, 0] [0, 0, 2, 1, 0, 2, 1, 0, 2, 0, 1, 0] [2, 0, 2, 1, 0, 0, 1, 0, 2, 0, 1, 0] [2, 0, 2, 1, 0, 0, 0, 0, 2, 0, 1, 1] [2, 2, 2, 1, 0, 0, 0, 0, 0, 0, 1, 1] [2, 2, 2, 0, 0, 0, 0, 0, 1, 0, 1, 1] [2, 2, 2, 0, 0, 0, 0, 0, 0, 1, 1, 1]
最短手数は 16 手になりました。ところで、昔々の話で恐縮ですが、拙作のページ「Puzzle DE Programming: 騎士の交換」で「最長手数の局面」を求めたことがあります。最長手数は 22 手で局面数は対称解を除くと 2 通りになります。興味のある方は最長手数の局面を求めるプログラムにも挑戦してみてください。
#
# puzzle2.jl : Puzzle DE Julia!! 入れ替えパズルと幅優先探索編
#
# Copyright (C) 2018-2021 Makoto Hiroi
#
using Printf
#
# おしどりの遊び
#
# 定数
const space = 0
const black = 1
const white = 2
# 盤面
const Board = Vector{Int}
# 局面
struct State
board::Board
pos::Int
prev
end
# 手順の表示
function printanswer(state, printer=println)
if state.prev !== nothing
printanswer(state.prev, printer)
end
printer(state.board)
end
# 石の移動
function movestone(state::State, dest::Int)
newboard = copy(state.board)
s = state.pos
newboard[s] = newboard[dest]
newboard[s + 1] = newboard[dest + 1]
newboard[dest] = space
newboard[dest + 1] = space
State(newboard, dest, state)
end
# 幅優先探索
function oshidori()
start::Board = [black, white, black, white, black, white, black, white, space, space]
goal::Board = [space, space, white, white, white, white, black, black, black, black]
state1 = State(start, 9, nothing)
que = State[state1]
chk = Board[start]
while !isempty(que)
state = popfirst!(que)
for i = 1 : length(start) - 1
if state.board[i] != space && state.board[i + 1] != space
newstate = movestone(state, i)
if newstate.board == goal
printanswer(newstate)
return
elseif findfirst(isequal(newstate.board), chk) === nothing
push!(que, newstate)
push!(chk, newstate.board)
end
end
end
end
end
#
# 蛙跳びゲーム
#
# 白石の移動 (右から左へ)
function movewhite1(state::State)
s = state.pos
b = state.board
if s < length(b) && b[s + 1] == white
newboard = copy(b)
newboard[s] = white
newboard[s + 1] = space
State(newboard, s + 1, state)
else
nothing
end
end
function movewhite2(state::State)
s = state.pos
b = state.board
if s < length(b) - 1 && b[s + 1] == black && b[s + 2] == white
newboard = copy(b)
newboard[s] = white
newboard[s + 2] = space
State(newboard, s + 2, state)
else
nothing
end
end
# 黒石の移動 (左から右へ)
function moveblack1(state::State)
s = state.pos
b = state.board
if 1 < s && b[s - 1] == black
newboard = copy(b)
newboard[s] = black
newboard[s - 1] = space
State(newboard, s - 1, state)
else
nothing
end
end
function moveblack2(state::State)
s = state.pos
b = state.board
if 2 < s && b[s - 1] == white && b[s - 2] == black
newboard = copy(b)
newboard[s] = black
newboard[s - 2] = space
State(newboard, s - 2, state)
else
nothing
end
end
# 幅優先探索
function kaeru()
start::Board = [black, black, black, space, white, white, white]
goal::Board = [white, white, white, space, black, black, black]
state1 = State(start, 4, nothing)
que = State[state1]
chk = Board[start]
while !isempty(que)
state = popfirst!(que)
for movefunc = [moveblack1, moveblack2, movewhite1, movewhite2]
newstate = movefunc(state)
if newstate !== nothing
if newstate.board == goal
printanswer(newstate)
return
elseif findfirst(isequal(newstate.board), chk) === nothing
push!(que, newstate)
push!(chk, newstate.board)
end
end
end
end
end
#
# 嫉妬深い夫の問題
#
# 定数
const ha = 0x01
const wa = 0x02
const hb = 0x04
const wb = 0x08
const hc = 0x10
const wc = 0x20
const boat = 0x40
const men = ha | hb | hc
const leftside = 1
const rightside = 2
# ボートに乗る組み合わせ
const riders = [
ha, hb, hc, wa, wb, wc,
ha | hb, ha | hc, hb | hc,
wa | wb, wa | wc, wb | wc,
ha | wa, hb | wb, hc | wc
]
# 安全確認
function issafe(side)
for (w, h) in [(wa, ha), (wb, hb), (wc, hc)]
# 婦人 w がいて、夫 h がいなくて、他の夫がいる場合はダメ
if side & w > 0 && side & h == 0 && side & men > 0
return false
end
end
true
end
# 岸の状態を表示
function printside(side)
xs = [(boat, "Boat"), (ha, "Ha"), (wa, "Wa"), (hb, "Hb"), (wb, "Wb"), (hc, "Hc"), (wc, "Wc")]
[n for (r, n) = xs if r & side > 0]
end
function printhusband(board)
@printf "%s %s\n" printside(board[1]) printside(board[2])
end
# 幅優先探索
function husband()
allmembers = ha | hb | hc | wa | wb | wc | boat
start::Board = [allmembers, 0]
goal::Board = [0, allmembers]
state1 = State(start, leftside, nothing)
que = State[state1]
chk = Int[start[leftside]]
while !isempty(que)
state = popfirst!(que)
src = state.pos
dst = src == leftside ? rightside : leftside
for rs = riders
if state.board[src] & rs != rs continue end
b = copy(state.board)
b[src] -= rs + boat
b[dst] += rs + boat
if !issafe(b[src]) || !issafe(b[dst]) || findfirst(isequal(b[leftside]), chk) !== nothing
continue
end
newstate = State(b, dst, state)
if b == goal
printanswer(newstate, printhusband)
return
else
push!(que, newstate)
push!(chk, b[1])
end
end
end
end
#
# 数字の並び替え
#
function changenumber(start::Board, goal::Board)
que = State[State(start, findfirst(isequal(0), start), nothing)]
chk = Dict{Board, Bool}(start => true)
while !isempty(que)
state = popfirst!(que)
s = state.pos
for x = [-2, -1, 1, 2]
if 0 < s + x <= length(start)
b = copy(state.board)
b[s] = b[s + x]
b[s + x] = space
if haskey(chk, b) continue end
newstate = State(b, s + x, state)
if b == goal
printanswer(newstate)
return
else
push!(que, newstate)
chk[b] = true
end
end
end
end
end
#
# 騎士の交換
#
# 隣接リスト
const adjacent = [
[6, 8], # 1
[7, 9], # 2
[4, 8], # 3
[3, 9, 11], # 4
[10, 12], # 5
[1, 7, 11], # 6
[2, 6, 12], # 7
[1, 3], # 8
[2, 4, 10], # 9
[5, 9], # 10
[4, 6], # 11
[5, 7] # 12
]
# 幅優先探索
function changeknight()
start::Board = [black, black, black, space, space, space,
space, space, space, white, white, white]
goal::Board = [white, white, white, space, space, space,
space, space, space, black, black, black]
que = State[State(start, 0, nothing)]
chk = Dict{Board, Bool}(start => true)
while !isempty(que)
state = popfirst!(que)
for (i, x) = enumerate(state.board)
if x == space continue end
for p = adjacent[i]
if state.board[p] != space continue end
b = copy(state.board)
b[p] = b[i]
b[i] = space
if haskey(chk, b) continue end
newstate = State(b, 0, state)
if newstate.board == goal
printanswer(newstate)
return
else
push!(que, newstate)
chk[b] = true
end
end
end
end
end