Rubyでエイトクイーン問題をバックトラック法で解く | Ruby入門 - Worth Living

エイトクイーン問題のルール エイト・クイーン – Wikipedia チェスの盤上に、8個のクイーンを配置する。このとき、どの駒も他の駒に取られるような位置においてはいけない。 クイーンの動きは、上下左右斜めの8方向に、遮る物がない限り進める。将棋の飛車と角行を合わせた動きである。 面白そうな問題です。 びっくりしたのは、100年以上前の1874年には解答が出ていたそうです。 バックトラック法でエイトクイーン問題を解く とりあえず試してみて、ダメだったら引き返してやり直す、というアルゴリズムは、バックトラック法と呼ばれるそうです。 そういえば、正規表現のマッチはバックトラック法で行われると、なんかの本で読んだことがある。 以下、バックトラック法で試行錯誤を行い、エイトクイーン問題を解く。 # エイトクイーン問題 # 8×8マスのボード上に、8つのクイーンを置く # 8つのクイーンは、上下2