●解答１
拙作のページ 組み合わせと順列 で作成した関数 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 通りあります。最近のパソコンはハイスペックなので、このままでも高速に解けるのですが、対称解を排除すると枝刈りの効果により、実行時間はもう少し速くなります。
●対称解の排除
対称解のチェックは、下図のように四隅の大小関係を利用すると簡単です。
図 : 対称解のチェック
魔方陣の場合、回転解が 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))
26.791192 seconds (453.02 M allocations: 15.252 GiB, 3.37% gc time, 0.26% 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.6.4, Ubuntu 18.04 (WSL), 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.042718 seconds (42.17 k allocations: 2.453 MiB, 99.67% 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]
実行環境 : Julia ver 1.6.4, Ubuntu 18.04 (WSL), Intel Core i5-6200U 2.30GHz
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
2021/12/05 改訂: Julia のバージョンを 1.6 に変更
図 : 魔方陣
問題 4 : 騎士の巡歴
