エイト・クイーン（8 queen）問題を Ruby で解いてみる

チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。

　
チェスの盤面は 8×8 であり、クイーンのコマは前後左右斜めにどれだけでも進むことができます。盤面上に 8つのクイーンを置くとき、どのクイーンも他のいずれにも取られないような配置を考えるわけです。

最初の駒は任意に与えられるものとしましょう。また、ひとつでも解が見つかれば終了することにします。考え方としては、人間がやる場合と似て、適当に一駒ずつ置いていき、失敗すればひとつ前に戻って置き直していくという方法を取ります。いわゆる「バックトラック法」というやつです。Ruby で解いてみました。下は回答のひとつです。

$ time ruby eight_queen.rb
@.......
......@.
....@...
.......@
.@......
...@....
.....@..
..@.....

real	0m0.077s
user	0m0.044s
sys	0m0.000s

eight_queen.rb

N = 8

class EightQueen
  class Step
    def initialize(x, y)
      @x, @y = x, y
      @parent = nil
      @depth = 0
    end
    attr_accessor :x, :y, :parent, :depth
  end
  
  def initialize(x, y)
    @stack = [Step.new(x, y)]
  end
  
  def solve
    #Step{a, nxt}, Integer{y, board[][]}
    while (a = @stack.pop)
      y = a.y + 1
      board = get_board(a)
      N.times do |x|
        next if board[y][x] == 1
        nxt = Step.new(x, y)
        nxt.parent = a
        nxt.depth = a.depth + 1
        finish(nxt) if nxt.depth == N - 1
        @stack.push(nxt)
      end
    end
    raise "No answer."
  end
  
  def get_board(a)
    #board, d, x1, x2
    board = Array.new(N) {Array.new(N, 0)}
    begin
      N.times do |i|
        board[i][a.x] = 1
        board[i] = Array.new(N, 1) if i == a.y
        d = (i - a.y).abs
        next if d.zero?
        x1 = a.x - d
        x2 = a.x + d
        board[i][x1] = 1 if x1 >= 0
        board[i][x2] = 1 if x2 < N
      end
    end while (a = a.parent)
    board
  end
  
  def finish(a)
    bd = Array.new(N) {"." * N}
    while a
      bd[a.y][a.x] = "@"
      a = a.parent
    end
    bd.map {|x| puts x}
    exit
  end
end

EightQueen.new(rand(N), 0).solve

※追記（7/24）
コードを多少修正しました。また、すべてのパターン（92通り）も求めてみました。コードと結果は下の Gist に。実行時間は 0.1秒程度です。コードは上のものにほんの少し修正を加えただけです。
eight_queen_all.rb · GitHub
　
続編。
obelisk.hatenablog.com