エイトクイーンパズルの解法について
「アルゴリズムとデータ構造」紀平拓男/春日伸弥 著 (http://www.sbcr.jp/products/4797324198.html?sku=4797324198)第10章において エイトクイーンパズルをC言語で解いているのですが、
左上(0, 0)がクイーンの場合しか答えを出力しない
のはどうしてか教えてください。また、
他の91通りの解を出力するにはどのように修正すればよいか
も教えていただけないでしょうか?
ちなみに以下のコードは、本の解法をRuby版にかなり忠実に置き換えたものです。 (コードの重複等あるかと思いますが、あらかじめご了承ください。)
ご指摘や、コードの修正は、こちらのRuby版で行なっていただけると ありがたいです。
@board = Array.new(8, false)
@board.each_index do |i|
@board[i] = Array.new(8, false)
end
# (x,y)にクィーンがあるかどうかチェック
def check(x, y)
# 左方向をチェック
p = 0
while p < x
return false if @board[p][y]
p += 1
end
# 左上方向をチェック
p, q = x, y
while p > 0 && q > 0
return false if @board[p -= 1][q -= 1]
end
# 左下方向をチェック
p, q = x, y
while p > 0 && q < 7
return false if @board[p -= 1][q += 1]
end
return true
end
def showBoard
for y in (0..7)
for x in (0..7)
if @board[x][y]
printf "Q "
else
printf ". "
end
end
printf "\n"
end
end
def solve(x)
if x == 8
return true
end
i = 0
while i < 8
if check(x, i)
# (x,i)にクィーンがおけたら実際に置く
@board[x][i] = true
if solve(x + 1)
# 次の列以降が成功ならこの列も成功
return true
else
# 次の列以降が失敗ならクィーンを置き直す
@board[x][i] = false
end
end
i += 1
end
return false
end
if solve(0)
showBoard
puts "---------------"
end