パズルの解法を題材にした簡単な Ruby のサンプルプログラムです。
1 から 9 までの数字を順番に並べ、間に + と - を補って 100 になる式を作ってください。ただし、1 の先頭に - 符号はつけないことにします。
例 : 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
パズルの世界では、1 から 9 までの数字を 1 個ずつすべて使った数字を「小町数」といいます。たとえば、123456789 とか 321654987 のような数字です。「小町算」というものもあり、たとえば 123 + 456 + 789 とか 321 * 654 + 987 のようなものです。この問題は小町算の中でも特に有名なパズルです。
詳しい説明は拙作のページ「Puzzle DE Programming: 数字のパズル」の「式の値が 100 になる小町算」をお読みくださいませ。
リスト : 小町算
#
# 式を文字列で表す (eval で評価)
#
def komachi(n, expr, ans)
if n == 10
if eval(expr) == ans
print expr, " = ", ans, "\n"
end
else
komachi(n + 1, expr + " + " + n.to_s, ans)
komachi(n + 1, expr + " - " + n.to_s, ans)
komachi(n + 1, expr + n.to_s, ans)
end
end
def komachi_solver1(ans)
komachi(2, "1", ans)
end
#
# 式を配列で表す
#
# 式の表示
def print_expr(expr, ans)
expr.each do |x| print x, " " end
print '= ', ans, "\n"
end
# 式の計算
def calc_expr(expr)
a = expr[0]
i = 1
while i < expr.size
case expr[i]
when "+"
a += expr[i + 1]
when "-"
a -= expr[i + 1]
end
i += 2
end
a
end
# 式の生成
def make_expr(n, expr, ans)
if n == 10
print_expr(expr, ans) if calc_expr(expr) == ans
else
make_expr(n + 1, expr + ["+", n], ans)
make_expr(n + 1, expr + ["-", n], ans)
save = expr[-1]
expr[-1] = expr[-1] * 10 + n
make_expr(n + 1, expr, ans)
expr[-1] = save
end
end
def komachi_solver2(ans)
make_expr(2, [1], ans)
end
irb> komachi_solver1 100 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 => nil irb> komachi_solver2 100 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 => 1
騎士 (ナイト) はチェスの駒のひとつで将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。
┌─┬─┬─┬─┬─┐
│ │●│ │●│ │
├─┼─┼─┼─┼─┤ ┌─┬─┬─┐
│●│ │ │ │●│ │Ｋ│ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┤
│ │ │Ｋ│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┤
│●│ │ │ │●│ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┤
│ │●│ │●│ │ │ │ │ │
└─┴─┴─┴─┴─┘ └─┴─┴─┘
●：ナイト (K) が動ける位置 問題
図 : ナイトの巡歴
このナイトを動かして、N 行 M 列の盤面のどのマスにもちょうど一回ずつ訪れるような経路を求めるのが問題です。ちなみに、3 行 3 列、4 行 4 列の盤面には解がありませんが、5 行 5 列の盤面には解があります。大きな盤面を解くのは大変なので、3 行 4 列の盤面でナイトの移動経路を求めてください。プログラムを作る前に自分で考えてみるのも面白いでしょう。
┌─┬─┬─┐
│０│１│２│ ０──７──２
├─┼─┼─┤ │ │
│３│４│５│ ５──10──３
├─┼─┼─┤ │ │
│６│７│８│ ６──１──８
├─┼─┼─┤ │ │
│９│10│11│ 11──４──９
└─┴─┴─┘
（Ａ）盤面 （Ｂ）騎士の移動
図 : 盤面と騎士の移動
図 (A) のように、3 行 4 列盤の各マスに番号をつけて表します。すると、ナイトの移動は (B) のようにグラフで表すことができます。これならばコンピュータを使わなくても解くことができますね。プログラムも隣接リストを定義すれば簡単です。次のリストを見てください。
リスト : 騎士の巡歴
# 隣接リスト
$adjacent = [
[5, 7], # 0
[6, 8], # 1
[3, 7], # 2
[2, 8, 10], # 3
[9, 11], # 4
[0, 6, 10], # 5
[1, 5, 11], # 6
[0, 2], # 7
[1, 3, 9], # 8
[4, 8], # 9
[3, 5], # 10
[4, 6] # 11
]
# 深さ優先探索
def knight_tour(n = 1, path = [0])
if n == 12
print path, "\n"
else
for x in $adjacent[path[-1]]
next if path.member? x
path.push x
knight_tour n + 1, path
path.pop
end
end
end
隣接リストは大域変数 $adjacent に定義します。あとは単純な深さ優先探索で解を探します。関数 knight_tour() の引数 n が手数で、path が経路を表す配列です。末尾の要素が現在地点になります。
n が 12 になったら、すべての地点を訪問したので print() で path を表示します。そうでなければ、隣接リストから次の訪問先を求めて変数 x にセットします。x が path に含まれていなければ、x を path に追加して knight_tour() を再帰呼び出しします。戻ってきたら、path から x を削除することをお忘れなく。
irb> knight_tour [0, 7, 2, 3, 10, 5, 6, 1, 8, 9, 4, 11] [0, 7, 2, 3, 10, 5, 6, 11, 4, 9, 8, 1] => [5, 7]
2 通りの経路を見つけることができました。このプログラムでは隣接リストを使いましたが、盤面を二次元配列で表しても簡単にプログラムすることができるでしょう。
┌─┬─┬─┐ 式
│Ａ│Ｂ│Ｃ│ A + B + C = N, A + E + I = N
├─┼─┼─┤ D + E + F = N, C + E + G = N
│Ｄ│Ｅ│Ｆ│ G + H + I = N
├─┼─┼─┤ A + D + G = N
│Ｇ│Ｈ│Ｉ│ B + E + H = N
└─┴─┴─┘ C + F + I = N
図 : 魔方陣
上図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。縦横斜めの合計が等しくなるように数字を配置してください。
3 行 3 列の魔方陣は生成検定法で簡単に解くことができます。
リスト : 魔方陣 (3 行 3 列盤)
# 盤面
# 0 1 2
# 3 4 5
# 6 7 8
# 直線を表す配列
$lines = [
[0, 1, 2], [3, 4, 5], [6, 7, 8],
[0, 3, 6], [1, 4, 7], [2, 5, 8],
[0, 4, 8], [2, 4, 6]
]
def sum_line(board, a, b, c)
board[a] + board[b] + board[c]
end
def check(board)
xs = $lines.map {|ls| sum_line(board, *ls)}
xs.count(xs[0]) == xs.size
end
def print_board(board)
for i in 0..8
print board[i], " "
print "\n" if (i + 1) % 3 == 0
end
print "\n"
end
def magic_square()
(1..9).to_a.permutation do |board|
print_board(board) if check(board)
end
end
関数 magic_square() はメソッド permutation() で 1 から 9 までの数字の順列を生成します。それを関数 check() に渡して、魔方陣の条件を満たしているかチェックします。map() で各直線の和を求めて、すべて同じ値であれば魔方陣の条件を満たすので true を返します。
メソッド count() は、引数と等しい要素の個数を返します。先頭要素と同じ値が 8 個あれば、すべての要素が等しいことがわかります。条件を満たしていたら print_board() で盤面を表示します。
irb> s = Time.now; magic_square; Time.now - s 2 7 6 9 5 1 4 3 8 2 9 4 7 5 3 6 1 8 4 3 8 9 5 1 2 7 6 4 9 2 3 5 7 8 1 6 6 1 8 7 5 3 2 9 4 6 7 2 1 5 9 8 3 4 8 1 6 3 5 7 4 9 2 8 3 4 1 5 9 6 7 2 => 0.726876909 実行環境 : Ruby 3.0, Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz
対称解を含めると、解は 8 通りあります。対称解を排除すると枝刈りの効果により、実行時間はもう少し速くなります。
対称解のチェックは、下図のように四隅の大小関係を利用すると簡単です。
┌─┬─┬─┐
│Ａ│Ｂ│Ｃ│
├─┼─┼─┤ A < C < G
│Ｄ│Ｅ│Ｆ│
├─┼─┼─┤ A < I
│Ｇ│Ｈ│Ｉ│
└─┴─┴─┘
図 : 対称解のチェック
魔方陣の場合、回転解が 4 種類あって、鏡像解が 2 種類あります。四隅の大小関係をチェックすることで、これらの対称解を排除することができます。プログラムは次のようになります。
リスト : 対称解の排除
def magic_square1(board = [])
if board.size == 9
print_board(board) if check(board)
else
for n in 1..9
next if board.member? n
next if board.size == 2 && board[0] > n
next if board.size == 6 && board[2] > n
next if board.size == 8 && board[0] > n
board.push n
magic_square1 board
board.pop
end
end
end
順列を生成する magic_square1() の中で四隅の大小関係をチェックします。条件を満たしていなければ magic_square1() を再帰呼び出ししません。これで枝刈りを行うことができます。実行結果を示します。
irb> s = Time.now; magic_square1; Time.now - s 2 9 4 7 5 3 6 1 8 => 0.661712937
対称解を除くと解は 1 通りしかありません。Ruby のメソッド permutation() は速いので、自分で順列を生成するプログラムを作ると遅くなります。枝刈りを入れたとしても、実行時間はそれほど速くなりませんでした。
ライツアウトは光っているボタンをすべて消すことが目的のパズルです。ルールはとても簡単です。あるボタンを押すと、そのボタンと上下左右のボタンの状態が反転します。つまり、光っているボタンは消灯し消えていたボタンは点灯します。次の図を見てください。
□□□□□ □□□□□ ０ １ ２ ３ ４
□□□□□ □□■□□ ５ ６ ７ ８ ９
□□□□□ ─→ □■■■□ 10 11 12 13 14
□□□□□ □□■□□ 15 16 17 18 19
□□□□□ □□□□□ 20 21 22 23 24
（Ａ）中央のボタンを押した場合 （Ｂ）座標
図 : ライツアウトの点灯パターン
ボタンは 5 行 5 列に配置されています。上図に示したように、中央のボタン 12 を押すとそのボタンと上下左右のボタンの状態が反転します。
パズルの詳しい説明は拙作のページ「Puzzle DE Programming: ライツアウトの解法」をお読みくださいませ。
最初は単純な生成検定法でプログラムを作りましょう。25 個のボタンから i 個を選ぶ組み合わせを求め、選んだボタンを押してライトがすべて消えるかチェックします。これをそのままプログラムすると次のようになります。
リスト : ライツアウトの解法 (単純な生成検定法)
# 押すボタンのパターン
$pattern = [
0x0000023, 0x0000047, 0x000008e, 0x000011c, 0x0000218,
0x0000461, 0x00008e2, 0x00011c4, 0x0002388, 0x0004310,
0x0008c20, 0x0011c40, 0x0023880, 0x0047100, 0x0086200,
0x0118400, 0x0238800, 0x0471000, 0x08e2000, 0x10c4000,
0x0308000, 0x0710000, 0x0e20000, 0x1c40000, 0x1880000
]
# 解の表示
def print_answer_lo(xs)
for i in 0..24
if xs.member? i
print 'O '
else
print '. '
end
print "\n" if (i + 1) % 5 == 0
end
print "\n"
end
# ボタンを押す
def push_button(board, xs)
xs.reduce(board) do |a, x| a ^ $pattern[x] end
end
# ライツアウトの解法
def solver_lo(board)
for i in 1..25
print '-----', i, '-----', "\n"
(0..24).to_a.combination(i) do |xs|
if push_button(board, xs) == 0
print_answer_lo(xs)
return
end
end
end
end
ボタンの状態をビットで表すと、盤面は 0 から #x1ffffff までの整数値で表すことができます。配列 $pattern は、ボタンを押したときに状態が変わる位置をビットで示したものです。この値とボタンの状態の排他的論理和 (xor) を取ると、ボタンの状態を反転させることができます。
関数 push_button() は選んだボタンを押した盤面を返します。関数 solver_lo() は簡単です。for ループで選ぶボタンの個数 i を 1 から 25 まで順番に増やしていき、combination() で組み合わせを生成して、push_button() でボタンを押して全部消えるかチェックするだけです。
それでは、ボタンが全部点灯しているときの解を求めてみましょう。
irb> s = Time.now; solver_lo(0x1ffffff); Time.now - s -----1----- -----2----- -----3----- -----4----- -----5----- -----6----- -----7----- -----8----- -----9----- -----10----- -----11----- -----12----- -----13----- -----14----- -----15----- O O . . . O O . O O . . O O O . O O O . . O O . O => 45.987224112 実行環境: Ruby 3.0, Ubuntu 22.04 LTS (WSL2), Intel Core i5-6200U 2.30GHz です。
最短手数は 15 手で、O が押すボタンの位置です。実行時間は約 46 秒かかりました。けっこう時間がかかりますね。実は、もっと高速に解く方法があるのです。
下図を見てください。
ＡＢＣＤＥ ＡＢＣＤＥ ＡＢＣＤＥ ＡＢＣＤＥ
１□■□■□ １□□□□□ １□□□□□ １□□□□□
２□□□□□ ２■■□■■ ２□□□□□ ２□□□□□
３□□□□□ ３□■□■□ ３□■□■□ ３□□□□□
４□□□□□ ４□□□□□ ４■■□■■ ４□□□□□
５□□□□□ ５□□□□□ ５□□□□□ ５□■□■□
（１） （２） （３） （４）
図 : 1 行ずつボタンを消灯していく方法
(1) では、1 行目のボタンが 2 つ点灯しています。このボタンを消すには、真下にある 2 行目の B と D のボタンを押せばいいですね。すると (2) の状態になります。次に、2 行目のボタンを消します。3 行目の A, B, D, E のボタンを押して (3) の状態になります。
あとはこれを繰り返して 4 行目までのボタンを消したときに、5 行目のボタンも全部消えていれば成功となります。(4) のように、5 行目のボタンが消えない場合は失敗です。この場合は、1 行目のボタンを押して、点灯パターンを変更します。
2 - 5 行目のボタンの押し方は、1 行目の点灯パターンにより決定されるので、けっきょく 1 行目のボタンの押し方により、解けるか否かが決まります。この場合、ボタンの押し方は、2 ^ 5 = 32 通りしかありせん。つまり、たった 32 通り調べるだけでライツアウトの解を求めることができるのです。
それでは、32 通りをチェックするプログラムを作りましょう。
リスト : ライツアウトの解法 (高速版)
def solver_lo_fast(board)
for i in 0..5
(0..4).to_a.combination(i) do |xs|
b = push_button(board, xs)
for j in 5..24
if b[j - 5] == 1
b ^= $pattern[j]
xs.push j
end
end
print_answer_lo(xs) if b == 0
end
end
end
最初の for ループで押すボタンの個数 i を 0 から 5 まで増やしていき、combination() で押すボタンの組み合わせを生成します。次の for ループで、2 行目から 5 行目のボタンを押して、全部消えるかチェックします。変数 j が押すボタンの位置を表しています。上のボタンの位置は j - 5 で求めることができます。j - 5 番目のボタンが点灯していたならば j 番目のボタンを押します。このとき、押したボタンの位置を配列 xs に追加することをお忘れなく。最後にボタンが全部消えているかチェックします。そうであれば print_answer_lo() で解を出力します。
プログラムはこれで完成です。さっそく試してみましょう。
irb> s = Time.now; solver_lo_fast(0x1ffffff); Time.now - s O O . . . O O . O O . . O O O . O O O . . O O . O . . . O O O O . O O O O O . . . O O O . O . O O . O . O O . . O O O . O O O . . O O . O O . . . O O . O O . O . O O O . . . O O O O O . O O O O . . . => 0.003841298
一瞬で答えを求めることができました。
8 クイーンは 8 行 8 列のチェスの升目に 8 個のクイーンを互いの利き筋が重ならないように配置する問題です。これはコンピュータに解かせるパズルの中でもとくに有名な問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を次に示します。
*-----------------* | Q . . . . . . . | | . . . . Q . . . | | . . . . . . . Q | | . . . . . Q . . | | . . Q . . . . . | | . . . . . . Q . | | . Q . . . . . . | | . . . Q . . . . | *-----------------* 図 : 8 クイーンの解答例
パズルの詳しい説明は拙作のページ「Puzzle DE Programming: N Queens Problem」をお読みくださいませ。
単純な生成検定法でプログラムを作ると次のようになります。
リスト : ８クイーンの解法
# 解の表示
def print_queen_line(q, size)
print "| "
for i in 0 ... size
if i == q
print "Q "
else
print ". "
end
end
print "|\n"
end
def print_queen(board)
n = board.size
print "*-", "--" * n, "*\n"
board.each do |x|
print_queen_line(x, n)
end
print "*-", "--" * n, "*\n"
end
# 衝突のチェック
def conflict(board, y, x)
for x1 in 0 ... x
y1 = board[x1]
return true if (x1 - y1 == x - y) || (x1 + y1 == x + y)
end
false
end
# 安全確認
def is_safe(board)
for x in 0 ... board.size
return false if conflict(board, board[x], x)
end
true
end
def nqueen_solver(n)
(0...n).to_a.permutation do |board|
print_queen(board) if is_safe(board)
end
end
# 時間計測
def nqueen_solver_count(n)
cnt = 0
s = Time.now
(0...n).to_a.permutation do |board|
cnt += 1 if is_safe(board)
end
print cnt, " ", Time.now - s, "\n"
end
irb> nqueen_solver(4) *---------* | . Q . . | | . . . Q | | Q . . . | | . . Q . | *---------* *---------* | . . Q . | | Q . . . | | . . . Q | | . Q . . | *---------* => [0, 1, 2, 3] irb> nqueen_solver(8) *-----------------* | Q . . . . . . . | | . . . . Q . . . | | . . . . . . . Q | | . . . . . Q . . | | . . Q . . . . . | | . . . . . . Q . | | . Q . . . . . . | | . . . Q . . . . | *-----------------* ・・・省略・・・ *-----------------* | . . . . . . . Q | | . . . Q . . . . | | Q . . . . . . . | | . . Q . . . . . | | . . . . . Q . . | | . Q . . . . . . | | . . . . . . Q . | | . . . . Q . . . | *-----------------* => [0, 1, 2, 3, 4, 5, 6, 7]
解は重複解を含めて全部で 92 通りです。
ところで、クイーンの個数を増やすと、プログラムの実行時間は極端に遅くなります。
irb> nqueen_solver_count(8) 92 0.080634698 => nil irb> nqueen_solver_count(9) 352 0.7200884 => nil irb> nqueen_solver_count(10) 724 7.421598528 => nil 実行環境 : Ruby 3.0, Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz
クイーンの個数をひとつ増やしただけでも、実行時間はとても遅くなります。遅くなる理由は、失敗することがわかっている順列も生成してしまうからです。たとえば、最初 (1, 1) の位置にクイーンを置くと、次のクイーンは (2, 2) の位置に置くことはできませんね。したがって、[1, 2, X, X, X, X, X, X,] という配置はすべて失敗するのですが、順列を生成してからチェックする方法では、このような無駄を省くことができません。
そこで、クイーンの配置を決めるたびに衝突のチェックを行うことにします。これをプログラムすると次のようになります。
リスト : 高速化
def nqueen_fast(n, m, xs, &func)
if n == m
func.call xs
else
for i in m ... n
next if conflict(xs, xs[i], m)
xs[i], xs[m] = xs[m], xs[i]
nqueen_fast(n, m + 1, xs, &func)
xs[i], xs[m] = xs[m], xs[i]
end
end
end
def nqueen_solver_fast_count(n)
cnt = 0
s = Time.now
nqueen_fast(n, 0, (0...n).to_a) do |board| cnt += 1 end
print cnt, " ", Time.now - s, "\n"
end
関数 nqueen_fast() は順列を生成するときに conflict() を付け加えただけです。これで無駄な順列の生成を省くことができます。
irb> nqueen_solver_fast_count(8) 92 0.0058453 => nil irb> nqueen_solver_fast_count(9) 352 0.024330488 => nil irb> nqueen_solver_fast_count(10) 724 0.106956391 => nil irb> nqueen_solver_fast_count(11) 2680 0.532901968 => nil irb> nqueen_solver_fast_count(12) 14200 2.984976401 => nil 実行環境 : Ruby 3.0, Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz
N Queens Problem の高速化に興味のある方は拙作のページ「Puzzle DE Programming: N Queens Problem」をお読みくださいませ。
┌─┬─┬─┐ ┌─┬─┬─┐
│６│４│７│ │１│２│３│
├─┼─┼─┤ ├─┼─┼─┤
│８│５│ │ => │４│５│６│
├─┼─┼─┤ ├─┼─┼─┤
│３│２│１│ │７│８│ │
└─┴─┴─┘ └─┴─┴─┘
START GOAL
8 パズルは上図に示すように 1 から 8 までの駒を並べるパズルです。駒の動かし方は、1 回に 1 個の駒を空いている隣の場所に滑らせる、というものです。駒を飛び越したり持ち上げたりすることはできません。スタートからゴールまでの最短手順を求めてください。
パズルの詳しい説明は以下の拙作のページをお読みください。
単純な幅優先探索で解を求めます。
リスト : 8 パズル
# 盤面
# 0 1 2
# 3 4 5
# 6 7 8
# 隣接リスト
$adjacent8 = [
[1, 3],
[0, 2, 4],
[1, 5],
[0, 4, 6],
[1, 3, 5, 7],
[2, 4, 8],
[3, 7],
[4, 6, 8],
[5, 7]
]
# 解の表示
def print_answer8(que, n)
print_answer8(que, que[n][2]) if n > 0
print que[n][0], "\n"
end
# 幅優先探索
def bfs8(start, goal)
que = [[start, start.index(0), -1]]
tbl = {start => true}
rp = 0
while rp < que.size
board, space, prev = que[rp]
if board == goal
print_answer8(que, rp)
return true
else
$adjacent8[space].each {|x|
newboard = board.dup
newboard[space] = newboard[x]
newboard[x] = 0
if !tbl[newboard]
que.push [newboard, x, rp]
tbl[newboard] = true
end
}
end
rp += 1
end
false
end
irb> Time.now; bfs8([8,6,7,2,5,4,3,0,1], [1,2,3,4,5,6,7,8,0]); Time.now - s [8, 6, 7, 2, 5, 4, 3, 0, 1] [8, 6, 7, 2, 0, 4, 3, 5, 1] [8, 0, 7, 2, 6, 4, 3, 5, 1] [0, 8, 7, 2, 6, 4, 3, 5, 1] [2, 8, 7, 0, 6, 4, 3, 5, 1] [2, 8, 7, 3, 6, 4, 0, 5, 1] [2, 8, 7, 3, 6, 4, 5, 0, 1] [2, 8, 7, 3, 6, 4, 5, 1, 0] [2, 8, 7, 3, 6, 0, 5, 1, 4] [2, 8, 0, 3, 6, 7, 5, 1, 4] [2, 0, 8, 3, 6, 7, 5, 1, 4] [2, 6, 8, 3, 0, 7, 5, 1, 4] [2, 6, 8, 0, 3, 7, 5, 1, 4] [2, 6, 8, 5, 3, 7, 0, 1, 4] [2, 6, 8, 5, 3, 7, 1, 0, 4] [2, 6, 8, 5, 3, 7, 1, 4, 0] [2, 6, 8, 5, 3, 0, 1, 4, 7] [2, 6, 0, 5, 3, 8, 1, 4, 7] [2, 0, 6, 5, 3, 8, 1, 4, 7] [2, 3, 6, 5, 0, 8, 1, 4, 7] [2, 3, 6, 0, 5, 8, 1, 4, 7] [2, 3, 6, 1, 5, 8, 0, 4, 7] [2, 3, 6, 1, 5, 8, 4, 0, 7] [2, 3, 6, 1, 5, 8, 4, 7, 0] [2, 3, 6, 1, 5, 0, 4, 7, 8] [2, 3, 0, 1, 5, 6, 4, 7, 8] [2, 0, 3, 1, 5, 6, 4, 7, 8] [0, 2, 3, 1, 5, 6, 4, 7, 8] [1, 2, 3, 0, 5, 6, 4, 7, 8] [1, 2, 3, 4, 5, 6, 0, 7, 8] [1, 2, 3, 4, 5, 6, 7, 0, 8] [1, 2, 3, 4, 5, 6, 7, 8, 0] => 1.063105344 実行環境 : Ruby 3.0, Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz
次は最長手数の局面を求めてみましょう。まず、完成形から駒を動かして 1 手で到達する局面をすべて作ります。次に、これらの局面から駒を動かして新しい局面を作れば、完成形から 2 手で到達する局面となります。このように、手数を 1 手ずつ伸ばしていき、新しい局面が生成できなくなった時点での手数が求める最長手数となります。この処理は幅優先探索を使えばぴったりです。
リスト : 最長手数の局面
def bfs8_max()
start = [1,2,3,4,5,6,7,8,0]
xs = [[start, start.index(0)]]
move = 0
tbl = {start => true}
while true
ys = []
xs.each {|board, space|
$adjacent8[space].each {|x|
newboard = board.dup
newboard[space] = newboard[x]
newboard[x] = 0
if !tbl[newboard]
ys.push [newboard, x]
tbl[newboard] = true
end
}
}
break if ys.size == 0
move += 1
print "move = ", move, " 個数 = ", ys.size, "\n"
xs = ys
end
print "最長手数 = ", move, " 個数 = ", xs.size, "\n"
xs.each {|x| print x[0], "\n"}
end
irb> s = Time.now; bfs8_max(); Time.now - s move = 1 個数 = 2 move = 2 個数 = 4 move = 3 個数 = 8 move = 4 個数 = 16 move = 5 個数 = 20 move = 6 個数 = 39 move = 7 個数 = 62 move = 8 個数 = 116 move = 9 個数 = 152 move = 10 個数 = 286 move = 11 個数 = 396 move = 12 個数 = 748 move = 13 個数 = 1024 move = 14 個数 = 1893 move = 15 個数 = 2512 move = 16 個数 = 4485 move = 17 個数 = 5638 move = 18 個数 = 9529 move = 19 個数 = 10878 move = 20 個数 = 16993 move = 21 個数 = 17110 move = 22 個数 = 23952 move = 23 個数 = 20224 move = 24 個数 = 24047 move = 25 個数 = 15578 move = 26 個数 = 14560 move = 27 個数 = 6274 move = 28 個数 = 3910 move = 29 個数 = 760 move = 30 個数 = 221 move = 31 個数 = 2 最長手数 = 31 個数 = 2 [6, 4, 7, 8, 5, 0, 3, 2, 1] [8, 6, 7, 2, 5, 4, 3, 0, 1] => 1.220661362 実行環境 : Ruby 3.0, Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz
最長手数は 31 手で、その配置は全部で 2 通りになります。
ペグ・ソリテアは、盤上に配置されたペグ (駒) を、最後にはひとつ残るように取り除いていく、古典的なパズルです。ルールについては拙作のページ「Puzzle DE Programming: ペグ・ソリテア」をお読みください。
Hoppers は芦ヶ原伸之氏が考案されたペグ・ソリテアです。次の図を見てください。
●───●───● │＼ ／│＼ ／│ │ ● │ ● │ │／ ＼│／ ＼│ ●───○───● │＼ ／│＼ ／│ │ ● │ ● │ │／ ＼│／ ＼│ ●───●───● 図 : Hoppers
Hoppers は穴を 13 個に減らしていて、遊ぶのに手頃な大きさになっています。上図に示したように、最初に中央のペグを取り除きます。この状態から始めて、最後のペグが中央の位置に残る跳び方の最小手数を求めてください。
最小手数といえば「幅優先探索」ですが、連続跳びの処理が面倒になりそうなので、ここは「深さ優先探索」を採用することにします。プログラムのポイントは、ペグを跳び越すときに手数も同時に数えていくことです。直前に動かしたペグと違うペグを動かすときは手数をカウントし、同じペグを動かすときは手数をカウントしません。そして、手数の上限値を定めて探索を行います。たとえば、最初は 5 手を限度に探索し、見つからなければ上限値を 6 手に増やす、というように 1 手ずつ増やしながら探索するのです。
このような探索を「反復深化」といいます。幅優先探索が使えない問題には有効な探索手法のひとつです。反復深化の詳しい説明は拙作のページ「Algorithms with Python: 集合、グラフ、経路の探索」をお読みください。
それでは、プログラムを作りましょう。今回は Hoppers の盤面を配列で表すことにします。配列の要素は真偽値です。ペグがある状態を true で、ペグがない状態を false で表します。配列の添字と盤面の対応は、下図を見てください。
●───●───● ０───１───２
│＼ ／│＼ ／│ │＼ ／│＼ ／│
│ ● │ ● │ │ ３ │ ４ │
│／ ＼│／ ＼│ │／ ＼│／ ＼│
●───○───● ５───６───７
│＼ ／│＼ ／│ │＼ ／│＼ ／│
│ ● │ ● │ │ ８ │ ９ │
│／ ＼│／ ＼│ │／ ＼│／ ＼│
●───●───● 10───11───12
(1) Hoppers (2) ビットの位置
図 : Hoppers の盤面
ペグの移動は跳び先表を用意すると簡単です。次のプログラムを見てください。
リスト : 定数と跳び先表
# 定数
MAX_JUMP = 11
HOLE = 6
SIZE = 13
# 跳び先表
$jump_table = [
[[1, 2], [3, 6], [5, 10]],
[[3, 5], [6, 11], [4, 7]],
[[1, 0], [4, 6], [7, 12]],
[[6, 9]],
[[6, 8]],
[[3, 1], [6, 7], [8, 11]],
[[3, 0], [4, 2], [8, 10], [9, 12]],
[[4, 1], [6, 5], [9, 11]],
[[6, 4]],
[[6, 3]],
[[5, 0], [8, 6], [11, 12]],
[[8, 5], [6, 1], [9, 7]],
[[11, 10], [9, 6], [7, 2]]
]
ペグの跳び先表は配列 $jump_table で定義します。要素は跳び越されるペグの位置と跳び先の位置を格納した配列です。たとえば、0 番の位置にあるペグは、1 番を跳び越して 2 番へ移動する場合と、3 番を跳び越して 6 番へ移動する場合と、5 番を跳び越して 10 番へ移動する場合の 3 通りがあります。これを配列 [1, 2], [3, 6], [5, 10] で表しています。
あとは単純な反復深化で最短手順を求めます。プログラムは次のようになります。
リスト : 反復深化による解法
# 反復深化
def dfs(board, jc, limit, move)
return if jc > limit
if move.size == MAX_JUMP
if board[HOLE]
print_move(move)
$cnt += 1
end
else
for from in 0...SIZE
next if not board[from]
for del, to in $jump_table[from]
next if !board[del] || board[to]
board[from] = false
board[del] = false
board[to] = true
if move[-1][1] == from
newjc = jc
else
newjc = jc + 1
end
move.push [from, to]
dfs(board, newjc, limit, move)
move.pop
board[from] = true
board[del] = true
board[to] = false
end
end
end
end
def peg_solver()
$cnt = 0
board = [true] * SIZE
# 初手を 0 -> 6 に限定
board[0] = false
board[3] = false
for i in 2 .. MAX_JUMP
print '-----', i, '-----', "\n"
dfs(board, 1, i, [[0, 6]])
break if $cnt > 0
end
print $cnt, "\n"
end
反復深化の処理は関数 dfs() で行います。引数 board が盤面、jc がペグが跳んだ回数、limit が反復深化の上限値、move が移動手順を格納するリストで、要素は配列 [移動元, 移動先] です。
ペグ・ソリテアを反復深化で解く場合、上限値 limit に達していても連続跳びによりペグを移動できることに注意してください。最初に、jc をチェックして limit 以下であればペグを移動します。Hoppers の場合、ペグの総数は 12 個なので、MAX_JUMP (11) 回ペグを移動すると、残りのペグは 1 個になります。解を見つけたら関数 print_move() で手順を表示して、見つけた解の個数 $cnt を +1 します。
そうでなければペグを移動します。for ループの変数 from が動かすペグの位置を表します。最初に、from の位置にペグがあることを確認します。それから、跳び先表から跳び越されるペグの位置と跳び先の位置を for ループで順番に取り出して、変数 del, to にセットします。del の位置にペグがあり to の位置にペグがなければ、from のペグを to へ移動することができます。
ペグが移動できるできる場合、ペグを動かして dfs() を再帰呼び出しします。そして、このプログラムのポイントが連続跳びのチェックをするところです。直前に移動した場所からペグを動かすときは、連続跳びと判断することができます。つまり、move の末尾の配列の 1 番目の要素 (move[-1][1]) が from と等しい場合は、跳んだ回数 jc を増やしません。異なる場合は jc の値を +1 します。再帰呼び出しから戻ってきたらペグを元に戻します。
あとは反復深化の上限値を増やしながら dfs() を呼び出します。for ループの変数 i が上限値を表します。最初の移動は、四隅にあるペグのひとつを中央に動かす手順しかありません。そこで、最初は 0 のペグを 6 へ動かすことに決めて、その状態から探索を開始します。$cnt が 0 でなければ、解を見つけたので反復深化を終了します。
最後に手順を表示する関数 print_move() を作ります。
リスト : 手順の表示
def print_move(xs)
from, to = xs[0]
print "[", from, ", ", to
prev = to
for from, to in xs[1..-1]
if prev == from
print ", ", to
else
print "][", from, ", ", to
end
prev = to
end
print "]", "\n"
end
移動手順は 1 手を [from, to] で表し、連続跳びの場合は [from, to1, to2, ..., toN] とします。1 手前の跳び先の位置を変数 prev にセットしておいて、それと動かすペグの位置が同じであれば連続跳びです。跳び先の位置を prev にセットして、それを表示します。違うペグが跳ぶ場合は、] [ を表示してから動かすペグの位置と跳び先の位置を表示します。
これでプログラムは完成です。それでは実行してみましょう。
irb> peg_solver() -----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][2, 0, 6][11, 1][10, 6][4, 8][12, 2, 0, 10, 6] [0, 6][9, 3][2, 0, 6][11, 1][12, 2, 6][8, 4][10, 0, 2, 6] [0, 6][9, 3][2, 6][8, 4][10, 0, 2, 6][7, 5][12, 10, 0, 6] [0, 6][9, 3][2, 6][8, 4][10, 0, 2, 6][11, 1][12, 2, 0, 6] [0, 6][9, 3][2, 6][8, 4][10, 0, 6][7, 5][12, 10, 0, 2, 6] [0, 6][9, 3][2, 6][8, 4][12, 2, 0, 6][5, 7][10, 12, 2, 6] [0, 6][9, 3][2, 6][8, 4][12, 2, 0, 6][11, 1][10, 0, 2, 6] [0, 6][9, 3][2, 6][8, 4][12, 2, 6][5, 7][10, 12, 2, 0, 6] [0, 6][9, 3][10, 0, 6][7, 5][2, 0, 10, 6][4, 8][12, 10, 6] [0, 6][9, 3][10, 0, 6][7, 5][2, 6][8, 4][12, 10, 0, 2, 6] [0, 6][9, 3][10, 0, 6][7, 5][12, 10, 6][4, 8][2, 0, 10, 6] [0, 6][9, 3][10, 6][4, 8][2, 0, 6][11, 1][12, 2, 0, 10, 6] [0, 6][9, 3][10, 6][4, 8][2, 0, 10, 6][7, 5][12, 10, 0, 6] [0, 6][9, 3][10, 6][4, 8][2, 0, 10, 6][11, 1][12, 2, 0, 6] [0, 6][9, 3][10, 6][4, 8][12, 10, 0, 6][1, 11][2, 12, 10, 6] [0, 6][9, 3][10, 6][4, 8][12, 10, 0, 6][7, 5][2, 0, 10, 6] [0, 6][9, 3][10, 6][4, 8][12, 10, 6][1, 11][2, 12, 10, 0, 6] 18 => nil
7 手で解くことができました。解は全部で 18 通りあります。最近のパソコンは高性能なので、穴の数が少ない盤面であれば、単純な反復深化でも高速に解くことができるようです。
マスターマインドは拙作のページ「お気楽 Scheme プログラミング入門: 数当てゲーム [2]」で作成した、0 から 9 までの重複しない 4 つの数字からなる隠しコードを当てるゲームです。数字は合っているが位置が間違っている個数を cows で表し、数字も位置も合っている個数を bulls で表します。bulls が 4 になると正解です。
[6, 2, 8, 1] : 正解
-------------------------------------
1. [0, 1, 2, 3] : cows 2 : bulls 0
2. [1, 0, 4, 5] : cows 1 : bulls 0
3. [2, 3, 5, 6] : cows 2 : bulls 0
4. [3, 2, 7, 4] : cows 0 : bulls 1
5. [3, 6, 0, 8] : cows 2 : bulls 0
6. [6, 2, 8, 1] : cows 0 : bulls 4
図 : マスターマインドの動作例
今回は、私達が出した問題をコンピュータに答えてもらうことにします。それはちょっと難しいのではないか、と思った人もいるかもしれませんね。ところが、とても簡単な方法があるのです。
このゲームでは、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] に矛盾しないコードを選択するのです。
それでは、プログラムを作りましょう。最初に bulls と cows を求める関数を作ります。
リスト : bulls と cows を求める
# bulls を数える
def count_bulls(xs, ys)
xs.zip(ys).map{|zs| zs[0] == zs[1]}.count(true)
end
# 同じ数字を数える
def count_same_number(xs, ys)
xs.reduce(0){|a, x| ys.member?(x) ? a + 1 : a}
end
関数 count_bulls() は bulls の個数を数えます。引数 xs と ys はコードを表す配列です。zip() と map() で 2 つの要素の等値を判定し、count() で true の個数を数えれば bulls を求めることができます。
次は cows を数える処理を作ります。いきなり cows を数えようとすると難しいのですが、2 つのコードに共通の数字を数えることは簡単にできます。この方法では、bulls の個数を含んだ数を求めることになりますが、そこから bulls を引けば cows を求めることができます。
関数名は count_same_number() としました。この処理は reduce() を使うと簡単です。xs の要素を取り出して、それが ys に含まれているか member?() で判定します。そうであれば、累積変数 a を +1 します。
次は生成したコードが今までの結果と矛盾していないか調べる関数 check_query() を作ります。次のリストを見てください。
リスト : 今までの質問と矛盾しているか
def check_query(code, qs)
for old_code, old_bulls, old_cows in qs
b = count_bulls(code, old_code)
c = count_same_number(code, old_code) - b
return false if b != old_bulls || c != old_cows
end
true
end
引数 code が生成したコード、qs は今までの質問結果を格納した配列です。質問結果は配列 [code, bulls, cows] にまとめて qs に格納します。for ループで qs から質問結果を順番に取り出し、その要素を変数 old_bulls, old_cows, old_code にセットします。
次に、code と old_colde から bulls と cows を求め、変数 b, c にセットします。b と old_bulls が異なる、または c と old_cows が異なる場合、code は矛盾しているので false を返します。すべての質問結果に対して矛盾が無ければ true を返します。
マスターマインドを解くプログラムは次のようになります。
リスト : マスターマインドの解法
def print_master_mind(qs)
qs.to_enum.with_index(1) do |xs, i|
printf "%d: %s : bulls = %d, cows = %d\n", i, xs[0], xs[1], xs[2]
end
print "Good Job!!\n"
end
def master(ans, verbos = true)
qs = []
(0..9).to_a.permutation(4) {|code|
next if !check_query(code, qs)
b = count_bulls(code, ans)
c = count_same_number(code, ans) - b
qs.push [code, b, c]
if b == 4
print_master_mind(qs) if verbos
return qs.size
end
}
0
end
関数 master() の引数 ans には正解のコードを渡し、変数 qs に質問結果を格納します。順列はメソッド permutations() で生成します。順列はブロックの引数 code に渡されます。code が質問結果と矛盾しないか check_query() でチェックします。矛盾が無ければ bulls と cows を求め、qs に質問結果を追加します。最後に bulls が 4 ならば、print_master_mind() で解を表示して、return で qs.size を返します。
これでプログラムは完成です。それでは実行例を示しましょう。
irb(main):002:0> master([9,8,7,6]) 1: [0, 1, 2, 3] : bulls = 0, cows = 0 2: [4, 5, 6, 7] : bulls = 0, cows = 2 3: [5, 4, 8, 9] : bulls = 0, cows = 2 4: [6, 7, 9, 8] : bulls = 0, cows = 4 5: [8, 9, 7, 6] : bulls = 2, cows = 2 6: [9, 8, 7, 6] : bulls = 4, cows = 0 Good Job!! => 6 irb(main):003:0> master([1,3,5,7]) 1: [0, 1, 2, 3] : bulls = 0, cows = 2 2: [1, 0, 4, 5] : bulls = 1, cows = 1 3: [1, 2, 5, 6] : bulls = 2, cows = 0 4: [1, 2, 7, 4] : bulls = 1, cows = 1 5: [1, 3, 5, 7] : bulls = 4, cows = 0 Good Job!! => 5 irb(main):004:0> master([8,6,4,2]) 1: [0, 1, 2, 3] : bulls = 0, cows = 1 2: [1, 4, 5, 6] : bulls = 0, cows = 2 3: [2, 5, 4, 7] : bulls = 1, cows = 1 4: [2, 6, 8, 4] : bulls = 1, cows = 3 5: [8, 6, 4, 2] : bulls = 4, cows = 0 Good Job!! => 5
肝心の質問回数ですが、5, 6 回で当たる場合が多いようです。そこで、5040 個のコードをすべて試してみました。
リスト : すべてのコードを試す
def master_mind_all()
xs = (0..9).to_a.permutation(4).to_a
ys = xs.map {|code| master(code, false)}
printf "平均質問回数 %f\n", ys.sum.fdiv(ys.size)
m = ys.max
printf "最大質問回数 %d\n", m
ys.each_with_index {|cnt, i|
print xs[i], "\n" if cnt == m
}
end
プログラムは簡単なので説明は割愛させていただきます。実行結果は次のようになりました。
irb(main):002:0> s = Time.now; master_mind_all; Time.now - s 平均質問回数 5.560317 最大質問回数 9 [5, 2, 9, 3] [9, 2, 0, 4] [9, 2, 1, 4] [9, 2, 4, 1] [9, 4, 3, 1] => 52.79299904 実行環境 : Ruby 3.0, Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz
平均質問回数は 5.56 回になりました。これは参考文献「数当てゲーム (MOO, マスターマインド)」の結果と同じです。質問回数の最大値は 9 回で、そのときのコードは [5, 2, 9, 3], [9, 2, 0, 4], [9, 2, 1, 4], [9, 2, 4, 1], [9, 4, 3, 1] の 5 通りでした。
irb(main):003:0> master [5,2,9,3] 1: [0, 1, 2, 3] : bulls = 1, cows = 1 2: [0, 2, 4, 5] : bulls = 1, cows = 1 3: [0, 3, 5, 6] : bulls = 0, cows = 2 4: [1, 5, 4, 3] : bulls = 1, cows = 1 5: [1, 6, 2, 5] : bulls = 0, cows = 2 6: [4, 2, 6, 3] : bulls = 2, cows = 0 7: [5, 2, 7, 3] : bulls = 3, cows = 0 8: [5, 2, 8, 3] : bulls = 3, cows = 0 9: [5, 2, 9, 3] : bulls = 4, cows = 0 Good Job!! => 9 irb(main):004:0> master [9,4,3,1] 1: [0, 1, 2, 3] : bulls = 0, cows = 2 2: [1, 0, 4, 5] : bulls = 0, cows = 2 3: [2, 3, 5, 4] : bulls = 0, cows = 2 4: [3, 4, 0, 6] : bulls = 1, cows = 1 5: [3, 5, 6, 1] : bulls = 1, cows = 1 6: [6, 5, 0, 2] : bulls = 0, cows = 0 7: [7, 4, 3, 1] : bulls = 3, cows = 0 8: [8, 4, 3, 1] : bulls = 3, cows = 0 9: [9, 4, 3, 1] : bulls = 4, cows = 0 Good Job!! => 9
なお、参考文献には平均質問回数がこれよりも少なくなる方法が紹介されています。単純な数当てゲームと思っていましたが、その奥はけっこう深いようです。興味のある方はいろいろ試してみてください。
# coding: utf-8
#
# puzzle.rb : Puzzle DE Ruby!!
#
# Copyright (C) 2023 Makoto Hiroi
#
#
# 小町算
#
# eval 版
def komachi(n, expr, ans)
if n == 10
if eval(expr) == ans
print expr, " = ", ans, "\n"
end
else
komachi(n + 1, expr + " + " + n.to_s, ans)
komachi(n + 1, expr + " - " + n.to_s, ans)
komachi(n + 1, expr + n.to_s, ans)
end
end
def komachi_solver1(ans)
komachi(2, "1", ans)
end
# 式を配列で表す
# 式の表示
def print_expr(expr, ans)
expr.each do |x| print x, " " end
print '= ', ans, "\n"
end
# 式の計算
def calc_expr(expr)
a = expr[0]
i = 1
while i < expr.size
case expr[i]
when "+"
a += expr[i + 1]
when "-"
a -= expr[i + 1]
end
i += 2
end
a
end
# 式の生成
def make_expr(n, expr, ans)
if n == 10
print_expr(expr, ans) if calc_expr(expr) == ans
else
make_expr(n + 1, expr + ["+", n], ans)
make_expr(n + 1, expr + ["-", n], ans)
save = expr[-1]
expr[-1] = expr[-1] * 10 + n
make_expr(n + 1, expr, ans)
expr[-1] = save
end
end
def komachi_solver2(ans)
make_expr(2, [1], ans)
end
#
# 騎士の巡歴
#
# 隣接リスト
$adjacent = [
[5, 7], # 0
[6, 8], # 1
[3, 7], # 2
[2, 8, 10], # 3
[9, 11], # 4
[0, 6, 10], # 5
[1, 5, 11], # 6
[0, 2], # 7
[1, 3, 9], # 8
[4, 8], # 9
[3, 5], # 10
[4, 6] # 11
]
# 深さ優先探索
def knight_tour(n = 1, path = [0])
if n == 12
print path, "\n"
else
for x in $adjacent[path[-1]]
next if path.member? x
path.push x
knight_tour n + 1, path
path.pop
end
end
end
#
# 魔方陣
#
# 盤面
# 0 1 2
# 3 4 5
# 6 7 8
# 直線を表す配列
$lines = [
[0, 1, 2], [3, 4, 5], [6, 7, 8],
[0, 3, 6], [1, 4, 7], [2, 5, 8],
[0, 4, 8], [2, 4, 6]
]
def sum_line(board, a, b, c)
board[a] + board[b] + board[c]
end
def check(board)
xs = $lines.map {|ls| sum_line(board, *ls)}
xs.count(xs[0]) == xs.size
end
def print_board(board)
for i in 0..8
print board[i], " "
print "\n" if (i + 1) % 3 == 0
end
print "\n"
end
def magic_square()
(1..9).to_a.permutation do |board|
print_board(board) if check(board)
end
end
def magic_square1(board = [])
if board.size == 9
print_board(board) if check(board)
else
for n in 1..9
next if board.member? n
next if board.size == 2 && board[0] > n
next if board.size == 6 && board[2] > n
next if board.size == 8 && board[0] > n
board.push n
magic_square1 board
board.pop
end
end
end
#
# ライツアウト
#
# 押すボタンのパターン
$pattern = [
0x0000023, 0x0000047, 0x000008e, 0x000011c, 0x0000218,
0x0000461, 0x00008e2, 0x00011c4, 0x0002388, 0x0004310,
0x0008c20, 0x0011c40, 0x0023880, 0x0047100, 0x0086200,
0x0118400, 0x0238800, 0x0471000, 0x08e2000, 0x10c4000,
0x0308000, 0x0710000, 0x0e20000, 0x1c40000, 0x1880000
]
# 解の表示
def print_answer_lo(xs)
for i in 0..24
if xs.member? i
print 'O '
else
print '. '
end
print "\n" if (i + 1) % 5 == 0
end
print "\n"
end
# ボタンを押す
def push_button(board, xs)
xs.reduce(board) do |a, x| a ^ $pattern[x] end
end
# ライツアウトの解法
def solver_lo(board)
for i in 1..25
print '-----', i, '-----', "\n"
(0..24).to_a.combination(i) do |xs|
if push_button(board, xs) == 0
print_answer_lo(xs)
return
end
end
end
end
# 高速化
def solver_lo_fast(board)
for i in 0..5
(0..4).to_a.combination(i) do |xs|
b = push_button(board, xs)
for j in 5..24
if b[j - 5] == 1
b ^= $pattern[j]
xs.push j
end
end
print_answer_lo(xs) if b == 0
end
end
end
#
# 8 Queen
#
# 解の表示
def print_queen_line(q, size)
print "| "
for i in 0 ... size
if i == q
print "Q "
else
print ". "
end
end
print "|\n"
end
def print_queen(board)
n = board.size
print "*-", "--" * n, "*\n"
board.each do |x|
print_queen_line(x, n)
end
print "*-", "--" * n, "*\n"
end
# 衝突のチェック
def conflict(board, y, x)
for x1 in 0 ... x
y1 = board[x1]
return true if (x1 - y1 == x - y) || (x1 + y1 == x + y)
end
false
end
# 安全確認
def is_safe(board)
for x in 0 ... board.size
return false if conflict(board, board[x], x)
end
true
end
def nqueen_solver(n)
(0...n).to_a.permutation do |board|
print_queen(board) if is_safe(board)
end
end
def nqueen_solver_count(n)
cnt = 0
s = Time.now
(0...n).to_a.permutation do |board|
cnt += 1 if is_safe(board)
end
print cnt, " ", Time.now - s, "\n"
end
def nqueen_fast(n, m, xs, &func)
if n == m
func.call xs
else
for i in m ... n
next if conflict(xs, xs[i], m)
xs[i], xs[m] = xs[m], xs[i]
nqueen_fast(n, m + 1, xs, &func)
xs[i], xs[m] = xs[m], xs[i]
end
end
end
def nqueen_solver_fast_count(n)
cnt = 0
s = Time.now
nqueen_fast(n, 0, (0...n).to_a) do |board| cnt += 1 end
print cnt, " ", Time.now - s, "\n"
end
#
# 8 パズル
#
# 盤面
# 0 1 2
# 3 4 5
# 6 7 8
# 隣接リスト
$adjacent8 = [
[1, 3],
[0, 2, 4],
[1, 5],
[0, 4, 6],
[1, 3, 5, 7],
[2, 4, 8],
[3, 7],
[4, 6, 8],
[5, 7]
]
# 解の表示
def print_answer8(que, n)
print_answer8(que, que[n][2]) if n > 0
print que[n][0], "\n"
end
# 幅優先探索
def bfs8(start, goal)
que = [[start, start.index(0), -1]]
tbl = {start => true}
rp = 0
while rp < que.size
board, space, prev = que[rp]
if board == goal
print_answer8(que, rp)
return true
else
$adjacent8[space].each {|x|
newboard = board.dup
newboard[space] = newboard[x]
newboard[x] = 0
if !tbl[newboard]
que.push [newboard, x, rp]
tbl[newboard] = true
end
}
end
rp += 1
end
false
end
# 最長手数の局面
def bfs8_max()
start = [1,2,3,4,5,6,7,8,0]
xs = [[start, start.index(0)]]
move = 1
tbl = {start => true}
while true
ys = []
xs.each {|board, space|
$adjacent8[space].each {|x|
newboard = board.dup
newboard[space] = newboard[x]
newboard[x] = 0
if !tbl[newboard]
ys.push [newboard, x]
tbl[newboard] = true
end
}
}
break if ys.size == 0
print "move = ", move, " 個数 = ", ys.size, "\n"
move += 1
xs = ys
end
print "最長手数 = ", move, " 個数 = ", xs.size, "\n"
xs.each {|x| print x[0], "\n"}
end
#
# Hoppers
#
# 定数
MAX_JUMP = 11
HOLE = 6
SIZE = 13
# 跳び先表
$jump_table = [
[[1, 2], [3, 6], [5, 10]],
[[3, 5], [6, 11], [4, 7]],
[[1, 0], [4, 6], [7, 12]],
[[6, 9]],
[[6, 8]],
[[3, 1], [6, 7], [8, 11]],
[[3, 0], [4, 2], [8, 10], [9, 12]],
[[4, 1], [6, 5], [9, 11]],
[[6, 4]],
[[6, 3]],
[[5, 0], [8, 6], [11, 12]],
[[8, 5], [6, 1], [9, 7]],
[[11, 10], [9, 6], [7, 2]]
]
# 手順の表示
def print_move(xs)
from, to = xs[0]
print "[", from, ", ", to
prev = to
for from, to in xs[1..-1]
if prev == from
print ", ", to
else
print "][", from, ", ", to
end
prev = to
end
print "]", "\n"
end
# 反復深化
def dfs(board, jc, limit, move)
return if jc > limit
if move.size == MAX_JUMP
if board[HOLE]
print_move(move)
$cnt += 1
end
else
for from in 0...SIZE
next if not board[from]
for del, to in $jump_table[from]
next if !board[del] || board[to]
board[from] = false
board[del] = false
board[to] = true
if move[-1][1] == from
newjc = jc
else
newjc = jc + 1
end
move.push [from, to]
dfs(board, newjc, limit, move)
move.pop
board[from] = true
board[del] = true
board[to] = false
end
end
end
end
def peg_solver()
$cnt = 0
board = [true] * SIZE
# 初手を 0 -> 6 に限定
board[0] = false
board[3] = false
for i in 2 .. MAX_JUMP
print '-----', i, '-----', "\n"
dfs(board, 1, i, [[0, 6]])
break if $cnt > 0
end
print $cnt, "\n"
end
#
# マスターマインド
#
# bulls を数える
def count_bulls(xs, ys)
xs.zip(ys).map{|zs| zs[0] == zs[1]}.count(true)
end
# 同じ数字を数える
def count_same_number(xs, ys)
xs.reduce(0){|a, x| ys.member?(x) ? a + 1 : a}
end
# 今までの質問と矛盾がないか
def check_query(code, qs)
for old_code, old_bulls, old_cows in qs
b = count_bulls(code, old_code)
c = count_same_number(code, old_code) - b
return false if b != old_bulls || c != old_cows
end
true
end
def print_master_mind(qs)
qs.to_enum.with_index(1) do |xs, i|
printf "%d: %s : bulls = %d, cows = %d\n", i, xs[0], xs[1], xs[2]
end
print "Good Job!!\n"
end
def master(ans, verbos = true)
qs = []
(0..9).to_a.permutation(4) {|code|
next if !check_query(code, qs)
b = count_bulls(code, ans)
c = count_same_number(code, ans) - b
qs.push [code, b, c]
if b == 4
print_master_mind(qs) if verbos
return qs.size
end
}
0
end
def master_mind_all()
xs = (0..9).to_a.permutation(4).to_a
ys = xs.map {|code| master(code, false)}
printf "平均質問回数 %f\n", ys.sum.fdiv(ys.size)
m = ys.max
printf "最大質問回数 %d\n", m
ys.each_with_index {|cnt, i|
print xs[i], "\n" if cnt == m
}
end