前回は基本的な探索アルゴリズムである深さ優先探索、幅優先探索、反復深化を説明しました。今回は簡単な例題として、積木の移動手順を求めるプログラムを作ってみましょう。
積木は赤 (red)、青 (blue)、緑 (green) の三種類あり、積木を置く場所は x, y, z の三か所あります。積木は、一回にひとつしか移動できません。また、上に積木が置かれている場合も、移動することはできません。上にある積木をどかしてから移動します。左図の初期状態の場合、積木 red を場所 y か場所 z へ動かすことはできますが、積木 blue や green を動かすことはできません。
問題はスタートから積木をひとつずつ動かして、ゴールになるまでの移動手順を求めることです。
最初にデータ構造を決めましょう。積木は文字列 "red", "blue", "green" で表すことにします。積木はリストに格納して、そのリストをタプルに格納することにしましょう。すると、スタートとゴールの局面 (状態) は次のように表すことができます。
start: (List("red", "blue", "green"), Nil, Nil) goal : (Nil, Nil, List("red", "blue", "green"))
タプルの 1 番目の要素が場所 x, 2 番目の要素が場所 y, 3 番目の要素が場所 z を表します。各場所の状態をリストで表すと、一番上の積木はリストのパターンマッチング x::xs で簡単に取り出すことができます。それから、局面を表す型が長くなるので、type で別名を定義します。
リスト : 積木の局面 type State = (List[String], List[String], List[String])
次は積木を動かすプログラムを作ります。積木の動かし方は次の 6 通りがあります。
x -> y, x -> z y -> x, y -> z z -> x, z -> y
これをそのままプログラムすると、次のようになります。
リスト : 積木を動かす // x -> y def moveXtoY(st: State): List[State] = st match { case (x::xs, ys, zs) => List((xs, x::ys, zs)) case _ => Nil } // x -> z def moveXtoZ(st: State): List[State] = st match { case (x::xs, ys, zs) => List((xs, ys, x::zs)) case _ => Nil } // y -> x def moveYtoX(st: State): List[State] = st match { case (xs, y::ys, zs) => List((y::xs, ys, zs)) case _ => Nil } // y -> z def moveYtoZ(st: State): List[State] = st match { case (xs, y::ys, zs) => List((xs, ys, y::zs)) case _ => Nil } // z -> x def moveZtoX(st: State): List[State] = st match { case (xs, ys, z::zs) => List((z::xs, ys, zs)) case _ => Nil } // z -> y def moveZtoY(st: State): List[State] = st match { case (xs, ys, z::zs) => List((xs, z::ys, zs)) case _ => Nil }
moveXtoY は x にある積み木を y へ移動します。パターンマッチングで場所 x の一番上にある積木 x を取り出して、それを場所 y のリスト ys の先頭に追加します。返り値は新しい状態 (State) をリストに格納したものです。場所 x に積み木がない場合は空リスト Nil を返します。他の関数も同じように一番上の積木を動かします。
これらの関数を使って、局面 st から積木を動かして新しい局面を作成し、それをリストに格納して返す関数 makeNewState を作ります。
リスト : 新しい局面を作る // 移動関数表 val moveFunc = List(moveXtoY _, moveXtoZ _, moveYtoX _, moveYtoZ _, moveZtoY _, moveZtoX _) // 新しい局面を生成する def makeNewState(st: State): List[State] = moveFunc.flatMap((f:State => List[State]) => f(st))
積木を移動する関数をリスト moveFunc に格納します。関数値を取り出していることに注意してください。関数 makeNewState は、現在の状態 st にこれらの関数を適用して、新しい状態を生成します。この場合、map を使うとリストの中にリストが格納される、つまり、返り値の型が List[List[State]] になってしまいます。このような場合、リストを平坦化 (flatten) すると List[List[State]] を List[State] に変換することができます。
リストのメソッド flatMap は map のあとに flatten を行ってくれます。簡単な例を示しましょう。
scala> List(1,2,3,4,5).map(x => List(x,x)) val res0: List[List[Int]] = List(List(1, 1), List(2, 2), List(3, 3), List(4, 4), List(5, 5)) scala> List(1,2,3,4,5).flatMap(x => List(x,x)) val res1: List[Int] = List(1, 1, 2, 2, 3, 3, 4, 4, 5, 5)
無名関数は引数 x を 2 つリストに格納して返します。map の場合、返り値の型は List[List[Int]] になりますが、flatMap ではマッピングのあとに平坦化が行われるので List[Int] になります。また、平坦化が行われるとき、Nil は削除されるので、makeNewState の返り値は新しい State を格納したリストになります。
それでは、実際に試してみましょう。
scala> import tumiki._ import tumiki._ scala> makeNewState((List("red", "blue", "green"), Nil, Nil)) val res0: List[tumiki.State] = List((List(blue, green),List(red),List()), (List(blue, green),List(),List(red))) scala> makeNewState((List("red"), List("blue"), List("green"))) val res1: List[tumiki.State] = List((List(),List(red, blue),List(green)), (List(),List(blue),List(red, green)), (List(blue, red),List(),List(green)), (List(red),List(),List(blue, green)), (List(red),List(green, blue),List()), (List(green, red),List(blue),List()))
最初の例は、積木がある場所が x しかないので、生成される State は、red を y に移動したものと、z に移動したものの 2 つになります。次の例は x, y, z に積木があるので、生成される新しい State は 6 通りになります。
あとのプログラムは簡単です。深さ優先探索は次のようになります。
リスト : 深さ優先探索 // 移動手順の表示 def printMove(move: List[State]): Unit = { for (st <- move) println(st) } def depthFirstSearch(start: State, goal: State): Unit = { def dfs(move: List[State]): Unit = { val st = move.head if (st == goal) { printMove(move.reverse) throw new Exception("Found") } else { for (newSt <- makeNewState(st) if (!(move contains newSt))) dfs(newSt::move) } } try { dfs(List(start)) } catch { case e:Exception => () } }
実際の処理は局所関数 dfs で行います。引数 move は State を格納したリストです。これで移動手順を表すことにします。move の先頭要素が現在の状態を表します。それを変数 st にセットして、goal に到達したかチェックします。そうであれば、printMove で手順を表示して、探索を終了するため大域脱出します。
goal に到達していない場合は、makeNewState で新しい局面を生成し、for 式で局面を順番に取り出して変数 newSt にセットします。そして、newSt が移動手順 move の中に含まれていなければ、newSt を move に追加して dfs を再帰呼び出しします。あとは、try 式の中で dfs を呼び出して catch で大域脱出を捕捉します。
それでは実行してみましょう。
scala> val start: State = (List("red", "blue", "green"), Nil, Nil) val start: tumiki.State = (List(red, blue, green),List(),List()) scala> val goal: State = (Nil, Nil, List("red", "blue", "green")) val goal: tumiki.State = (List(),List(),List(red, blue, green)) scala> depthFirstSearch(start, goal) (List(red, blue, green),List(), List()) (List(blue, green), List(red), List()) (List(green), List(blue, red), List()) (List(), List(green, blue, red),List()) (List(), List(blue, red), List(green)) (List(blue), List(red), List(green)) (List(), List(red), List(blue, green)) (List(red), List(), List(blue, green)) (List(), List(), List(red, blue, green))
移動手順は手作業で直しています。興味のある方は、移動手順をきれいに表示するようにプログラムを修正してみてください。スタートからゴールまで 8 手かかっています。もちろん、これは最短手順ではありません。
次は幅優先探索で解いてみましょう。
リスト : 幅優先探索 def breadthFirstSearch(start: State, goal: State): Unit = { val q = new Queue[List[State]] var states = List(start) q.enqueue(List(start)) while (!q.isEmpty()) { val move = q.dequeue() val st = move.head if (st == goal) { printMove(move.reverse) return } for (newSt <- makeNewState(st) if (!(states contains newSt))) { states = newSt::states q.enqueue(newSt::move) } } }
プログラムは経路の探索とほぼ同じです。ただし、一つだけ異なるところがあります。幅優先探索で最短手順を求める場合、すべての手順を記憶しておく必要はありません。n 手目の移動で作られた局面が、n 手目以前の局面で出現しているのであれば、n 手より短い手数で到達する移動手順があるはずです。したがって、この n 手の手順を記憶しておく必要はなく、探索を続けるのは今までに出現していない新しい局面だけになります。
新しく出現した局面は変数 states のリストに格納します。最初は、start の局面を格納しておきます。makeNewState で生成した局面 newSt が states にあるか contains で探索して、見つからなければ新しい局面です。states に newSt を追加して、キューに newSt::move を追加します。
それでは実行してみましょう。
scala> breadthFirstSearch(start, goal) (List(red, blue, green),List(), List()) (List(blue, green), List(red), List()) (List(green), List(blue, red),List()) (List(), List(blue, red),List(green)) (List(), List(red), List(blue, green)) (List(), List(), List(red, blue, green))
スタートからゴールまで 5 手で到達しました。これが最短手数になります。
最後に反復深化のプログラムを作ります。
リスト : 反復深化 def idSearch(start: State, goal: State): Unit = { def dfs(limit: Int, move: List[State]): Unit = { if (move.length == limit) { if (move.head == goal) { printMove(move.reverse) throw new Exception("Found") } } else { for (newSt <- makeNewState(move.head)) dfs(limit, newSt::move) } } // try { for (i <- 1 to 10) dfs(i, List(start)) } catch { case e:Exception => () } }
このプログラムも経路の探索とほぼ同じです。難しいところは特にないと思います。
それでは実行してみましょう。
scala> idSearch(start, goal) (List(red, blue, green),List(), List()) (List(blue, green), List(red), List()) (List(green), List(blue, red),List()) (List(), List(blue, red),List(green)) (List(), List(red), List(blue, green)) (List(), List(), List(red, blue, green))
幅優先探索と同じく、5 手でゴールに到達しました。このように、反復深化でも最短手数の手順を求めることができます。
// // tumiki.scala : 積木の移動 // // Copyright (C) 2014-2021 Makoto Hiroi // import dlist._ object tumiki { // 局面 (x, y, z) type State = (List[String], List[String], List[String]) // x -> y def moveXtoY(st: State): List[State] = st match { case (x::xs, ys, zs) => List((xs, x::ys, zs)) case _ => Nil } // x -> z def moveXtoZ(st: State): List[State] = st match { case (x::xs, ys, zs) => List((xs, ys, x::zs)) case _ => Nil } // y -> x def moveYtoX(st: State): List[State] = st match { case (xs, y::ys, zs) => List((y::xs, ys, zs)) case _ => Nil } // y -> z def moveYtoZ(st: State): List[State] = st match { case (xs, y::ys, zs) => List((xs, ys, y::zs)) case _ => Nil } // z -> x def moveZtoX(st: State): List[State] = st match { case (xs, ys, z::zs) => List((z::xs, ys, zs)) case _ => Nil } // z -> y def moveZtoY(st: State): List[State] = st match { case (xs, ys, z::zs) => List((xs, z::ys, zs)) case _ => Nil } // 移動関数表 val moveFunc = List(moveXtoY _, moveXtoZ _, moveYtoX _, moveYtoZ _, moveZtoY _, moveZtoX _) // 新しい局面の生成 def makeNewState(st: State): List[State] = moveFunc.flatMap((f:State => List[State]) => f(st)) // 移動手順の表示 def printMove(move: List[State]): Unit = { for (st <- move) println(st) } // 深さ優先探索 def depthFirstSearch(start: State, goal: State): Unit = { def dfs(move: List[State]): Unit = { val st = move.head if (st == goal) { printMove(move.reverse) throw new Exception("Found") } else { for (newSt <- makeNewState(st) if (!(move contains newSt))) dfs(newSt::move) } } try { dfs(List(start)) } catch { case e:Exception => () } } // 幅優先探索 def breadthFirstSearch(start: State, goal: State): Unit = { val q = new Queue[List[State]] var states = List(start) q.enqueue(List(start)) while (!q.isEmpty()) { val move = q.dequeue() val st = move.head if (st == goal) { printMove(move.reverse) return } for (newSt <- makeNewState(st) if (!(states contains newSt))) { states = newSt::states q.enqueue(newSt::move) } } } // 反復深化 def idSearch(start: State, goal: State): Unit = { def dfs(limit: Int, move: List[State]): Unit = { if (move.length == limit) { if (move.head == goal) { printMove(move.reverse) throw new Exception("Found") } } else { for (newSt <- makeNewState(move.head)) dfs(limit, newSt::move) } } // try { for (i <- 1 to 10) dfs(i, List(start)) } catch { case e:Exception => () } } }
今回は簡単なパズルを 3 つ出題します。Scala で解法プログラムを作ってください。
騎士(ナイト)はチェスの駒のひとつで、将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。
このナイトを動かして、どのマスにもちょうど一回ずつ訪れて出発点に戻る周遊経路を求めるのが問題です。ちなみに、4 行 4 列の盤面には解がありませんが、6 行 6 列、8 行 8 列の盤面には解が存在します。大きな盤面を解くのは大変なので、問題 A の盤面でナイトの周遊経路を求めてください。なお、ナイトは×印のマスに移動することはできません。
大きな容器に水が入っています。目盛の付いていない 8 リットルと 5 リットルの容器を使って、大きな容器から 4 リットルの水を汲み出してください。4 リットルの水は、どちらの容器に入れてもかまいません。水をはかる最短手順を求めてください。なお、水の総量に制限はありません。
「水差し問題」はいろいろな呼び方があって、「水をはかる問題」とか「水を測り出す問題」と呼ばれることもあります。
Hoppers は「ペグ・ソリテア」と呼ばれるパズルのひとつです。出典は C magazine 2000 年 2 月号の「Cマガ電脳クラブ第 107 回 Hoppers 」です。
ペグ・ソリテアは、盤上に配置されたペグ (駒) を、最後にはひとつ残るように取り除いていく古典的なパズルです。ペグは次のルールに従って移動し、除去することができます。
盤は今までに多数考案されていますが、33 穴英国盤、37 穴フランス盤、41 穴盤が有名でしょう。33 穴英国盤と Hoppers を図に示します。
(1) 33 穴英国盤
(2) Hoppers 図 : ペグ・ソリテア
それぞれのマスにペグがありますが、そこからひとつペグを取り除いてゲームを始めます。図では黒丸でペグを表し、白丸で空き場所を表しています。ルールに従ってペグを移動し、最後にひとつだけ残ればクリアとなります。ただし、ペグを取り除く位置によって、解けない場合もあるので注意してください。
それでは問題です。図 (2) に示したように、Hoppers の中央のペグを取り除きます。この状態から始めて、最後のペグが中央の位置に残る跳び方の最小手数を求めてください。
それではプログラムを作りましょう。この問題は盤面が小さいので、単純な深さ優先探索で簡単に解くことができます。下図に示すように、盤面のマスに番号をつけます。
あとは隣接リストを定義して、深さ優先探索で周遊経路を探索するだけです。プログラムは次のようになります。
リスト : 「騎士の周遊」解法プログラム // 隣接リスト val adjacent = Array( List(5, 6), // 0 List(2, 7), // 1 List(1, 9), // 2 List(7, 8, 10), // 3 List(6, 9, 11), // 4 List(0, 10), // 5 List(0, 4, 10, 12), // 6 List(1, 3, 9, 13), // 7 List(3, 13), // 8 List(2, 4, 7), // 9 List(3, 5, 6), // 10 List(4, 12), // 11 List(6, 11), // 12 List(7, 8)) // 13 // 深さ優先探索 def knightTour(path: List[Int] = List(0)): Unit = { if (path.length == adjacent.length) { val xs = path.reverse if (adjacent(path.head).contains(xs.head)) println(xs) } else { for (x <- adjacent(path.head) if (!(path contains x))) { knightTour(x::path) } } }
隣接リストはベクタ adjacent に定義します。要素はリストであることに注意してください。関数 knightTour は深さ優先探索で騎士の周遊経路を求めます。引数 path は経路(リスト)を表します。周遊経路を求めるので出発点はどこでもいいのですが、今回は 0 を出発点としてます。
全部のマスを 1 回ずつ訪れると path の長さは adjacent.length (14) になります。ここで、最後のマスから出発点に戻ることができれば周遊経路になります。これは最後のマスの隣接リストに出発点が含まれているかチェックすればいいですね。この処理を contains で行っています。そうであれば周遊経路になるので、関数 println で path を表示します。
n が 14 より小さい場合は、深さ優先で騎士を進めていきます。この処理は経路の探索と同じなので、詳しく説明する必要はないでしょう。これでプログラムは完成です。
それでは、実行してみましょう。
scala> puz02.knightTour() List(0, 5, 10, 3, 8, 13, 7, 1, 2, 9, 4, 11, 12, 6) List(0, 6, 12, 11, 4, 9, 2, 1, 7, 13, 8, 3, 10, 5)
2 通りの周遊経路が表示されましたが、逆回りの経路があるので、実際の経路は次の 1 通りしかありません。
「騎士の周遊」は、拙作のページ Puzzle DE Programming の 「騎士の巡歴 (Knight's Tour)」 でも取り上げています。興味のある方は参考にしてください。
水差し問題の場合、次に示す 3 通りの操作があります。
3 の操作は、容器が空になるまで水を移す場合と、もう一方の容器が満杯になるまで水を移す場合があります。容器は 2 つあるので、全部で 6 通りの操作があります。最初に、これらの操作を行う関数を定義します。プログラムは次のようになります。
リスト : 容器の操作 val maxA = 8 val maxB = 5 type State = (Int, Int) // A -> 0 def transfer1(st: State): State = st match { case (a, b) => (0, b) } // A -> Full def transfer2(st: State): State = st match { case (a, b) => (maxA, b) } // A -> B def transfer3(st: State): State = st match { case (a, b) => { val c = maxB - b if (a <= c) (0, a + b) else (a - c, b + c) } } // B -> 0 def transfer4(st: State): State = st match { case (a, b) => (a, 0) } // B -> Full def transfer5(st: State): State = st match { case (a, b) => (a, maxB) } // B -> A def transfer6(st: State): State = st match { case (a, b) => { val c = maxA - a if (b <= c) (a + b, 0) else (a + c, b - c) } }
タプル (a, b) で局面を表します。maxA は 8 リットルの容器の水の量、maxB は 5 リットルの容器の水の量を表します。引数 st が容器に入っている水の量を表します。容器を水で満たす、または空にする操作は簡単ですね。他の容器へ移す場合、たとえば transfer3 では、B の空き容量と A の水の量を比較して、少ない方が移す水の量になります。
次はこれらの関数を使って新しい局面を生成する関数 makeNewState を作ります。
リスト : 新しい局面の生成 // 操作関数表 val transTable = List(transfer1 _, transfer2 _, transfer3 _, transfer4 _, transfer5 _, transfer6 _) def makeNewState(st: State): List[State] = transTable.map((f: State => State) => f(st))
容器を操作する関数をリスト transTable に格納します。関数値を取り出していることに注意してください。関数 makeNewState は、現在の状態 st にこれらの関数を適用して、新しい状態を生成します。これは map を使えば簡単ですね。
あとは幅優先探索で最短手順を求めるだけです。次のリストを見てください。
リスト : 水差し問題の解法 def water(goal: Int): Unit = { val q = new Queue[List[State]] var states = List((0, 0)) q.enqueue(List((0, 0))) while (!q.isEmpty()) { val move = q.dequeue() val st = move.head if (st._1 == goal || st._2 == goal) { for (x <- move.reverse) println(x) return } for (newSt <- makeNewState(st) if (!(states contains newSt))) { states = newSt::states q.enqueue(newSt::move) } } }
関数 water の引数 goal は求める水の量です。手順はタプルを格納したリストで表します。最初に List((0, 0)) をキューに格納し、キューからデータを取り出して探索を行います。新しく出現した局面は states のリストに格納します。A または B に水が goal リットルあれば解を見つけることができました。for 式で手順を表示して return で探索を終了します。
そうでなければ、makeNewState で新しい局面を生成して、for 式で一つずつ取り出して変数 newSt にセットします。newSt と同一局面がないか contains でチェックします。newSt が新しく出現した局面であれば、newSt をstates に追加して、newSt::move をキューに追加します。
結果は次のようになりました。
scala> puz02.water(4) (0,0) (0,5) (5,0) (5,5) (8,2) (0,2) (2,0) (2,5) (7,0) (7,5) (8,4)
このように、最短手順は 10 手になります。
ペグ・ソリテアの場合、ペグの「跳び先表」を用意すると簡単にプログラムできます。座標は次のように定義します。
図 : Hoppers
リスト : 跳び先表 val jumpTable = Array( List((1, 2), (3, 6), (5, 10)), List((3, 5), (6, 11), (4, 7)), List((1, 0), (4, 6), (7, 12)), List((6, 9)), List((6, 8)), List((3, 1), (6, 7), (8, 11)), List((3, 0), (4, 2), (8, 10), (9, 12)), List((4, 1), (6, 5), (9, 11)), List((6, 4)), List((6, 3)), List((5, 0), (8, 6), (11, 12)), List((8, 5), (6, 1), (9, 7)), List((11, 10), (9, 6), (7, 2)))
タプルの第 1 要素が跳び越す位置、第 2 要素が着地する位置を表します。たとえば、0 番の位置にあるペグは、1 番を跳び越して 2 番へ移動する場合と、3 番を跳び越して 6 番へ移動する場合と、5 番を飛び越して 10 番へ移動する場合の 3 通りがあります。
盤面は Boolean 型の配列 board で、ペグの有無は true / false で表すことにします。
次は単純な反復深化で最短手順を求めます。
リスト : Hoppers の解法 def hoppers(): Unit = { // 反復深化 def dfs(limit: Int, jc: Int, move: List[(Int, Int)]): Unit = { if (jc > limit) return if (move.length == MaxJump) { if (board(Hole)) printMove(move.reverse) } else { for (from <- 0 until Size) { for ((del, to) <- jumpTable(from) if (board(from) && board(del) && !board(to))) { board(from) = false board(del) = false board(to) = true dfs(limit, if (move.head._2 == from) jc else jc + 1, (from, to)::move) board(from) = true board(del) = true board(to) = false } } } } // first move 0 -> 6 for (i <- 0 until Size) board(i) = true board(0) = false board(3) = false for (i <- 2 to MaxJump) { println("-----" + i + "-----") dfs(i, 1, List((0, 6))) if (count > 0) { println(count) return } } }
実際の処理は局所関数 dfs で行います。引数 limit が上限値、jc が跳んだ回数、move が移動手順です。移動手順はタプル (跳び元, 跳び先) をリストに格納して表します。
jc が上限値 limit より多くなったならば探索を打ち切ります。move の長さが MaxJump (11) に達したならば、盤上にはひとつのペグしか残っていません。それが中央の board[Hole] にあるならば解の条件を満たします。printMove で手順を表示します。ペグが複数残っている場合は、探索を続行します。for 式の変数 from が跳び元の位置を表します。跳び先表から跳び越す位置を del に、着地する位置を to にセットします。from と del の位置にペグがあり、to の位置が空いているならば、ペグを移動することができます。
ペグの移動は簡単です。from, del の位置を false に、to の位置を true に書き換えて、dfs を再帰呼び出しします。このとき、前回移動したペグ move.head._2 と同じペグならば、跳んだ回数 jc をカウントしないことに注意してください。手順 move には (from, to) を追加します。そして、再帰呼び出しから戻ってきたら、board を元の状態に戻します。
あとは反復深化の上限値を増やしながら dfs を呼び出します。for 式の変数 i が上限値を表します。最初の移動は、四隅にあるペグのひとつを中央に動かす手順しかありません。そこで、最初は 0 のペグを 6 へ動かすことに決めて、その状態から探索を開始します。count が 0 でなければ、解を見つけたので反復深化を終了します。
最後に移動手順を表示する関数 printMove を作ります。
リスト : 手順の表示 def printMove(move: List[(Int, Int)]): Unit = { var prev = move.head._2 print("[" + move.head._1 + "," + prev) for ((from, to) <- move.tail) { if (from == prev) { print("," + to) } else { print("]\n[" + from + "," + to) } prev = to } println("]\n") count += 1 }
移動手順は 1 手を [from, to] で表し、連続跳びの場合は [from, to1, to2, ..., to3] とします。1 手前の跳び先の位置を変数 prev にセットしておいて、それと動かすペグの位置が同じであれば連続跳びです。跳び先の位置を prev にセットして、それを表示します。違うペグが跳ぶ場合は、] [ を表示してから動かすペグの位置と跳び先の位置を表示します。
それでは実行してみましょう。
scala> puz02.hoppers() -----2----- -----3----- -----4----- -----5----- -----6----- -----7----- [0,6] [9,3] [2,0,6] [11,1] [10,0,2,6] [8,4] [12,2,6] ・・・ 省略 ・・・ [0,6] [9,3] [10,6] [4,8] [12,10,6] [1,11] [2,12,10,0,6] 18
7 手で解くことができました。解は全部で 18 通りになりました。最近のパソコンは高性能なので、穴の数が少ない盤面であれば、単純な反復深化でも高速に解くことができます。
// // puz02.scala : パズルの解法 (2) // // Copyright (C) 2014-2021 Makoto Hiroi // import dlist._ object puz02 { // // 問題1「騎士の周遊」 // // 隣接リスト val adjacent = Array( List(5, 6), // 0 List(2, 7), // 1 List(1, 9), // 2 List(7, 8, 10), // 3 List(6, 9, 11), // 4 List(0, 10), // 5 List(0, 4, 10, 12), // 6 List(1, 3, 9, 13), // 7 List(3, 13), // 8 List(2, 4, 7), // 9 List(3, 5, 6), // 10 List(4, 12), // 11 List(6, 11), // 12 List(7, 8)) // 13 // 深さ優先探索 def knightTour(path: List[Int] = List(0)): Unit = { if (path.length == adjacent.length) { val xs = path.reverse if (adjacent(path.head).contains(xs.head)) println(xs) } else { for (x <- adjacent(path.head) if (!(path contains x))) { knightTour(x::path) } } } // // 問題2「水差し問題」 // val maxA = 8 val maxB = 5 type State = (Int, Int) // A -> 0 def transfer1(st: State): State = st match { case (a, b) => (0, b) } // A -> Full def transfer2(st: State): State = st match { case (a, b) => (maxA, b) } // A -> B def transfer3(st: State): State = st match { case (a, b) => { val c = maxB - b if (a <= c) (0, a + b) else (a - c, b + c) } } // B -> 0 def transfer4(st: State): State = st match { case (a, b) => (a, 0) } // B -> Full def transfer5(st: State): State = st match { case (a, b) => (a, maxB) } // B -> A def transfer6(st: State): State = st match { case (a, b) => { val c = maxA - a if (b <= c) (a + b, 0) else (a + c, b - c) } } // 操作関数表 val transTable = List(transfer1 _, transfer2 _, transfer3 _, transfer4 _, transfer5 _, transfer6 _) // 新しい局面を生成する def makeNewState(st: State): List[State] = transTable.map((f: State => State) => f(st)) // 幅優先探索 def water(goal: Int): Unit = { val q = new Queue[List[State]] var states = List((0, 0)) q.enqueue(List((0, 0))) while (!q.isEmpty()) { val move = q.dequeue() val st = move.head if (st._1 == goal || st._2 == goal) { for (x <- move.reverse) println(x) return } for (newSt <- makeNewState(st) if (!(states contains newSt))) { states = newSt::states q.enqueue(newSt::move) } } } // // 問題3「Hoppers」 // // 跳び先表 val jumpTable = Array( List((1, 2), (3, 6), (5, 10)), List((3, 5), (6, 11), (4, 7)), List((1, 0), (4, 6), (7, 12)), List((6, 9)), List((6, 8)), List((3, 1), (6, 7), (8, 11)), List((3, 0), (4, 2), (8, 10), (9, 12)), List((4, 1), (6, 5), (9, 11)), List((6, 4)), List((6, 3)), List((5, 0), (8, 6), (11, 12)), List((8, 5), (6, 1), (9, 7)), List((11, 10), (9, 6), (7, 2))) val Hole = 6 val Size = 13 val MaxJump = 11 // 盤面 val board = new Array[Boolean](Size) // 解の総数 var count = 0 // 手順の表示 def printMove(move: List[(Int, Int)]): Unit = { var prev = move.head._2 print("[" + move.head._1 + "," + prev) for ((from, to) <- move.tail) { if (from == prev) { print("," + to) } else { print("]\n[" + from + "," + to) } prev = to } println("]\n") count += 1 } def hoppers(): Unit = { // 反復深化 def dfs(limit: Int, jc: Int, move: List[(Int, Int)]): Unit = { if (jc > limit) return if (move.length == MaxJump) { if (board(Hole)) printMove(move.reverse) } else { for (from <- 0 until Size) { for ((del, to) <- jumpTable(from) if (board(from) && board(del) && !board(to))) { board(from) = false board(del) = false board(to) = true dfs(limit, if (move.head._2 == from) jc else jc + 1, (from, to)::move) board(from) = true board(del) = true board(to) = false } } } } // first move 0 -> 6 for (i <- 0 until Size) board(i) = true board(0) = false board(3) = false for (i <- 2 to MaxJump) { println("-----" + i + "-----") dfs(i, 1, List((0, 6))) if (count > 0) { println(count) return } } } }