Rubyでエイトクイーン問題をバックトラック法で解く
お金 | 仕事 | 勉強 | プライベート | 健康 | 心
プログラミング関連のコンテンツ
C言語/C++入門 | Ruby入門 | Python入門 | プログラミング全般
という本を読んでいたら、エイトクイーン問題というのが出てきて面白そうでした。
再帰関数の練習がてら、Rubyプログラムで解いてみることにチャレンジ。
エイトクイーン問題のルール
チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。
クイーンの動きは、上下左右斜めの8方向に、遮る物がない限り進める。将棋の飛車と角行を合わせた動きである。
面白そうな問題です。
びっくりしたのは、100年以上前の1874年には解答が出ていたそうです。
バックトラック法でエイトクイーン問題を解く
とりあえず試してみて、ダメだったら引き返してやり直す、というアルゴリズムは、バックトラック法と呼ばれるそうです。
そういえば、正規表現のマッチはバックトラック法で行われると、なんかの本で読んだことがある。
以下、バックトラック法で試行錯誤を行い、エイトクイーン問題を解く。
# エイトクイーン問題
# 8×8マスのボード上に、8つのクイーンを置く
# 8つのクイーンは、上下2方向、左右2方向、斜め4方向、合計8方向へ移動可能とする。
# このとき、8つのクイーンはお互いに、進行方向でぶつからないように配置する。⇒利き筋
class EightQueen
attr_reader :row
def initialize
# ボード上の座標(0, 0)～(7, 7)まで、マス目を@board[x][y]で表す。
# xが縦軸、yが横軸になるので注意。
@board = [
[false, false, false, false, false, false, false, false],
[false, false, false, false, false, false, false, false],
[false, false, false, false, false, false, false, false],
[false, false, false, false, false, false, false, false],
[false, false, false, false, false, false, false, false],
[false, false, false, false, false, false, false, false],
[false, false, false, false, false, false, false, false],
[false, false, false, false, false, false, false, false],
]
=begin
# 以下の書き方でも良い
@board = Array.new(8, false)
@board.each_index do |i|
@board[i] = Array.new(8, false)
end
=end
# 行(row), 列(col)のサイズ
@row = @board.length # ⇒8
@col = @board[0].length # ⇒8
end
# x は行番号、count は制御用。@row回再帰したら、trueを返す。
# x に0～(@row-1)を渡して使う
def solve_8q(x, count = 0)
if (@row - 1) < x || x < 0
return
end
if count == @row
return true
end
@board[x].each_index do |i|
# クイーンが(x, i)に置けるかどうかチェック
if check(x, i)
@board[x][i] = true
#puts "デバッグ用：(#{x}, #{i}) にクイーンを置きました。"
# 再帰で次の行へ。xは@row（8）以上にならず、0に巻き戻す
if solve_8q( ((x + 1) % @row), (count + 1) )
return true
else
# 次の行が失敗なら(x, i)をfalseに戻す
@board[x][i] = false
end
end
end
return false
end
# ボードを出力
def show_board
@row.times do |x|
@col.times do |y|
if @board[x][y]
print "■"
else
print "□"
end
end
print "\n"
end
end
# (x,y)の利き筋に、クィーンがあるかどうかチェック
# 利き筋がなく、(x,y)にクイーンが置けるなら、trueを返す
def check(x, y)
# 上方向をチェック
p = x - 1
while 0 <= p
return false if @board[p][y]
p -= 1
end
# 下方向をチェック
p = x + 1
while p < @col
return false if @board[p][y]
p += 1
end
# 左方向をチェック
q = y - 1
while 0 <= q
return false if @board[x][q]
q -= 1
end
# 右方向をチェック
q = y + 1
while q <= @row
return false if @board[x][q]
q += 1
end
# 左上方向をチェック。x,yとも1ずつ小さくなる。
p = x - 1
q = y - 1
while 0 <= p && 0 <= q
return false if @board[p][q]
p -= 1
q -= 1
end
# 左下方向をチェック。xは大きく、yは小さくなる
p = x + 1
q = y - 1
while p < @col && 0 <= q
return false if @board[p][q]
p += 1
q -= 1
end
# 右上方向をチェック。xは小さく、yは大きくなる
p = x - 1
q = y + 1
while 0 <= p && q < @col
return false if @board[p][q]
p -= 1
q += 1
end
# 右下方向をチェック。x,yとも1ずつ大きくなる
p = x + 1
q = y + 1
while p < @col && q < @row
return false if @board[p][q]
p += 1
q += 1
end
return true
end
end
row = EightQueen.new.row
row.times do |x|
puts "----- 解答 #{x + 1} -----"
puts
eq = EightQueen.new
eq.solve_8q(x)
eq.show_board
puts
end
上記のスクリプトは、以下のページのエイトクイーンのバックトラック法での解決を参考にしました。
開始の位置が(0,0)の場合は、解を発見できるけれど、それ以外の開始位置では正しい解が発見できない。
とのことだったので、起点（開始の位置）を、(0,0)以外の(0,0) ～ (7, 0)とした場合でも動作するように改良しました。
ちなみに、ボード上の(7, 0)の位置は、配列上では@board[7][0]となる。
以下に、実行結果を示します。
“■”がクイーン、”□”は空のマス。
実行結果
----- 解答 1 ----- ■□□□□□□□ □□□□■□□□ □□□□□□□■ □□□□□■□□ □□■□□□□□ □□□□□□■□ □■□□□□□□ □□□■□□□□ ----- 解答 2 ----- □□□□□□■□ ■□□□□□□□ □□■□□□□□ □□□□□□□■ □□□□□■□□ □□□■□□□□ □■□□□□□□ □□□□■□□□ ----- 解答 3 ----- □□□■□□□□ □□□□□□□■ ■□□□□□□□ □□■□□□□□ □□□□□■□□ □■□□□□□□ □□□□□□■□ □□□□■□□□ ----- 解答 4 ----- □□□□□■□□ □□□■□□□□ □□□□□□■□ ■□□□□□□□ □□■□□□□□ □□□□■□□□ □■□□□□□□ □□□□□□□■ ----- 解答 5 ----- □□□■□□□□ □■□□□□□□ □□□□□□□■ □□□□□■□□ ■□□□□□□□ □□■□□□□□ □□□□■□□□ □□□□□□■□ ----- 解答 6 ----- □□□■□□□□ □□□□□■□□ □□□□□□□■ □■□□□□□□ □□□□□□■□ ■□□□□□□□ □□■□□□□□ □□□□■□□□ ----- 解答 7 ----- □□□□□■□□ □□□■□□□□ □■□□□□□□ □□□□□□□■ □□□□■□□□ □□□□□□■□ ■□□□□□□□ □□■□□□□□ ----- 解答 8 ----- □□■□□□□□ □□□□■□□□ □■□□□□□□ □□□□□□□■ □□□□□■□□ □□□■□□□□ □□□□□□■□ ■□□□□□□□
ボード上の座標(0, 0) ～ (7,0) を起点として探索を開始して、8通りの答えを導くことができました。
一番左の列に注目すると、一つずつクイーンの位置（■）が下に下がっている。これが探索の開始地点。
・・・が、Wikipediaによると本当は、12通りの回答があるそうで、もれなく12通りを探し出すためには、もう一歩アルゴリズムの工夫が必要みたいです。
現在のアルゴリズムですと、起点1つにつき、一通りの解答しか得られない。
ここをどう改良したら良いんだろう･･･？バックトラックじゃなくて、総当りの方法にしなきゃ駄目なのだろうか。
参考・関連ページ
エイト・クイーン – Wikipedia
アルゴリズム for Ruby
バックトラック法
定番アルゴリズムを徹底理解！ – 今からでも遅くない！アルゴリズム入門：selfup
