バックトラック法
11月 11th, 2008 admin Posted in アルゴリズムとデータ構造 | 
久しぶりに「アルゴリズムとデータ構造シリーズ」です。今回は第10章「バックトラック法と幅優先探索」のバックトラック法です。
バックトラック法
ある解を求めるときに、考えられるパターンをすべて試しながら解く方法のひとつです。迷路の右手法をイメージするといいんじゃないでしょうか。パワープレイすぎてスマートさはありませんが、結局この方法が早かったり、この方法でないと解けなかったりします。以前ナンプレに挑戦したときも結局このバックトラック法を使いました。
コード
今回はエイトクイーン問題をバックトラック法で解くようにしました。
RUBY:
-
class Qween
-
def initialize(n)
-
@size = n
-
@board = Array.new
-
@size.times do |i|
-
@board[i] = Array.new
-
@size.times do |j|
-
@board[i].push(nil)
-
end
-
end
-
end
-
-
def check(y,x)
-
-
(0...x).each do |i|
-
return nil unless @board[y][i].nil?
-
end
-
-
(x+1).times do |i|
-
if (y-i)>= 0 && (x-i)>= 0
-
return nil unless @board[y-i][x-i].nil?
-
end
-
-
if (y+i) <@size && (x-i)>= 0
-
return nil unless @board[y+i][x-i].nil?
-
end
-
end
-
true
-
end
-
-
def solve(x)
-
return true if x == @size
-
-
(0...@size).each do |i|
-
if check(i,x)
-
@board[i][x] = true
-
-
-
if solve(x+1)
-
return true
-
else
-
@board[i][x] = nil
-
end
-
end
-
end
-
return nil
-
end
-
-
def show
-
@board.each do |row|
-
row.each do |c|
-
print c ? 'Q' : '-'
-
print ' '
-
end
-
print "\n"
-
end
-
end
-
end
-
-
q = Qween.new(ARGV[0].to_i
-
)
-
q.solve(0)
-
q.show
結果
CODE:
-
Q - - - - - - -
-
- - - - - - Q -
-
- - - - Q - - -
-
- - - - - - - Q
-
- Q - - - - - -
-
- - - Q - - - -
-
- - - - - Q - -
-
- - Q - - - - -
たしかにQが縦にも横にも斜めにも重ならないように配置されています。
まとめ
ちなみにNクイーン問題は４x4以上ならすべて解があるそうです。個人的には４x4の解が一番かっこよく見えるかな。クイーン同士が仲良さそうで
CODE:
-
- - Q -
-
Q - - -
-
- - - Q
-
- Q - -
※このシリーズは私がRubyでアルゴリズムとデータ構造を基礎から学ぶ記録です。全体の目次はこちらへ。
11月 11th, 2008 at 2:28:31
[...] バックトラック法 はてなに追加 MyYahoo!に追加 del.icio.usに追加 livedoorClipに追加 15 Responses to “Rubyでアルゴリズムとデータ構造” [...]
8月 31st, 2009 at 8:16:08
I loved reading this and I dont really like to read