●解答１
それではプログラムを作りましょう。式は次のように文字列のリストで表すことにします。
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 => ("1", "+", "2", "+", "3", "-", "4", "+", "5", "+", "6", "+", "78", "+", "9")
あとは、式を生成して値を計算するだけです。次の図を見てください。
(1) => (2 + 1) => (3 + 2 + 1)
=> (3 - 2 + 1)
=> (23 + 1)
=> (2 - 1) => (3 + 2 - 1)
=> (3 - 2 - 1)
=> (21 - 1)
=> (12) => (3 + 12)
=> (3 - 12)
=> (123)
式を生成するとき、リストの先頭に数字と演算子を順番に追加していきます。この場合、数式は逆順になることに注意してください。数字と +, - を追加する処理は簡単です。プログラムのポイントは数字を連結する処理、たとえば 1 と 2 を連結して一つの数値 12 にする処理です。この処理は先頭の数字 1 を 12 ("1" + "2") に置き換えることで実現できます。リストが (2 + 1) であれば、数字 2 を 23 ("2" + "3") に置き換えます。
式を生成するプログラムは次のようになります。
リスト：式の生成
def makeExpr(n: Int, expr: List[String]): Unit = {
if (n == 10) {
val xs = expr.reverse
if (calcExpr(xs.head.toInt, xs.tail) == 100) printExpr(xs)
} else {
val s = n.toString
makeExpr(n + 1, s :: "+" :: expr)
makeExpr(n + 1, s :: "-" :: expr)
makeExpr(n + 1, expr.head + s :: expr.tail)
}
}
makeExpr の引数 n が追加する数字、expr が生成する式 (リスト) です。n が 10 の場合は、式が完成したので値を計算します。expr を reverse で反転して、変数 xs にセットします。そして、関数 calcExpr で式 xs を計算します。値が 100 になれば関数 printExpr で式 xs を出力します。
n が 10 未満であれば、n を expr に追加します。最初に、n をメソッド toString で文字列に変換して変数 s にセットします。次に、コンス演算子で s と "+" を expr に追加して makeExpr を再帰呼び出しします。その次が s と "-" を追加する場合です。最後は文字列を連結する場合です。この場合、リストの先頭要素 expr.head と s を連結し、それを expr.tail の先頭に追加します。とても簡単ですね。
次は式を計算する calcExpr を作ります。今回の問題は演算子に + と - しかないので、リストで表現した式を計算することは簡単です。次のプログラムを見てください。
リスト：式の計算 (+ と - だけ)
def calcExpr(a: Int, xs: List[String]): Int =
xs match {
case Nil => a
case _::Nil => throw new Exception("komachi.calcExpr error")
case op::n::ys => op match {
case "+" => calcExpr(a + n.toInt, ys)
case "-" => calcExpr(a - n.toInt, ys)
case _ => throw new Exception("komachi.calcExpr error")
}
}
calcExpr を呼び出すとき、リストの先頭文字列をメソッド toInt で整数に変換して引数 a に、残りのリストを引数 xs に渡します。calcExpr では、match 式でリストの 2 つの要素 op と n を取り出します。op は "+" または "-" で、n が数字になります。
それから、op を match 式でチェックして、"+" ならば a に n を加算して calcExpr を再帰呼び出しします。"-" なら n を減算して再帰呼び出しします。xs が Nil ならば a の値を返します。
このように、正解の可能性があるデータを作りそれをチェックするという方法を「生成検定法 (generate and test)」といいます。可能性のあるデータをもれなく作るのに、バックトラック法は最適です。ただし、「生成するデータ数が多くなると時間がとてもかかる」という弱点があるので注意してください。
あとのプログラムは簡単なので説明は割愛します。詳細は プログラムリスト１ をお読みください。
それでは実行結果を示します。
$ scalac komachi.scala
$ scala komachi
1+2+3-4+5+6+78+9=100
1+2+34-5+67-8+9=100
1+23-4+5+6+78-9=100
1+23-4+56+7+8+9=100
12+3+4+5-6-7+89=100
12+3-4+5+67+8+9=100
12-3-4+5-6+7+89=100
123+4-5+67-89=100
123+45-67+8-9=100
123-4-5-6-7+8-9=100
123-45-67+89=100
全部で 11 通りの解が出力されます。
ところで、今回のプログラムは数式を List[String] で表したので、文字列と数値の変換が必要になりました。数値と演算子を別々のリスト (List[Int] と List[String]) に格納すると、このような処理は不要になります。興味のある方は 別解 をお読みください。
●プログラムリスト１
//
// komachi.scala : パズル「小町算」の解法
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
object komachi {
// 式の計算
def calcExpr(a: Int, xs: List[String]): Int =
xs match {
case Nil => a
case _::Nil => throw new Exception("komachi.calcExpr error")
case op::n::ys => op match {
case "+" => calcExpr(a + n.toInt, ys)
case "-" => calcExpr(a - n.toInt, ys)
case _ => throw new Exception("komachi.calcExpr op error")
}
}
// 式の表示
def printExpr(xs: List[String]): Unit = {
for (x <- xs) print(x)
println("=100")
}
// 式の生成
def makeExpr(n: Int, expr: List[String]): Unit = {
if (n == 10) {
val xs = expr.reverse
if (calcExpr(xs.head.toInt, xs.tail) == 100) printExpr(xs)
} else {
val s = n.toString
makeExpr(n + 1, s :: "+" :: expr)
makeExpr(n + 1, s :: "-" :: expr)
makeExpr(n + 1, expr.head + s :: expr.tail)
}
}
def main(args: Array[String]): Unit = {
makeExpr(2, List("1"))
}
}
●別解
//
// komachi1.scala : パズル「小町算」の解法
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
object komachi1 {
// 式の表示
def printExpr(nums: List[Int], ops: List[String]): Unit = {
(nums, ops) match {
case (x::Nil, Nil) => println(s"$x=100")
case (x::xs, y::ys) => { print(s"$x$y"); printExpr(xs, ys) }
case _ => throw new Exception("puz01.printExpr error")
}
}
// 式の計算
def calcExpr(a: Int, nums: List[Int], ops: List[String]): Int =
(nums, ops) match {
case (Nil, Nil) => a
case (x::xs, y::ys) => y match {
case "+" => calcExpr(a + x, xs, ys)
case "-" => calcExpr(a - x, xs, ys)
case _ => throw new Exception("komachi1.calcExpr op error")
}
case _ => throw new Exception("komachi1.calcExpr expr error")
}
// 式の表示
def makeExpr(n: Int, nums: List[Int], ops: List[String]): Unit = {
if (n == 10) {
val xs = nums.reverse
val ys = ops.reverse
if (calcExpr(xs.head, xs.tail, ys) == 100) printExpr(xs, ys)
} else {
makeExpr(n + 1, n :: nums, "+" :: ops)
makeExpr(n + 1, n :: nums, "-" :: ops)
makeExpr(n + 1, (nums.head * 10 + n) :: nums.tail, ops)
}
}
def main(args: Array[String]): Unit = {
makeExpr(2, List(1), Nil)
}
}
●解答２
式 SEND + MORE = MONEY は足し算なので、M が 1 であることはすぐにわかります。ここでは、それ以外の数字を求めるプログラムを作ります。次のリストを見てください。
//
// hukumen.scala : send + more = money
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
object hukumen {
// 順列の生成
def permutations(f: List[Int] => Unit, n: Int, xs: List[Int], a: List[Int]): Unit =
if (n == 0)
f(a.reverse)
else
xs.foreach((x: Int) => permutations(f, n - 1, xs.filter(_ != x), x::a))
// チェック
def check(xs: List[Int]): Unit = xs match {
case s::e::n::d::o::r::y::Nil => {
val send = s * 1000 + e * 100 + n * 10 + d
val more = 1000 + o * 100 + r * 10 + e
val money = 10000 + o * 1000 + n * 100 + e * 10 + y
if (send + more == money) println(s"$send + $more = $money")
}
case _ => throw new Exception("hukumen error")
}
def main(args: Array[String]): Unit = {
permutations(check, 7, List(0, 2, 3, 4, 5, 6, 7, 8, 9), Nil)
}
}
permutations はリスト xs から n 個の要素を選ぶ順列を生成します。順列の生成は拙作のページ 順列と組み合わせ で作成したプログラムとほぼ同じです。あとは関数 check で数値 send, more, money を計算して、send + more = money を満たしているかチェックします。とても簡単なプログラムですね。さっそく実行してみましょう。
$ scalac hukumen.scala
$ scala hukumen
9567 + 1085 = 10652
答えは 9567 + 1085 = 10652 の 1 通りしかありません。興味のある方は、ほかの方法でも試してみてください。
●解答３
3 行 3 列の魔方陣も順列を生成するプログラムを使って簡単に解くことができます。次のリストを見てください。
//
// mahou.scala : 魔方陣
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
object mahou {
// 順列の生成
def permutations(f: List[Int] => Unit, n: Int, xs: List[Int], a: List[Int]): Unit =
if (n == 0)
f(a.reverse)
else
xs.foreach((x: Int) => permutations(f, n - 1, xs.filter(_ != x), x::a))
// 直線
val lines: List[List[Int]] = List(
List(0, 1, 2), List(3, 4, 5), List(6, 7, 8), List(0, 3, 6),
List(1, 4, 7), List(2, 5, 8), List(0, 4, 8), List(2, 4, 6))
// チェック
def checkMahoujin(xs: List[Int]): Unit = {
def sum(ys: List[Int]): Int =
ys.foldLeft(0)((a: Int, y: Int) => a + xs(y))
val ys = lines.map(sum)
if (ys.tail.forall(_ == ys.head)) println(xs)
}
def main(args: Array[String]): Unit = {
permutations(checkMahoujin, 9, List(1,2,3,4,5,6,7,8,9), Nil)
}
}
関数 permutations で順列を生成します。それを関数 checkMahoujin に渡して、魔方陣の条件を満たしているかチェックします。局所関数 sum で各直線の和を求めて、すべて同じ値かメソッド forall でチェックします。すべて同じ数字であれば魔方陣の条件を満たすので、println で盤面 xs を表示します。
forall はリストの要素に関数を適用し、その結果がすべて真であれば forall は真を返します。簡単な使用例を示します。
scala> List(2, 4, 6, 8, 10).forall(_ % 2 == 0)
val res0: Boolean = true
scala> List(2, 4, 6, 8, 10, 11).forall(_ % 2 == 0)
val res1: Boolean = false
最初の例はすべて偶数なので、forall は真を返します。次の例は奇数 (11) が一つ含まれているので偽を返します。
それでは実行結果を示します。
$ scalac mahou.scala
$ scala mahou
List(2, 7, 6, 9, 5, 1, 4, 3, 8)
List(2, 9, 4, 7, 5, 3, 6, 1, 8)
List(4, 3, 8, 9, 5, 1, 2, 7, 6)
List(4, 9, 2, 3, 5, 7, 8, 1, 6)
List(6, 1, 8, 7, 5, 3, 2, 9, 4)
List(6, 7, 2, 1, 5, 9, 8, 3, 4)
List(8, 1, 6, 3, 5, 7, 4, 9, 2)
List(8, 3, 4, 1, 5, 9, 6, 7, 2)
対称解を含めると、解は 8 通りあります。最近のパソコンはハイスペックなので、このままでも高速に解けるのですが、対称解を排除すると枝刈りの効果により、実行時間はもう少し速くなります。
●対称解の排除
対称解のチェックは、下図のように四隅の大小関係を利用すると簡単です。
図 : 対称解のチェック
魔方陣の場合、回転解が 4 種類あって、鏡像解が 2 種類あります。四隅の大小関係をチェックすることで、これらの対称解を排除することができます。また、早い段階で枝刈りを行うため、盤面の番号と試行順序を工夫します。
試行順序を上図のように定義し、スライスの添字と対応させます。そうすると、最初に四隅 (0, 1, 2, 3) の数字が選択されますね。ここで対称解のチェックが行われるので、枝刈りの効率は良くなります。プログラムは次のようになります。
//
// mahou1.scala : 魔方陣
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
object mahou1 {
// 直線
val lines: List[List[Int]] = List(
List(0, 4, 1), List(5, 8, 6), List(2, 7, 3), List(0, 5, 2),
List(4, 8, 7), List(1, 6, 3), List(0, 8, 3), List(1, 8, 2))
// 盤面の表示
def printBoard(board: Array[Int]): Unit = {
println(s"${board(0)} ${board(4)} ${board(1)}")
println(s"${board(5)} ${board(8)} ${board(6)}")
println(s"${board(2)} ${board(7)} ${board(3)}")
}
// チェック
def checkMahouSub(board: Array[Int]): Unit = {
def sum(ys: List[Int]): Int =
ys.foldLeft(0)((a: Int, y: Int) => a + board(y))
val ys = lines.map(sum)
if (ys.tail.forall(_ == ys.head)) printBoard(board)
}
// 順列の生成
def mahouSub(n: Int, board: Array[Int], used: Array[Boolean]): Unit = {
def check(n: Int): Boolean =
n match {
case 1 if (board(0) > board(1)) => false
case 2 if (board(1) > board(2)) => false
case 3 if (board(0) > board(3)) => false
case _ => true
}
if (n == 9) {
checkMahouSub(board)
} else {
for (x <- 1 to 9) {
if (!used(x)) {
board(n) = x
if (check(n)) {
used(x) = true
mahouSub(n + 1, board, used)
used(x) = false
}
}
}
}
}
def main(args: Array[String]): Unit = {
mahouSub(0, new Array[Int](9), new Array[Boolean](10))
}
}
関数 mahouSub は配列を使って順列を生成します。引数 n は選んだ数字の個数を表します。引数 board が盤面を表す配列で、ここに数字を書き込みます。引数 used は Boolean 型の配列で、数字 x を選んだ場合は used(x) を true に書き換えます。局所関数 check は対称解のチェックを行います。n が 1 の場合、board(0) > board(1) ならば false を返します。n が 2 と 3 の場合も同様にチェックします。それ以外は true を返します。
本体の処理は簡単で、n が 9 ならばすべての数字を選んだので魔方陣のチェックを行います。そうでなければ、for ループで数字を選びます。used(x) が false であれば、x を選ぶことができます。board(n) に x をセットして、check で対称解のチェックを行います。それを満たしていれば、used(x) に true をセットして、mahouSub を再帰呼び出しします。戻ってきたら used(x) を false に戻します。
あとのプログラムは簡単なので説明を割愛します。詳細はプログラムリストをお読みください。
実行結果を示します。
$ scalac mahou1.scala
$ scala mahou1
2 9 4
7 5 3
6 1 8
●解答４
このゲームは 10 個の数字の中から 4 個選ぶわけですから、全体では 10 * 9 * 8 * 7 = 5040 通りのコードしかありません。この中から正解を見つける方法ですが、質問したコードとその結果を覚えておいて、それと矛盾しないコードを作るようにします。具体的には、4 つの数字の順列を生成し、それが今まで質問したコードと矛盾しないことを確かめます。これは生成検定法と同じですね。
矛盾しているかチェックする方法も簡単で、以前に質問したコードと比較して、bulls と cows が等しいときは矛盾していません。たとえば、次の例を考えてみてください。
[6 2 8 1] が正解の場合
[0 1 2 3] => bulls = 0, cows = 2
[0 1 2 3] と比較する
--------------------------------------------------------
[0 X X X] 0 から始まるコードは bulls = 1
になるので矛盾する。
・・・・
[1 0 3 4] cows = 3, bulls = 0 になるので矛盾する
・・・・
[1 0 4 5] cows = 2, bulls = 0 で矛盾しない。
--------------------------------------------------------
[1 0 4 5] => bulls = 0, cows = 1
次は、[0 1 2 3] と [1 0 4 5] に矛盾しない数字を選ぶ
図 : マスターマインドの推測アルゴリズム
[0 1 2 3] で bulls が 0 ですから、その位置にその数字は当てはまりません。したがって、[0 X X X] というコードは [0 1 2 3] と比較すると bulls が 1 となるので、矛盾していることがわかります。
次に [1 0 3 4] というコードを考えてみます。[0 1 2 3] の結果は cows が 2 ですから、その中で合っている数字は 2 つしかないわけです。ところが、[1 0 3 4] と [0 1 2 3] と比較すると cows が 3 になります。当たっている数字が 2 つしかないのに、同じ数字を 3 つ使うのでは矛盾していることになりますね。
次に [1 0 4 5] というコードと比較すると、bulls が 0 で cows が 2 となります。これは矛盾していないので、このコードを質問することにします。その結果が bulls = 0, cows = 1 となり、今度は [0 1 2 3] と [1 0 4 5] に矛盾しないコードを選択するのです。
●プログラムの作成
それでは、プログラムを作りましょう。まず、質問したコードとその結果を格納する型を定義します。今回はタプルに格納することにしましょう。型名が長くなるので、短い名前を付けることができると便利です。Scala の場合、type でデータ型に別名を付けることができます。
type 名前 = 型
type のあとに名前を書き、= のあとに既存の型を書きます。これで型を短い名前で表すことができます。プログラムは次のようになります。
リスト : 型の定義
type Query = (List[Int], Int, Int)
型名は Query としました。最初の要素が質問したコードで、2 番目の要素が bulls の個数、3 番目の要素が cows の個数を表します。
次は bulls を数える関数 countBulls を作ります。
リスト : bulls を数える
def countBulls(xs: List[Int], ys: List[Int]): Int =
xs.zip(ys).count((p: (Int, Int)) => p._1 == p._2)
メソッド zip はリスト xs, ys の要素をタプルに格納して、それをリストに格納して返します。メソッド count は引数の述語が真を返す要素の個数を求めます。Common Lisp の関数 count-if と同じです。簡単な使用例を示しましょう。
scala> List(1,2,3).zip(List(4,5,6))
val res0: List[(Int, Int)] = List((1,4), (2,5), (3,6))
scala> List(1,2,3,4,5).count(_ % 2 == 0)
val res1: Int = 2
scala> List(1,2,3,4,5).count(_ % 2 != 0)
val res2: Int = 3
countBulls はリスト xs, ys の要素を zip でまとめて、タプルの 2 要素が等しい個数を count で求めます。
次は cows を数える処理を作ります。いきなり cows を数えようとすると難しいのですが、2 つのリストに共通の数字を数えることは簡単にできます。この方法では、bulls の個数を含んだ数を求めることになりますが、そこから bulls を引けば cows を求めることができます。関数名は countSameNumber としましょう。プログラムは次のようになります。
リスト : 同じ数字の個数を数える
def countSameNumber(xs: List[Int], ys: List[Int]): Int =
xs.count(ys contains _)
メソッド count に ys contains _ を渡して呼び出せば同じ数字の個数を求めることができます。
次は、今まで質問したコードと矛盾していないか調べる関数 checkQuery を作ります。
リスト : 今まで質問したコードと矛盾していないか
def checkQuery(xs: List[Int], query: List[Query]): Boolean = {
for ((ys, bulls, cows) <- query) {
val b = countBulls(xs, ys)
val c = countSameNumber(xs, ys) - b
if (b != bulls || c != cows) return false
}
true
}
引数 xs が質問したコード、query が今まで質問した Query を格納したリストです。すべてのデータで矛盾がなければ true を返します。関数 countBulls と countSameNumber を使って bulls (変数 b) と cows (変数 c) を求めて、質問したときの bulls と cows に矛盾しないかチェックします。
次はマスターマインドを解く関数 solver を作ります。
リスト : マスターマインドの解法
def solver(answer: List[Int], query: List[Query], code: List[List[Int]]): List[Query] =
code match {
case Nil => Nil
case xs::xcode => {
if (checkQuery(xs, query)) {
val bulls = countBulls(answer, xs)
val cows = countSameNumber(answer, xs) - bulls
val qs = (xs, bulls, cows)::query
if (bulls == 4) qs.reverse
else solver(answer, qs, xcode)
} else {
solver(answer, query, xcode)
}
}
}
引数 answer が正解のコード、query は今まで質問したコードと結果を格納したリスト、code が質問するコードを格納したリストです。質問するコードを code から一つ取り出し、checkQuery で矛盾していなかチェックします。そうであれば、bulls と cows を求めて、その結果を query の先頭に追加して変数 qs にセットします。もし、bulls が 4 であれば、答えを求めることができました。reverse で qs を反転して返します。そうでなければ、solver を再帰呼び出しして次に質問するコードを選択します。
最後に main 関数を作ります。
リスト : main 関数
ef main(args: Array[String]): Unit = {
val code = permutations2(4, Range(0, 10).toList)
solver(List(9, 4, 3, 1), Nil, code).foreach(println)
// 平均質問回数を求める
var c = 0.0
for (xs <- code) {
c += solver(xs, Nil, code).length
}
println(c / 5040.0)
}
permutations2 で順列を生成して変数 code にセットします。(9, 4, 3, 1) を解く場合は、それを solver に渡して、foreach で返り値 (リスト) の要素を println で表示します。
5040 通りのコードすべて試してみることもできます。code から順番に正解のコードを取り出して solver に渡します。そして、変数 c に質問した回数を加算します。あとは c / 5040.0 を計算すれば、平均質問回数を求めることができます。
●何回で当たるか
これでプログラムは完成です。それでは実行例を示しましょう。
$ scalac master.scala
$ scala master
(List(0, 1, 2, 3),0,2)
(List(1, 0, 4, 5),0,2)
(List(2, 3, 5, 4),0,2)
(List(3, 4, 0, 6),1,1)
(List(3, 5, 6, 1),1,1)
(List(6, 5, 0, 2),0,0)
(List(7, 4, 3, 1),3,0)
(List(8, 4, 3, 1),3,0)
(List(9, 4, 3, 1),4,0)
5.56031746031746
肝心の質問回数ですが、5, 6 回で当たる場合が多いようです。平均質問回数は 5.56 回になりました。これは 参考文献 [1] の結果と同じです。質問回数の最大値は 9 回で、そのときのコードは (9, 4, 3, 1), (9, 2, 4, 1), (5, 2, 9, 3), (9, 2, 0, 4), (9, 2, 1, 4) でした。
なお、参考文献 [1] には平均質問回数がこれよりも少なくなる方法が紹介されています。単純な数当てゲームだと思っていましたが、その奥はけっこう深いようです。興味のある方はいろいろ試してみてください。
●参考文献
- 田中哲郎 「数当てゲーム (MOO, マスターマインド)」, 松原仁、竹内郁雄 編 『bit 別冊 ゲームプログラミング』 pp150 - 157, 共立出版, 1997
●プログラムリスト
//
// master.scala : マスターマインド
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
object master {
// 順列の生成
def permutations2[A](n: Int, xs: List[A]): List[List[A]] =
(n, xs) match {
case (0, _) => List(Nil)
case _ => {
for (x <- xs;
ys <- permutations2(n - 1, xs.filterNot(x == _))) yield x::ys
}
}
// bulls を求める
def countBulls(xs: List[Int], ys: List[Int]): Int =
xs.zip(ys).count((p: (Int, Int)) => p._1 == p._2)
// 同じ数字の個数を求める
def countSameNumber(xs: List[Int], ys: List[Int]): Int =
xs.count(ys contains _)
// 型の定義
type Query = (List[Int], Int, Int)
// 矛盾しているか
def checkQuery(xs: List[Int], query: List[Query]): Boolean = {
for ((ys, bulls, cows) <- query) {
val b = countBulls(xs, ys)
val c = countSameNumber(xs, ys) - b
if (b != bulls || c != cows) return false
}
true
}
// マスターマインドの解法
def solver(answer: List[Int], query: List[Query], code: List[List[Int]]): List[Query] =
code match {
case Nil => Nil
case xs::xcode => {
if (checkQuery(xs, query)) {
val bulls = countBulls(answer, xs)
val cows = countSameNumber(answer, xs) - bulls
val qs = (xs, bulls, cows)::query
if (bulls == 4) qs.reverse
else solver(answer, qs, xcode)
} else {
solver(answer, query, xcode)
}
}
}
def main(args: Array[String]): Unit = {
val code = permutations2(4, Range(0, 10).toList)
solver(List(9, 4, 3, 1), Nil, code).foreach(println)
// 平均質問回数を求める
var c = 0.0
for (xs <- code) {
c += solver(xs, Nil, code).length
}
println(c / 5040.0)
}
}
初版 2014 年 8 月 9 日
改訂 2021 年 4 月 4 日
図 : 魔方陣
