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

書籍で紹介されていて自分もすぐにこういう法則を
発見できるように精進していきたいです。


新・明解C言語によるアルゴリズムとデータ構造

新・明解C言語によるアルゴリズムとデータ構造