【アルゴリズムの勉強】Rubyで8王妃(エイトクイーン)問題を解いてみる
8王妃(エイトクイーン)問題とは
チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。
クイーンの動きは、上下左右斜めの8方向に、遮る物がない限り進める。将棋の飛車と角行を合わせた動きである。
Rubyで実装
QUEEN = 8 @is_set = Array.new(QUEEN){false} @is_set_diagonal_right = Array.new(QUEEN * 2 - 1){false} @is_set_diagonal_left = Array.new(QUEEN * 2 - 1){false} @queen_position = [] @count = 0 def calc_pattern(column) QUEEN.times{|row| unless @is_set[row] || @is_set_diagonal_right[column + row] || @is_set_diagonal_left[column - row + (QUEEN - 1)] @queen_position[column] = row if column == (QUEEN - 1) @count += 1 else @is_set[row] = @is_set_diagonal_right[column + row] = @is_set_diagonal_left[column - row + (QUEEN - 1)] = true calc_pattern(column + 1) @is_set[row] = @is_set_diagonal_right[column + row] = @is_set_diagonal_left[column - row + (QUEEN - 1)] = false end end } end calc_pattern(0) p @count # => 92