8 Queens Problem
再帰処理を利用してエイトクイーン問題を解きます。
エイトクイーン問題とは
チェスの盤上に、8個のクイーンを配置する。 このとき、どの駒も他の駒に取られるような位置においてはいけない。 クイーンの動きは、上下左右斜めの8方向に、 遮る物がない限り進める。将棋の飛車と角行を合わせた動きである。
というものです。
8queens.rb
$SIZE = 7 $pos = [] $flag_a = [] $flag_b = [] $flag_c = [] def print_pos board = Array.new($SIZE+1).map{Array.new($SIZE+1," ")} $pos.each_with_index {|q,column| board[q][column] = "q" } board.each{ |elem| p elem } puts "\n" end def set(i) (0..$SIZE).each { |x| if($flag_a[x]==0 && $flag_b[i+x]==0 && $flag_c[i-x+7]==0) then $pos[i] = x if i == $SIZE then print_pos() else $flag_a[x] = $flag_b[i+x] = $flag_c[i-x+$SIZE] = 1 set(i+1) $flag_a[x] = $flag_b[i+x] = $flag_c[i-x+$SIZE] = 0 end end } end $pos.fill(0,0..$SIZE) $flag_a.fill(0,0..$SIZE) $flag_b.fill(0,0..$SIZE*2) $flag_c.fill(0,0..$SIZE*2) set(0)
実行結果のうち二つ(全92通り)
[" ", " ", "q", " ", " ", " ", " ", " "] [" ", " ", " ", " ", "q", " ", " ", " "] [" ", "q", " ", " ", " ", " ", " ", " "] [" ", " ", " ", " ", " ", " ", " ", "q"] [" ", " ", " ", " ", " ", "q", " ", " "] [" ", " ", " ", "q", " ", " ", " ", " "] [" ", " ", " ", " ", " ", " ", "q", " "] ["q", " ", " ", " ", " ", " ", " ", " "] [" ", " ", "q", " ", " ", " ", " ", " "] [" ", " ", " ", " ", " ", "q", " ", " "] [" ", " ", " ", "q", " ", " ", " ", " "] [" ", "q", " ", " ", " ", " ", " ", " "] [" ", " ", " ", " ", " ", " ", " ", "q"] [" ", " ", " ", " ", "q", " ", " ", " "] [" ", " ", " ", " ", " ", " ", "q", " "] ["q", " ", " ", " ", " ", " ", " ", " "]
rubyをもっと知っていれば、もっとかっこよく書けそうなのですが、
私にはこれが限界です。これもこちらを参考にさせてもらっています。
さて、エイトクイーン問題は初めて実装したのですが、
考え方は結構単純です。
すべての場合を列挙し、そこから条件を絞っていくという流れです。
下記の部分で条件判定をしています。
if($flag_a[x]==0 && $flag_b[i+x]==0 && $flag_c[i-x+$SIZE]==0) then
書籍で紹介されていて自分もすぐにこういう法則を
発見できるように精進していきたいです。
- 作者: 柴田望洋,辻亮介
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2011/09/01
- メディア: 単行本
- 購入: 3人 クリック: 37回
- この商品を含むブログ (7件) を見る