「ナイト・ツアー」の解をruby 60行でコーディング
年末でやらなきゃいけないことがあるにもかかわらず、スラッシュドットをぼーっと見てたら、面白そうな話を見つけました。
本家/.のttsiod氏は、このパズルの解をPythonで60行のコードで書いたそうだ。「100×100マスのボードでも1秒足らずで解を出せる」とのこと
「ナイト・ツアー」の解をPython 60行でコーディング | スラッシュドット・ジャパン
ナイト・ツアーってのは、騎士の巡歴とも呼ばれる、チェスをモチーフにしたパズルのことです。で、、、
「詰まってる仕事がある」→「現実逃避で ruby で遊ぶ」
というコンボが発動し、元サイトにある高速で解を求める 60 行の python スクリプトを ruby で書いてみました。まぁまんま Pythonのコードをパクってるだけですが、、、。
# -*- coding: utf-8 -*- require 'pp' class Array def sum self.inject(0) {|r, i| r += i } end end class KnightTour attr_reader :board def initialize(size) @board = [] @square_size = size end def in_range_and_empty(ty, tx) ty>=0 && tx>=0 && ty<@square_size && tx<@square_size && @board[ty][tx] == 0 end def fill(y, x, counter) @board[y][x] = counter exit 0 if counter == @square_size ** 2 empty_neighbours = [] jumps = [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]] jumps.each do |jump| ty, tx = y + jump[0], x + jump[1] empty_neighbours << [ty, tx] if in_range_and_empty(ty, tx) end empty_neighbours.sort_by {|v| jumps.map {|j| in_range_and_empty(v[0]+j[0], v[1]+j[1]) ? 1 : 0 }.sum }.each do |ty, tx| fill(ty, tx, counter+1) end @board[y][x] = 0 end def init_board 1.upto(@square_size) {|i| @board << [0] * @square_size } end def self.start(size) k = self.new(size) k.init_board k.fill(0, 0, 1) rescue SystemExit pp k.board else puts "no solution." end end if $0 == __FILE__ if ARGV[0].to_i == 0 puts "Usage: #{$0} <square size>" exit 0 end KnightTour.start(ARGV[0].to_i) end
狙ったわけじゃないけど、ruby でもちょうど 60 行になったw
さっそく 10x10 マスの解を出してみました。
/Users/kenkiti/% ruby knight_tour.rb 10 [[1, 38, 17, 42, 3, 36, 57, 48, 5, 34], [18, 41, 2, 37, 94, 49, 4, 35, 58, 47], [39, 16, 99, 50, 43, 56, 95, 60, 33, 6], [52, 19, 40, 93, 98, 91, 44, 63, 46, 59], [15, 100, 51, 90, 55, 96, 61, 86, 7, 32], [20, 53, 78, 97, 92, 87, 64, 45, 62, 71], [79, 14, 89, 54, 83, 76, 85, 72, 31, 8], [24, 21, 82, 77, 88, 73, 28, 65, 70, 67], [13, 80, 23, 26, 11, 84, 75, 68, 9, 30], [22, 25, 12, 81, 74, 27, 10, 29, 66, 69]]
おお一瞬で解がでた、はやい。ちなみに遅い方のスクリプトだと数十秒かかりました。一つ手を先読みして、動ける場所が多いルートから順に探索する、って処理を入れるだけで、こんなに速くなるんだなあ。。。ちょっと感動。
しかし、このrubyスクリプト、31x31 で探索すると、stack level too deep (SystemStackError) って出ちゃった。だめぽ。。。
追記
色々調べてたら、ruby は Cスタックを使っているので、SystemStackError を回避するには ulimit で stack size を増やせばよいそうな。そんなわけで 31x31 マスを再試。ちなみに stack を増やしても、100x100は無理でした。残念。
/Users/kenkiti/work% ulimit -aH -t: cpu time (seconds) unlimited -f: file size (blocks) unlimited -d: data seg size (kbytes) unlimited -s: stack size (kbytes) 65532 -c: core file size (blocks) unlimited -v: address space (kb) unlimited -l: locked-in-memory size (kb) unlimited -u: processes 532 -n: file descriptors unlimited /Users/kenkiti/work% ulimit -s 65532 /Users/kenkiti/work% time ruby knight_tour.rb 31 ruby knight_tour.rb 31 0.67s user 0.26s system 87% cpu 1.067 total