エイトクィーンその1 - 順列の作成

エイトクィーンとは

チェスにはクィーンという駒があります。 クィーンは将棋の飛車と角を併せた動きをする駒で上下左右斜め の一直線上はいくらでも移動することができます。

エイトクィーン問題とは8 x 8のチェスの盤面上に8つのクィーンを お互い一回の手で取ることのないように 置くパターンを探す問題です。

解き方

8 x 8の64個のますに8つのクィーンを置く置き方は64 C 8 = 4426165368通り あります。 これら全ての置き方を検証することは非常に時間がかかるので、 除外されることが自明なパターンは最初から検証しないようにしなければ なりません。

クィーンは上下にいくらでも動くことが出来ますので、縦の列には 一つしか置けないことが分かります。 したがって、その縦のますのどの位置にクィーンが置けるか考えればいいことに なります。

次に横に無限に移動できることを考えます。 このことから、縦の位置が同じ駒は存在できないことが分かります。 ですので、縦の列の駒の縦の位置を並べた列には同じものが含まれないことが 分かります。 結局これは1から8までの数字の順列を考えればいいことになります。

1から8までの順列を生成した後、その数列が斜めの条件にひっかからないか どうか検証すればいいことになります。

順列の作成