エイト・クイーン(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