Puzzle DE Julia!! は、パズルを題材に Julia でプログラミングを楽しみましょう、というお気楽なページです。どのプログラミング言語でもそうですが、上達の秘訣は実際にプログラムを作って、その動作を確認してみることです。ところが、いざとなると「さて、何を作ろうか？」と困ってしまう方も多いのではないでしょうか。
このようなときにぴったりな題材が「パズルの解法」です。なんといっても、実際にパズルが解けたときの喜びはとても大きく、プログラムを作る意欲をかきたててくれます。そして、解を求めるだけではなく、実行時間を短縮するためにプログラムを改良するのです。これがパズルプログラミングの醍醐味といってもいいでしょう。
簡単なパズルは力任せでも解くことができますが、少し複雑なパズルになると力任せでは時間がかかってしまいます。ところが、パズルの性質や特徴を見極めてプログラムを作ると、実行時間を劇的に短縮できる場合があります。プログラミングに興味をお持ちの方は、ぜひパズルの解法にも挑戦してみてください。
探索の基本的なアルゴリズムには、深さ優先探索 (depth first search)、幅優先探索 (breadth first searh)、反復深化 (iterative deeping) などがあります。アルゴリズムの詳しい説明は以下に示す拙作のページをお読みくださいませ。
今回は「生成検定法 (generate and test)」という方法を使ってパズルを解いてみましょう。生成検定法は問題を解くときによく用いられる方法で、正解の可能性があるデータを生成してチェックすることで正解をひとつ、またはすべて見つけることができます。可能性のあるデータをもれなく作るのにバックトラックは最適です。ただし、「生成するデータ数が多くなると時間がとてもかかる」という弱点があるので注意してください。
パズルの世界では、1 から 9 までの数字を 1 個ずつすべて使った数字を「小町数」といいます。たとえば、123456789 とか 321654987 のような数字です。「小町算」というものもあり、たとえば 123 + 456 + 789 とか 321 * 654 + 987 のようなものです。一番有名な問題は拙作のページ「小町算」で取り上げました。参考文献『超々難問数理パズル 解けるものなら解いてごらん』に掲載されている問題に挑戦してみましょう。
下図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。3 つの分数を足すと 1 / N になる配置を求めてください。
このパズルの元ネタは N = 1 の場合です。ちなみに、3 つの分数の和が整数になる場合、その値は 1 しかありません。
計算式の数字を文字や記号に置き換えて、それを元の数字に戻すパズルを「覆面算」といいます。異なる文字は異なる数字を表し、同じ文字は同じ数字を表します。使用する数字は 0 から 9 までで、最上位の桁に 0 を入れることはできません。
S E N D
+ M O R E
-------------
M O N E Y
図 : 覆面算
問題２はデュードニーが 1924 年に発表したもので、覆面算の古典といわれる有名なパズルです。
皆さんお馴染みの「魔方陣 (Magic square)」です。
┌─┬─┬─┐ 式
│Ａ│Ｂ│Ｃ│ 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 までの数字をひとつずつ配置します。縦横斜めの合計が等しくなるように数字を配置してください。
ナイト (騎士) はチェスの駒のひとつで将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。
┌─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┐
│ │●│ │●│ │ │Ｋ│ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│●│ │ │ │●│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│ │ │Ｋ│ │ │ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│●│ │ │ │●│ │ │ │ │ │ │
├─┼─┼─┼─┼─┤ ├─┼─┼─┼─┼─┤
│ │●│ │●│ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
● : ナイト (K) が動ける位置 問題
問題 4 : 騎士の巡歴
このナイトを動かして、N 行 M 列の盤面のどのマスにもちょうど一回ずつ訪れるような経路を求めるのが問題です。ちなみに、3 行 3 列、4 行 4 列の盤面には解がありませんが、5 行 5 列の盤面には解があります。今回は 5 行 5 列の盤面でナイトの移動経路の総数を求めてください。
ライツアウトは光っているボタンをすべて消すことが目的のパズルです。ルールはとても簡単です。あるボタンを押すと、そのボタンと上下左右のボタンの状態が反転します。つまり、光っているボタンは消灯し、消えていたボタンは点灯します。次の図を見てください。
□□□□□ □□□□□ 1 2 3 4 5
□□□□□ □□■□□ 6 7 8 9 10
□□□□□ ─→ □■■■□ 11 12 13 14 15
□□□□□ □□■□□ 16 17 18 19 20
□□□□□ □□□□□ 21 22 23 24 25
中央のボタンを押した場合 盤面
図 : ライツアウトの点灯パターン
ボタンは 5 行 5 列に配置されています。図に示したように、中央のボタン 13 を押すと、そのボタンと上下左右のボタンの状態が反転します。ライトが全部点灯している状態で、ライトを全部消灯するボタンの押し方をすべて求めてください。
拙作のページ「組み合わせと順列」で作成した関数 permutation() を使うと、プログラムは次のようになります。
リスト : 小町分数の解法
function check1(xs)
a, b, c, d, e, f, g, h, i = xs
x = Rational(a, b * 10 + c)
y = Rational(d, e * 10 + f)
z = Rational(g, h * 10 + i)
r = x + y + z
if numerator(r) == 1
@printf("%d/%d%d + %d/%d%d + %d/%d%d = 1/%d\n", xs..., denominator(r))
end
end
komachi() = permutation(check1, 9, collect(1 : 9))
permutation() で順列を生成し、関数 check1() で条件を満たしているかチェックします。本当に単純な生成検定法です。check1() は分数を生成して小町分数を計算します。分数の分子は関数 numerator() で、分母は denominator() で取得することができます。分子が 1 であれば条件を満たしているので、@printf で式を表示します。
それでは実行してみましょう。
julia> komachi() 1/24 + 3/56 + 7/98 = 1/6 1/24 + 7/98 + 3/56 = 1/6 1/26 + 5/39 + 7/84 = 1/4 ・・・省略・・・ 9/81 + 6/72 + 3/54 = 1/4 9/84 + 1/56 + 3/72 = 1/6 9/84 + 3/72 + 1/56 = 1/6
重複解をチェックしていないので多数の解が出力されます。そこで、分子の数字を a < d < g と限定することで、重複解を生成しないように工夫しましょう。このチェックを permutation() で行うと枝刈りの効果で実行時間も速くなります。プログラムは次のようになります。
リスト : 重複解の排除
# xs の中から n 個を選ぶ順列
# 枝刈り用の関数を引数 check で受け取る
function permutation(fn, n, xs, check = (_) -> true)
ys::typeof(xs) = []
function perm()
if !check(ys) return end
if length(ys) == n
fn(ys)
else
for x = xs
if x in ys continue end
push!(ys, x)
perm()
pop!(ys)
end
end
end
perm()
end
# 重複解の排除
function cut1(xs)
n = length(xs)
if n == 4
xs[1] < xs[4]
elseif n == 7
xs[4] < xs[7]
else
true
end
end
komachi1() = permutation(check1, 9, collect(1 : 9), cut1)
まず permutation() で枝刈り用の関数を受け取る引数 check を用意します。デフォルト値は無条件で true を返す関数です。この関数には生成途中の順列を渡します。関数 cut1() は、順列 xs の長さ n が 4 ならば xs[1] と xs[4] を比較し、n が 7 ならば xs[4] と xs[7] を比較します。あとは permutation() に cut1() を渡すだけです。
それでは実行してみましょう。
julia> komachi1() 1/24 + 3/56 + 7/98 = 1/6 1/26 + 5/39 + 7/84 = 1/4 1/32 + 5/96 + 7/84 = 1/6 1/38 + 2/95 + 4/76 = 1/10 1/48 + 5/32 + 7/96 = 1/4 1/56 + 3/72 + 9/84 = 1/6 1/96 + 5/32 + 7/84 = 1/4 1/96 + 5/48 + 7/32 = 1/3 2/18 + 5/63 + 7/49 = 1/3 2/19 + 4/57 + 6/38 = 1/3 3/27 + 6/54 + 9/81 = 1/3 3/48 + 5/16 + 9/72 = 1/2 3/54 + 6/72 + 9/81 = 1/4 5/34 + 7/68 + 9/12 = 1/1
結果は全部で 14 通りになりました。
式 SEND + MORE = MONEY は足し算なので、M が 1 であることはすぐにわかります。ここでは、それ以外の数字を求めるプログラムを作ります。単純な生成検定法でプログラムを作ると、次のようになります。
リスト : 覆面算 SEND + MORE =MONEY
function check2(xs)
m = 1
s, e, n, d, o, r, y = xs
send = s * 1000 + e * 100 + n * 10 + d
more = m * 1000 + o * 100 + r * 10 + e
money = m * 10000 + o * 1000 + n * 100 + e * 10 + y
if send + more == money
@printf("%d + %d = %d", send, more, money)
end
end
hukumenzan() = permutation(check2, 7, [0, 2, 3, 4, 5, 6, 7, 8, 9])
関数 check2() で数値 send, more, money を計算して、send + more = money を満たしているかチェックするだけです。とても簡単なプログラムですね。さっそく実行してみましょう。
julia> hukumenzan() 9567 + 1085 = 10652
答えは 9567 + 1085 = 10652 の 1 通りしかありません。興味のある方は、ほかの方法でも試してみてください。
3 行 3 列の魔方陣は生成検定法で簡単に解くことができます。次のリストを見てください。
リスト : 魔方陣 (3 行 3 列盤)
# 盤面
# 1 2 3
# 4 5 6
# 7 8 9
# 直線を表す配列
lines = [
[1, 2, 3], [4, 5, 6], [7, 8, 9],
[1, 4, 7], [2, 5, 8], [3, 6, 9],
[1, 5, 9], [3, 5, 7]
]
function check3(xs)
values = [xs[x] + xs[y] + xs[z] for (x, y, z) = lines]
if all(isequal(values[1]), values)
@printf("%d %d %d\n", xs[1 : 3]...)
@printf("%d %d %d\n", xs[4 : 6]...)
@printf("%d %d %d\n\n", xs[7 : 9]...)
end
end
magicsquare() = permutation(check3, 9, collect(1 : 9))
関数 permutation() で 1 から 9 までの数字の順列を生成します。それを関数 check に渡して、魔方陣の条件を満たしているかチェックします。内包表記で各直線の和を求めて、すべて同じ値であれば魔方陣の条件を満たすので、@printf で盤面 xs を表示します。
それでは実行結果を示します。
julia> magicsquare() 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
対称解を含めると、解は 8 通りあります。最近のパソコンはハイスペックなので、このままでも高速に解けるのですが、対称解を排除すると枝刈りの効果により、実行時間はもう少し速くなります。
対称解のチェックは、下図のように四隅の大小関係を利用すると簡単です。
┌─┬─┬─┐
│Ａ│Ｂ│Ｃ│
├─┼─┼─┤ A < C < G
│Ｄ│Ｅ│Ｆ│
├─┼─┼─┤ A < I
│Ｇ│Ｈ│Ｉ│
└─┴─┴─┘
図 : 対称解のチェック
魔方陣の場合、回転解が 4 種類あって、鏡像解が 2 種類あります。四隅の大小関係をチェックすることで、これらの対称解を排除することができます。プログラムは次のようになります。
リスト : 重複解の排除
# 枝刈り用
function cut3(xs)
n = length(xs)
if n == 3
xs[1] < xs[3]
elseif n == 7
xs[3] < xs[7]
elseif n == 9
xs[1] < xs[9]
else
true
end
end
magicsquare1() = permutation(check3, 9, collect(1 : 9), cut3)
実行結果を示します。
julia> magicsquare1() 2 9 4 7 5 3 6 1 8
それではプログラムを作りましょう。盤面は 2 次元配列で表すことにします。この場合、騎士の移動手順は 5 行 5 列の盤面に記録したほうが簡単です。騎士が訪れていないマスを 0 とし、騎士の移動手順を 1 から始めれば、移動できるマスの判定を簡単に行うことができます。また、経路の出力も盤面を表示した方が直感的でわかりやすいかもしれません。
次は盤面の構成を考えましょう。単純な 5 行 5 列の 2 次元配列にすると、騎士が盤面から飛び出さないようにするため座標の範囲チェックが必要になります。このような場合、盤面の外側に壁を設定するとプログラムが簡単になります。
騎士は最大で 2 マス移動するので、壁の厚さも 2 マス用意します。したがって、盤面を表す配列は 9 行 9 列の大きさになります。壁に 0 以外の値 (1) を設定しておけば、騎士が盤面から飛び出して壁の位置に移動しようとしても、盤面の値が 0 ではないので実際に移動することはできません。これで騎士を移動したときの範囲チェックを省略することができます。
リスト : 騎士の巡歴
# 盤面の初期化
function init_board()
board = fill(1, 9, 9)
for i = 3 : 7, j = 3 : 7
board[i, j] = 0
end
board[3, 3] = 1
board
end
# 移動
dx = [1, 2, 2, 1, -1, -2, -2, -1]
dy = [-2, -1, 1, 2, 2, 1, -1, -2]
# 盤面の表示
function print_board(board)
global cnt += 1
for i = 3 : 7
for j = 3 : 7
@printf "%2d " board[i, j]
end
println("")
end
println("")
end
# 解法
function solver(board, n, x, y)
if n > 25
print_board(board)
else
for i = 1 : 8
x1 = x + dx[i]
y1 = y + dy[i]
if board[x1, y1] == 0
board[x1, y1] = n
solver(board, n + 1, x1, y1)
board[x1, y1] = 0
end
end
end
end
function knight()
global cnt = 0
solver(init_board(), 2, 3, 3)
println(cnt)
end
配列 dx は騎士の x 方向の変位、配列 dy は y 方向の変位を表します。現在の座標にこの値を加えることで、次の座標を決定します。配列 board は盤面を表します。関数 init_board() で、壁の部分は 1 に、実際の盤面は 0 に初期化しておきます。
関数 solver() は引数として手数 n と騎士の座標 x, y を受け取ります。まず、n が 25 よりも大きくなったかチェックします。そうであれば、騎士はすべてのマスを訪れたので、print_board() で盤面を出力します。
そうでなければ、次に移動するマスを選びます。for 文で dx と dy の要素を取り出して x と y の値に加え、solver() を再帰呼び出しします。再帰呼び出しから戻ってきたら、board[x1, y1] の値を 0 に戻すことをお忘れなく。あとはとくに難しいところはないと思います。
julia> knight() 1 16 21 10 25 20 11 24 15 22 17 2 19 6 9 12 7 4 23 14 3 18 13 8 5 ・・・省略・・・ 1 16 11 6 3 10 5 2 17 12 15 22 19 4 7 20 9 24 13 18 23 14 21 8 25 304
解は全部で 304 通りあります。
ライツアウトはボタンを押すと、そのボタンと上下左右のボタンの状態が反転します。もう一度同じボタンを押すと、再度ボタンの状態が反転するので、元の状態に戻ります。つまり、ライツアウトでは「同じボタンは二度押さなくてよい」ことがわかります。
また、実際にボタンを押してみるとわかりますが、「ボタンを押す順番は関係がない」ことがわかります。たとえば、ボタン A と B を押す場合、A -> B と押すのも、B -> A と押したのも、同じ結果になります。
この 2 つの法則から、ボタンを押す組み合わせは全部で 2 ^ 25 (2 の 25 乗)、約 32 万通りになります。この組み合わせを生成して、ライトが全部消えるかチェックすればいいわけです。
これをそのままプログラムすると、次のようになります。
リスト : ライツアウトの解法
# パターンを作る
function make_pattern()
a = []
for i = 0 : 24
x = i % 5
y = div(i, 5)
d = [(0, -1), (-1, 0), (0, 0), (1, 0), (0, 1)]
push!(a, [(y + dy) * 5 + x + dx + 1 for (dx, dy) = d if 0 <= x + dx <= 4 && 0 <= y + dy <= 4])
end
a
end
# ボタンを押す
push_button(xs, n, pattern) = foreach(x -> xs[x] = xor(xs[x], 1), pattern[n])
# ライツアウトを解く
function lightsout(board)
table = make_pattern()
ans = Vector{Int}[]
if iszero(board) return ans end
for i = 1 : 25
combination(i, collect(1 : 25)) do buttons
xs = copy(board)
foreach(b -> push_button(xs, b, table), buttons)
if iszero(xs)
push!(ans, copy(buttons))
end
end
end
return ans
end
盤面は Int 型の 1 次元配列で表します。1 が点灯を、0 が消灯を表します。配列の添字がボタンの番号になります。関数 make_pattern() はボタンを押したときに反転するボタンの位置を格納した配列を生成します。関数 push_button() はボタン n を押したとき、盤面 xs のライトの状態を更新します。ライトの反転は排他的論理和 (xor) を使えば簡単に実装できます。
ライツアウトの解法は関数 lightsout() で行います。最初に make_pattern() でパターンを生成して変数 table にセットします。見つけた解は配列 ans に格納します。board がすべて 0 の場合は return で ans を返します。
iszero(x) は引数が 0 の場合は true を返す関数です。引数が配列の場合、要素がすべて 0 の場合は true を返します。Julia には zero(x) という関数もあって、引数 x と同じ型の 0 を返します。簡単な例を示しましょう。
julia> iszero(0)
true
julia> iszero(1)
false
julia> iszero(0.0)
true
julia> iszero(1.0)
false
julia> iszero([0, 0, 0, 0])
true
julia> iszero([0, 0, 0, 1])
false
julia> zero(10)
0
julia> zero(1.234)
0.0
julia> zero([1, 2, 3, 4])
4-element Array{Int64,1}:
0
0
0
0
次の for ループで、押すボタンの個数を 1 から順番に増やしていきます。ボタンの組み合わせは拙作のページ「組み合わせと順列」で作成した関数 combination() を使います。ブロックの引数 buttons には選んだボタンを格納した配列が渡されます。
ブロックの中では board をコピーして変数 xs にセットします。次の foreach() で、buttons に格納されているボタンを push_button() で押します。そして、xs がすべて 0 になったか iszero() でチェックします。ライトがすべて消えていれば buttons をコピーして配列 ans に格納します。最後に ans を返します。
それでは実行してみましょう。ライトが全部点灯している状態を解いてみます。実行結果は次のようになりました。
julia> @time lightsout(fill(1, 25))
19.246514 seconds (453.05 M allocations: 14.254 GiB, 0.69% gc time, 0.43% compilation time)
4-element Vector{Vector{Int64}}:
[1, 2, 6, 7, 9, 10, 13, 14, 15, 17, 18, 19, 22, 23, 25]
[1, 3, 4, 7, 8, 9, 11, 12, 13, 16, 17, 19, 20, 24, 25]
[2, 3, 5, 7, 8, 9, 13, 14, 15, 16, 17, 19, 20, 21, 22]
[4, 5, 6, 7, 9, 10, 11, 12, 13, 17, 18, 19, 21, 23, 24]
実行環境 : Julia ver 1.10.5, Ubuntu 22.04 (WSL2), Intel Core i5-6200U 2.30GHz
4 通りの解が出力されました。ボタンを押した回数は、どの解も 15 回になりました。 実は、これがライツアウトの最長手数なのです。ライツアウトの場合、ライトの点灯パターンは 2 ^ 25 = 33554432 通りありますが、実際に解が存在するパターンは、その 1 / 4 の 8388608 通りしかありません。その中で最短回数が 15 回で解けるパターンは 7350 通りあり、そのうちのひとつが、ライトが全部点灯しているパターンなのです。
実行時間はとても遅いですね。実は、もっと簡単で高速な方法があるのです。
ライツアウトは次の図に示すように、ボタンを上から 1 行ずつ消灯していくという、わかりやすい方法で解くことができます。
ＡＢＣＤＥ ＡＢＣＤＥ ＡＢＣＤＥ ＡＢＣＤＥ
１□■□■□ １□□□□□ １□□□□□ １□□□□□
２□□□□□ ２■■□■■ ２□□□□□ ２□□□□□
３□□□□□ ３□■□■□ ３□■□■□ ３□□□□□
４□□□□□ ４□□□□□ ４■■□■■ ４□□□□□
５□□□□□ ５□□□□□ ５□□□□□ ５□■□■□
（１） （２） （３） （４）
図 : 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 通り調べるだけで、ライツアウトの解を求めることができます。
プログラムは次のようになります。
リスト : ライツアウトの高速化
function lightsout1(board)
table = make_pattern()
ans = Vector{Int}[]
if iszero(board) return ans end
for i = 1 : 5
combination(i, collect(1 : 5)) do buttons
xs = copy(board)
bs = copy(buttons)
foreach(b -> push_button(xs, b, table), buttons)
for j = 6 : 25
if xs[j - 5] == 1
push!(bs, j)
push_button(xs, j, table)
end
end
if iszero(xs)
push!(ans, bs)
end
end
end
ans
end
ボタンは 1 から 5 の中から選んで組み合わせを生成します。あとはブロックの中の for ループで、 盤面の 2 行目 (6 番目) から順番に上のライトが付いているかチェックし、そうであればボタンを押していくだけです。
それでは実行してみましょう。
julia> @time lightsout1(fill(1,25))
0.032761 seconds (13.10 k allocations: 861.828 KiB, 99.73% compilation time)
4-element Vector{Vector{Int64}}:
[1, 2, 6, 7, 9, 10, 13, 14, 15, 17, 18, 19, 22, 23, 25]
[4, 5, 6, 7, 9, 10, 11, 12, 13, 17, 18, 19, 21, 23, 24]
[1, 3, 4, 7, 8, 9, 11, 12, 13, 16, 17, 19, 20, 24, 25]
[2, 3, 5, 7, 8, 9, 13, 14, 15, 16, 17, 19, 20, 21, 22]
0.1 秒もかからずに解くことができました。500 倍以上の高速化に成功しました。
このほかに、高橋謙一郎さんの「コンピュータ＆パズル」では、細江万太郎さんが考案されたライツアウトを連立方程式で解く方法が紹介されています。拙作のページ「お気楽 NumPy プログラミング超入門: 連立一次方程式の解法 (2)」でもライツアウトを連立方程式で解いています。興味のある方はお読みくださいませ。
#
# puzzle1.jl : Puzzle DE Julia!! 生成検定法編
#
# Copyright (C) 2018-2021 Makoto Hiroi
#
using Printf
# xs の中から n 個を選ぶ順列
function permutation(fn, n, xs, check = (_) -> true)
ys::typeof(xs) = []
function perm()
if !check(ys) return end
if length(ys) == n
fn(ys)
else
for x = xs
if x in ys; continue; end
push!(ys, x)
perm()
pop!(ys)
end
end
end
perm()
end
# xs の中から n 個を選ぶ組み合わせ
function combination(fn, n, xs)
ys::typeof(xs) = []
function comb(m)
if length(ys) == n
fn(ys)
elseif length(xs) - m + 1 >= n - length(ys)
push!(ys, xs[m])
comb(m + 1)
pop!(ys)
comb(m + 1)
end
end
comb(1)
end
#
# 小町分数
#
function check1(xs)
a, b, c, d, e, f, g, h, i = xs
x = Rational(a, b * 10 + c)
y = Rational(d, e * 10 + f)
z = Rational(g, h * 10 + i)
r = x + y + z
if numerator(r) == 1
@printf("%d/%d%d + %d/%d%d + %d/%d%d = 1/%d\n", xs..., denominator(r))
end
end
komachi() = permutation(check1, 9, collect(1:9))
# 重複解の排除
function cut1(xs)
n = length(xs)
if n == 4
xs[1] < xs[4]
elseif n == 7
xs[4] < xs[7]
else
true
end
end
komachi1() = permutation(check1, 9, collect(1:9), cut1)
#
# 覆面算: SEND + MORE = MONEY
#
function check2(xs)
m = 1
s, e, n, d, o, r, y = xs
send = s * 1000 + e * 100 + n * 10 + d
more = m * 1000 + o * 100 + r * 10 + e
money = m * 10000 + o * 1000 + n * 100 + e * 10 + y
if send + more == money
@printf("%d + %d = %d", send, more, money)
end
end
hukumenzan() = permutation(check2, 7, [0, 2, 3, 4, 5, 6, 7, 8, 9])
#
# 魔方陣
#
# 盤面
# 1 2 3
# 4 5 6
# 7 8 9
# 直線を表す配列
lines = [
[1, 2, 3], [4, 5, 6], [7, 8, 9],
[1, 4, 7], [2, 5, 8], [3, 6, 9],
[1, 5, 9], [3, 5, 7]
]
function check3(xs)
values = [xs[x] + xs[y] + xs[z] for (x, y, z) = lines]
if all(isequal(values[1]), values)
@printf("%d %d %d\n", xs[1 : 3]...)
@printf("%d %d %d\n", xs[4 : 6]...)
@printf("%d %d %d\n\n", xs[7 : 9]...)
end
end
magicsquare() = permutation(check3, 9, collect(1 : 9))
# 重複解の排除
function cut3(xs)
n = length(xs)
if n == 3
xs[1] < xs[3]
elseif n == 7
xs[3] < xs[7]
elseif n == 9
xs[1] < xs[9]
else
true
end
end
magicsquare1() = permutation(check3, 9, collect(1 : 9), cut3)
#
# 騎士の巡歴
#
# 盤面の初期化
function init_board()
board = fill(1, 9, 9)
for i = 3 : 7, j = 3 : 7
board[i, j] = 0
end
board[3, 3] = 1
board
end
# 移動
dx = [1, 2, 2, 1, -1, -2, -2, -1]
dy = [-2, -1, 1, 2, 2, 1, -1, -2]
# 盤面の表示
function print_board(board)
global cnt += 1
for i = 3 : 7
for j = 3 : 7
@printf "%2d " board[i, j]
end
println("")
end
println("")
end
# 解法
function solver4(board, n, x, y)
if n > 25
print_board(board)
else
for i = 1 : 8
x1 = x + dx[i]
y1 = y + dy[i]
if board[x1, y1] == 0
board[x1, y1] = n
solver4(board, n + 1, x1, y1)
board[x1, y1] = 0
end
end
end
end
function knight()
global cnt = 0
solver4(init_board(), 2, 3, 3)
println(cnt)
end
#
# ライツアウト
#
# 盤面
# 1 2 3 4 5
# 6 7 8 9 10
# 11 12 13 14 15
# 16 17 18 19 20
# 21 22 23 24 25
# 押下パターンを作る
function make_pattern()
a = []
for i = 0 : 24
x = i % 5
y = div(i, 5)
d = [(0, -1), (-1, 0), (0, 0), (1, 0), (0, 1)]
push!(a, [(y + dy) * 5 + x + dx + 1 for (dx, dy) = d if 0 <= x + dx <= 4 && 0 <= y + dy <= 4])
end
a
end
# ボタンを押す
push_button(xs, n, pattern) = foreach(x -> xs[x] = xor(xs[x], 1), pattern[n])
function lightsout(board)
table = make_pattern()
ans = Vector{Int}[]
if iszero(board) return ans end
for i = 1 : 25
combination(i, collect(1 : 25)) do buttons
xs = copy(board)
foreach(b -> push_button(xs, b, table), buttons)
if iszero(xs)
push!(ans, copy(buttons))
end
end
end
return ans
end
# 高速化
function lightsout1(board)
table = make_pattern()
ans = Vector{Int}[]
if iszero(board) return ans end
for i = 1 : 5
combination(i, collect(1 : 5)) do buttons
xs = copy(board)
bs = copy(buttons)
foreach(b -> push_button(xs, b, table), buttons)
for j = 6 : 25
if xs[j - 5] == 1
push!(bs, j)
push_button(xs, j, table)
end
end
if iszero(xs)
push!(ans, bs)
end
end
end
ans
end