タイトルが長い(´・ω・｀) ただこう書くほかない(´・ω・｀) 掲題の通りTECH PLAY「定番のアルゴリズムは退屈？アルゴリズムをもっと楽しく学ぼう！」に掲載されているアルゴリズム問題を解いてみました。解答内容は自由に公開してよいとのことなので、せっかくですし、Qiitaにさらしてみたいと思います。
詳細な問題内容は当該記事を見ていただきたいのですが、おおよその内容としては「3x3の魔法陣を生成する。魔法陣を構成する数字はnからn+8まで(nは1以上10以下)」というものです。まず思いつくのは「考えうるすべての盤面を生成して、そのうち条件を満たすものだけをpickupする」という解法でしょうか。要は全探索するわけです。
wrong.rb
#
# 考えうる魔法陣をすべて生成して、そのうち条件を満たすものだけをpickupする。
# @param n 問題文にある"n"(1..10)
# @return 条件を満たす魔法陣の一覧
#
def solve(n)
[*n..(n + 8)].permutation.with_object([]) do |digits, squares|
square = digits.each_slice(3).to_a
totals = [
*square.map(&:sum), # 縦方向
*square.transpose.map(&:sum), # 横方向
(0...3).map{|x| square[x][x]}.sum, # 右ななめ
(0...3).map{|x| square[x][2 - x]}.sum # 左ななめ
]
squares << square if totals.uniq.length == 1
end
end
#
# 3x3の魔法陣をpretty-printする。
# 補助関数=メインロジックには無関係。
#
def pprint(squares)
(0...3).each do |x|
rows = squares.map{|square| square[x]}
puts rows.map{|row|
row.map{|digit| format("%02d", digit)}.join(',')
}.join(' | ')
end
end
if __FILE__ == $0
(1..10).each do |n|
squares = solve(n)
puts "[ n=#{n} ]"
pprint(squares)
end
end
この実行結果が以下の通り。
$ time ruby wrong.rb
[ n=1 ]
02,07,06 | 02,09,04 | 04,03,08 | 04,09,02 | 06,01,08 | 06,07,02 | 08,01,06 | 08,03,04
09,05,01 | 07,05,03 | 09,05,01 | 03,05,07 | 07,05,03 | 01,05,09 | 03,05,07 | 01,05,09
04,03,08 | 06,01,08 | 02,07,06 | 08,01,06 | 02,09,04 | 08,03,04 | 04,09,02 | 06,07,02
[ n=2 ]
03,08,07 | 03,10,05 | 05,04,09 | 05,10,03 | 07,02,09 | 07,08,03 | 09,02,07 | 09,04,05
10,06,02 | 08,06,04 | 10,06,02 | 04,06,08 | 08,06,04 | 02,06,10 | 04,06,08 | 02,06,10
05,04,09 | 07,02,09 | 03,08,07 | 09,02,07 | 03,10,05 | 09,04,05 | 05,10,03 | 07,08,03
[ n=3 ]
04,09,08 | 04,11,06 | 06,05,10 | 06,11,04 | 08,03,10 | 08,09,04 | 10,03,08 | 10,05,06
11,07,03 | 09,07,05 | 11,07,03 | 05,07,09 | 09,07,05 | 03,07,11 | 05,07,09 | 03,07,11
06,05,10 | 08,03,10 | 04,09,08 | 10,03,08 | 04,11,06 | 10,05,06 | 06,11,04 | 08,09,04
[ n=4 ]
05,10,09 | 05,12,07 | 07,06,11 | 07,12,05 | 09,04,11 | 09,10,05 | 11,04,09 | 11,06,07
12,08,04 | 10,08,06 | 12,08,04 | 06,08,10 | 10,08,06 | 04,08,12 | 06,08,10 | 04,08,12
07,06,11 | 09,04,11 | 05,10,09 | 11,04,09 | 05,12,07 | 11,06,07 | 07,12,05 | 09,10,05
[ n=5 ]
06,11,10 | 06,13,08 | 08,07,12 | 08,13,06 | 10,05,12 | 10,11,06 | 12,05,10 | 12,07,08
13,09,05 | 11,09,07 | 13,09,05 | 07,09,11 | 11,09,07 | 05,09,13 | 07,09,11 | 05,09,13
08,07,12 | 10,05,12 | 06,11,10 | 12,05,10 | 06,13,08 | 12,07,08 | 08,13,06 | 10,11,06
[ n=6 ]
07,12,11 | 07,14,09 | 09,08,13 | 09,14,07 | 11,06,13 | 11,12,07 | 13,06,11 | 13,08,09
14,10,06 | 12,10,08 | 14,10,06 | 08,10,12 | 12,10,08 | 06,10,14 | 08,10,12 | 06,10,14
09,08,13 | 11,06,13 | 07,12,11 | 13,06,11 | 07,14,09 | 13,08,09 | 09,14,07 | 11,12,07
[ n=7 ]
08,13,12 | 08,15,10 | 10,09,14 | 10,15,08 | 12,07,14 | 12,13,08 | 14,07,12 | 14,09,10
15,11,07 | 13,11,09 | 15,11,07 | 09,11,13 | 13,11,09 | 07,11,15 | 09,11,13 | 07,11,15
10,09,14 | 12,07,14 | 08,13,12 | 14,07,12 | 08,15,10 | 14,09,10 | 10,15,08 | 12,13,08
[ n=8 ]
09,14,13 | 09,16,11 | 11,10,15 | 11,16,09 | 13,08,15 | 13,14,09 | 15,08,13 | 15,10,11
16,12,08 | 14,12,10 | 16,12,08 | 10,12,14 | 14,12,10 | 08,12,16 | 10,12,14 | 08,12,16
11,10,15 | 13,08,15 | 09,14,13 | 15,08,13 | 09,16,11 | 15,10,11 | 11,16,09 | 13,14,09
[ n=9 ]
10,15,14 | 10,17,12 | 12,11,16 | 12,17,10 | 14,09,16 | 14,15,10 | 16,09,14 | 16,11,12
17,13,09 | 15,13,11 | 17,13,09 | 11,13,15 | 15,13,11 | 09,13,17 | 11,13,15 | 09,13,17
12,11,16 | 14,09,16 | 10,15,14 | 16,09,14 | 10,17,12 | 16,11,12 | 12,17,10 | 14,15,10
[ n=10 ]
11,16,15 | 11,18,13 | 13,12,17 | 13,18,11 | 15,10,17 | 15,16,11 | 17,10,15 | 17,12,13
18,14,10 | 16,14,12 | 18,14,10 | 12,14,16 | 16,14,12 | 10,14,18 | 12,14,16 | 10,14,18
13,12,17 | 15,10,17 | 11,16,15 | 17,10,15 | 11,18,13 | 17,12,13 | 13,18,11 | 15,16,11
real 0m34.338s
user 0m33.750s
sys 0m0.203s
わたしの環境ではプログラム実行から結果が返ってくるまでおよそ35秒かかっています。9!=362880通りの盤面を探索する必要があるので、これぐらいの時間がかかってしまうのは仕方がない--というよりは35万件以上探索してもこの程度の時間で済むという印象のほうが強いかも(´・ω・｀)
それはさておき、もう少し効率の良いアルゴリズムを考えてみます。たとえばn=1のときは15というように、1列の合計値は事前に求めることができます。つまり1列のうち2マスまで決まれば、最後の1マスは自動で決まります。よって「最後の1マスに数字を設定する際、縦/横/ななめ方向に合計値の検査を行って、条件を満たさない場合はその時点で探索をやめる」という枝刈りを実施すれば、単純な全探索よりは探索量が減るはずです。それを実装したものが以下のコードになります。
main.rb
#
# 幅優先探索で、条件を満たす魔法陣を探す。
# 「探索中にその魔法陣が条件を満たすかどうかをチェックし、
# 満たさない場合は探索をやめる」という枝刈りを行って、探索量を減らす。
# @param n 問題文にある"n"(1..10)
# @return 条件を満たす魔法陣の一覧
#
def solve(n)
lo, hi = n, n + 8
total = (lo..hi).sum / 3
queue = (lo..hi).map do |digit|
square = Array.new(3){ Array.new(3, 0) }
square[0][0] = digit
square
end
squares = []
until queue.empty?
square = queue.shift
# 数字が未設置の座標を探す。未設置の座標がない場合はその魔法陣が条件を満たすということ。
x, y = [*0...3].product([*0...3]).find{|i, j| square[i][j] == 0}
if x.nil? && y.nil?
squares << square
next
end
# 座標(x, y)に置くことができるのは、その魔法陣においていまだ利用されていない数字。
# ただし底辺や右辺の座標の場合は、縦方向や横方向あるいは斜め方向の検査を行っておく(=枝刈り)
digits = [*lo..hi] - square.flatten.uniq
digits.select!{|digit| square[0][y] + square[1][y] + digit == total} if x == 2 # 底辺=縦方向の検査を行う
digits.select!{|digit| square[x][0] + square[x][1] + digit == total} if y == 2 # 右辺=横方向の検査を行う
digits.select!{|digit| square[0][2] + square[1][1] + digit == total} if x == 2 && y == 0 # 左ななめ方向の検査を行う
digits.select!{|digit| square[0][0] + square[1][1] + digit == total} if x == 2 && y == 2 # 右ななめ方向の検査を行う
digits.each do |digit|
temp = square.map(&:dup)
temp[x][y] = digit
queue << temp
end
end
squares
end
#
# 3x3の魔法陣をpretty-printする。
# 補助関数=メインロジックには無関係。
#
def pprint(squares)
(0...3).each do |x|
rows = squares.map{|square| square[x]}
puts rows.map{|row|
row.map{|digit| format("%02d", digit)}.join(',')
}.join(' | ')
end
end
if __FILE__ == $0
(1..10).each do |n|
squares = solve(n)
puts "[ n=#{n} ]"
pprint(squares)
end
end
これを実行したものが次の通り。
$ time ruby main.rb
[ n=1 ]
02,07,06 | 02,09,04 | 04,03,08 | 04,09,02 | 06,01,08 | 06,07,02 | 08,01,06 | 08,03,04
09,05,01 | 07,05,03 | 09,05,01 | 03,05,07 | 07,05,03 | 01,05,09 | 03,05,07 | 01,05,09
04,03,08 | 06,01,08 | 02,07,06 | 08,01,06 | 02,09,04 | 08,03,04 | 04,09,02 | 06,07,02
[ n=2 ]
03,08,07 | 03,10,05 | 05,04,09 | 05,10,03 | 07,02,09 | 07,08,03 | 09,02,07 | 09,04,05
10,06,02 | 08,06,04 | 10,06,02 | 04,06,08 | 08,06,04 | 02,06,10 | 04,06,08 | 02,06,10
05,04,09 | 07,02,09 | 03,08,07 | 09,02,07 | 03,10,05 | 09,04,05 | 05,10,03 | 07,08,03
[ n=3 ]
04,09,08 | 04,11,06 | 06,05,10 | 06,11,04 | 08,03,10 | 08,09,04 | 10,03,08 | 10,05,06
11,07,03 | 09,07,05 | 11,07,03 | 05,07,09 | 09,07,05 | 03,07,11 | 05,07,09 | 03,07,11
06,05,10 | 08,03,10 | 04,09,08 | 10,03,08 | 04,11,06 | 10,05,06 | 06,11,04 | 08,09,04
[ n=4 ]
05,10,09 | 05,12,07 | 07,06,11 | 07,12,05 | 09,04,11 | 09,10,05 | 11,04,09 | 11,06,07
12,08,04 | 10,08,06 | 12,08,04 | 06,08,10 | 10,08,06 | 04,08,12 | 06,08,10 | 04,08,12
07,06,11 | 09,04,11 | 05,10,09 | 11,04,09 | 05,12,07 | 11,06,07 | 07,12,05 | 09,10,05
[ n=5 ]
06,11,10 | 06,13,08 | 08,07,12 | 08,13,06 | 10,05,12 | 10,11,06 | 12,05,10 | 12,07,08
13,09,05 | 11,09,07 | 13,09,05 | 07,09,11 | 11,09,07 | 05,09,13 | 07,09,11 | 05,09,13
08,07,12 | 10,05,12 | 06,11,10 | 12,05,10 | 06,13,08 | 12,07,08 | 08,13,06 | 10,11,06
[ n=6 ]
07,12,11 | 07,14,09 | 09,08,13 | 09,14,07 | 11,06,13 | 11,12,07 | 13,06,11 | 13,08,09
14,10,06 | 12,10,08 | 14,10,06 | 08,10,12 | 12,10,08 | 06,10,14 | 08,10,12 | 06,10,14
09,08,13 | 11,06,13 | 07,12,11 | 13,06,11 | 07,14,09 | 13,08,09 | 09,14,07 | 11,12,07
[ n=7 ]
08,13,12 | 08,15,10 | 10,09,14 | 10,15,08 | 12,07,14 | 12,13,08 | 14,07,12 | 14,09,10
15,11,07 | 13,11,09 | 15,11,07 | 09,11,13 | 13,11,09 | 07,11,15 | 09,11,13 | 07,11,15
10,09,14 | 12,07,14 | 08,13,12 | 14,07,12 | 08,15,10 | 14,09,10 | 10,15,08 | 12,13,08
[ n=8 ]
09,14,13 | 09,16,11 | 11,10,15 | 11,16,09 | 13,08,15 | 13,14,09 | 15,08,13 | 15,10,11
16,12,08 | 14,12,10 | 16,12,08 | 10,12,14 | 14,12,10 | 08,12,16 | 10,12,14 | 08,12,16
11,10,15 | 13,08,15 | 09,14,13 | 15,08,13 | 09,16,11 | 15,10,11 | 11,16,09 | 13,14,09
[ n=9 ]
10,15,14 | 10,17,12 | 12,11,16 | 12,17,10 | 14,09,16 | 14,15,10 | 16,09,14 | 16,11,12
17,13,09 | 15,13,11 | 17,13,09 | 11,13,15 | 15,13,11 | 09,13,17 | 11,13,15 | 09,13,17
12,11,16 | 14,09,16 | 10,15,14 | 16,09,14 | 10,17,12 | 16,11,12 | 12,17,10 | 14,15,10
[ n=10 ]
11,16,15 | 11,18,13 | 13,12,17 | 13,18,11 | 15,10,17 | 15,16,11 | 17,10,15 | 17,12,13
18,14,10 | 16,14,12 | 18,14,10 | 12,14,16 | 16,14,12 | 10,14,18 | 12,14,16 | 10,14,18
13,12,17 | 15,10,17 | 11,16,15 | 17,10,15 | 11,18,13 | 17,12,13 | 13,18,11 | 15,16,11
real 0m0.618s
user 0m0.406s
sys 0m0.109s
プログラム実行から同じ結果を出力するのに全探索では35秒かかっていましたが、枝刈り版では0.06秒にまで縮まっていることが分かります。上下左右対称のものを省いたり、枝刈り方法を工夫したりすれば、より効率化できそうですが、ここまで劇的な改善は難しいかもしれません(´・ω・｀)