「ナイト・ツアー」の解を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