今回は簡単なパズルを 3 つ出題します。Scala で解法プログラムを作ってください。
騎士（ナイト）はチェスの駒のひとつで、将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。
┌─┬─┬─┬─┬─┐ ┌─┬─┐
│ │●│ │●│ │ │Ｋ│ │
├─┼─┼─┼─┼─┤ ┌─┼─┼─┼─┐
│●│ │ │ │●│ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┤
│ │ │Ｋ│ │ │ │ │×│×│ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┤
│●│ │ │ │●│ │ │ │ │ │
├─┼─┼─┼─┼─┤ └─┼─┼─┼─┘
│ │●│ │●│ │ │ │ │
└─┴─┴─┴─┴─┘ └─┴─┘
● : ナイト (K) が動ける位置 問題Ａ
図 : 騎士の周遊
このナイトを動かして、どのマスにもちょうど一回ずつ訪れて出発点に戻る周遊経路を求めるのが問題です。ちなみに、4 行 4 列の盤面には解がありませんが、6 行 6 列、8 行 8 列の盤面には解が存在します。大きな盤面を解くのは大変なので、問題 A の盤面でナイトの周遊経路を求めてください。なお、ナイトは×印のマスに移動することはできません。
大きな容器に水が入っています。目盛の付いていない 8 リットルと 5 リットルの容器を使って、大きな容器から 4 リットルの水を汲み出してください。4 リットルの水は、どちらの容器に入れてもかまいません。水をはかる最短手順を求めてください。なお、水の総量に制限はありません。
「水差し問題」はいろいろな呼び方があって、「水をはかる問題」とか「水を測り出す問題」と呼ばれることもあります。
Hoppers は「ペグ・ソリテア」と呼ばれるパズルのひとつです。出典は C magazine 2000 年 2 月号の「Ｃマガ電脳クラブ第 107 回 Hoppers 」です。
ペグ・ソリテアは、盤上に配置されたペグ (駒) を、最後にはひとつ残るように取り除いていく古典的なパズルです。ペグは次のルールに従って移動し、除去することができます。
盤は今までに多数考案されていますが、33 穴英国盤、37 穴フランス盤、41 穴盤が有名でしょう。33 穴英国盤と Hoppers を図に示します。
●─●─●
│ │ │
●─●─● ●───●───●
│ │ │ │＼ ／│＼ ／│
●─●─●─●─●─●─● │ ● │ ● │
│ │ │ │ │ │ │ │／ ＼│／ ＼│
●─●─●─○─●─●─● ●───○───●
│ │ │ │ │ │ │ │＼ ／│＼ ／│
●─●─●─●─●─●─● │ ● │ ● │
│ │ │ │／ ＼│／ ＼│
●─●─● ●───●───●
│ │ │
●─●─● (2) Hoppers
(1) 33 穴英国盤
図 : ペグ・ソリテア
それぞれのマスにペグがありますが、そこからひとつペグを取り除いてゲームを始めます。図では黒丸でペグを表し、白丸で空き場所を表しています。ルールに従ってペグを移動し、最後にひとつだけ残ればクリアとなります。ただし、ペグを取り除く位置によって、解けない場合もあるので注意してください。
それでは問題です。図 (2) に示したように、Hoppers の中央のペグを取り除きます。この状態から始めて、最後のペグが中央の位置に残る跳び方の最小手数を求めてください。
それではプログラムを作りましょう。この問題は盤面が小さいので、単純な深さ優先探索で簡単に解くことができます。下図に示すように、盤面のマスに番号をつけます。
┌─┬─┐ ┌─┬─┐
│Ｋ│ │ │０│１│
┌─┼─┼─┼─┐ ┌─┼─┼─┼─┐
│ │ │ │ │ │２│３│４│５│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│ │×│×│ │ │６│×│×│７│
├─┼─┼─┼─┤ ├─┼─┼─┼─┤
│ │ │ │ │ │８│９│10│11│
└─┼─┼─┼─┘ └─┼─┼─┼─┘
│ │ │ │12│13│
└─┴─┘ └─┴─┘
盤面 番号
図 : 盤面と番号の関係
あとは隣接リストを定義して、深さ優先探索で周遊経路を探索するだけです。プログラムは次のようになります。
リスト : 「騎士の周遊」解法プログラム
// 隣接リスト
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 通りしかありません。
┌─┬─┐
│０│７│
┌─┼─┼─┼─┐
│６│11│４│13│
├─┼─┼─┼─┤
│１│×│×│８│
├─┼─┼─┼─┤
│10│５│12│３│
└─┼─┼─┼─┘
│２│９│
└─┴─┘
図 : 周遊経路
「騎士の周遊」は、拙作のページ 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 手になります。
ペグ・ソリテアの場合、ペグの「跳び先表」を用意すると簡単にプログラムできます。座標は次のように定義します。
●───●───● ０───１───２
│＼ ／│＼ ／│ │＼ ／│＼ ／│
│ ● │ ● │ │ ３ │ ４ │
│／ ＼│／ ＼│ │／ ＼│／ ＼│
●───○───● ５───６───７
│＼ ／│＼ ／│ │＼ ／│＼ ／│
│ ● │ ● │ │ ８ │ ９ │
│／ ＼│／ ＼│ │／ ＼│／ ＼│
●───●───● 10───11───12
(1) Hoppers (2) 座標
図 : 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-2024 Makoto Hiroi
//
import dlist._
object puz02 {
//
// 問題１「騎士の周遊」
//
// 隣接リスト
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)
}
}
}
//
// 問題２「水差し問題」
//
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)
}
}
}
//
// 問題３「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
}
}
}
}