【アルゴリズムの勉強】Rubyで8王妃（エイトクイーン）問題を解いてみる

8王妃（エイトクイーン）問題とは

チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。
クイーンの動きは、上下左右斜めの8方向に、遮る物がない限り進める。将棋の飛車と角行を合わせた動きである。

エイト・クイーン - Wikipedia

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

参考文献、参考リンク

• 明解 Javaによるアルゴリズムとデータ構造