いままでのNQueenは
NQueenは、ひとつの解には、盤面を90度・180度・270度回転、及びそれらの鏡像の合計8個の対称解が存在します。これを利用した、対称的な解を除去し、ユニーク解のみを求める方法として解がみつかるとすべての対称解を生成し、 状態を数値とみなして最も小さいもののみを解とする方法（最小解選択法）をベースに枝刈りを追加したロジックで高速化を試みていました。
このロジックをGPUを利用して並列化し高速化しようとしました。
確かにかなり速くなったのですがボトルネックが見つかりました。最小解選択法は、最終行で回転チェックをして最少解判定(symmetryOps)を行うのですが、symmetryOpsに必要な情報として各行のどこにクイーンを置いたかという配列(aBoard)が必要になります。このaBoard配列をGPUに呼び出す際に渡す必要があるのですが、それなりの情報量があり、これがかなりのボトルネックとなってました。
そんな時に、鈴木維一郎先生が、N27を実現したプロジェクトのプログラムを見つけて来てくれました。
https://github.com/preusser/q27/blob/master/pitch.pdf
このプログラムのロジックは、最初にsymmetryOpsに必要な上下左右2行2列にクイーンを置き、symmetryOpsをした後に残りのNQueenを実行するというものでした。
これなら、GPUにaBoard配列を渡さなくて済むので問題解決ではと思い取り組みました。
進めていくと、上下左右2行2列にクイーンを置くロジックが遅すぎて今までのロジックの10倍くらい時間がかかることが分かりました。
そこで、現在はこの上下左右2行2列にクイーンを置くロジックを速くできないか日々格闘しているところです。
8月4日
上下左右2行2列にクイーンを置くロジックを上下左右2行2列にしかクイーンを置けないようにしながら1行目から最終行まで一旦NQueenをするというロジックを開発して数が合うまでにはなった。
しかし、symmetryOpsを追加するとn8から数が合わなくなる。
N: Unique hh:mm:ss.ms
4: 1 0.00
5: 2 0.00
6: 1 0.00
7: 6 0.00
8: 13 0.00
9: 47 0.00
10: 93 0.01
11: 350 0.04
12: 1855 0.12
13: 9407 0.35
14: 46496 1.08
15: 288695 3.61
1週間以上考えてもさっぱりわからないので新ロジックと既存のnq27_N-Queen.cの両方にsymmetryOpsした直後の状態をロギングするようにして違いを眺めることにした。ロギングの準備は終わったが、n5から数が合わないなら楽だがn8からだと比較するのが結構大変そうだ。
時間がかかりそうなので日記形式で日々の取り組みを記すことにした。
