Nクイーンパズルを解く(2) - 対称性

GCC

今日はNクイーンパズルの対称性を検討してみます。

簡単な6クイーンでやってみよう。

ans : 1
...Q..
Q.....
....Q.
.Q....
.....Q
..Q...

ans : 2
....Q.
..Q...
Q.....
.....Q
...Q..
.Q....

ans : 3
.Q....
...Q..
.....Q
Q.....
..Q...
....Q.

ans : 4
..Q...
.....Q
.Q....
....Q.
Q.....
...Q..

解は4つ。しかし、どれもおんなじような感じ。


僕が思いついた比較法は、

  • 解が見付かったリストを用意しておく。
  • 見付かった解のリストを回転、反転して比較。(計8回*見付かったリスト数)
  • ユニークならリストに追加。

普通はこうやりそうなモノだけど、解説はすげーテクニック使ってる。


Karetta|Cパズルプログラミング-再帰編|ユニーク解は12個では

  • 自分自身を回転、反転させる(計8回)
  • 8個の中で一個だけを解とする。(クイーンが一番先に見付かったもの)
  • それ以外は無視。

解がユニークであるかどうかは、自分自身を見れば判っちゃう。凄いっす。感動っす。


それを元にコーディングすると、6クイーンの解は一個だけ。

.Q....
...Q..
.....Q
Q.....
..Q...
....Q.

x軸から見ているので、一番先にクイーンが見付かるのはans : 3になります。それ以外は対称性があるので、無視。

まとめ

  • 対称性の比較は自分自身を見ればわかる。

感動しました。

パスルの解法は、ans(ans(ans(ans(...))))と再帰的にやっていけば、出るみたいですね。再帰の練習には丁度いい素材です。

次はペグ'ソリティア。限定マスですが、フラッシュゲーム「ペグソリティア」がよくできてます。やぱい。ペグ・ソリティア面白いな ← はまりすぎ。