Nクイーン【後編】

前編では、力まかせ探索・バックトラッキング探索・配置フラグを用いた探索について解説した。

後編では、ビット演算・マルチスレッドを用いた高速化について解説する。

ビット演算（ビットマップ）による高速化

前章では配列の配置フラグを使用することで高速化を達成したが、本章ではビット演算によりさらに高速化してみよう。
int cols の各ビットが、各カラムにクイーンを配置可能かどうかを表すものとする。
最初は全てのカラムに配置可能なので、初期値は全ビットが立っている (1< N 解の数 BF(ミリ秒) BT（ミリ秒） BF（ミリ秒） Bit（ミリ秒） 4 2 0 0 0 0 5 10 0 0 0 0 6 4 0 0 0 0 7 40 6 0 0 0 8 92 90 0 0 0 9 352 2112 1 1 0 10 724 N/A 5 8 0 11 2680 N/A 21 23 1 12 14200 N/A 113 50 7 13 73712 N/A 671 226 31 14 365596 N/A 4158 1361 179 15 2279184 N/A N/A N/A 1128 16 14772512 N/A N/A N/A 7496

マルチスレッドによる高速化

最近のCPUは以前（2000年代前半まで）ほどはクロックが向上せず、マルチコア・マルチスレッド化が進んでいる。
これは、微細化の限界、リーク電流・放熱問題などが原因でクロック向上が困難になったからだ。
コア・スレッド数が増えたのだから、それを活用して高速化を計るのが最近のトレンドになっている。
「マルチスレッド」とは複数の処理を直列ではなく並行して行うことだ。
N個の処理を並行して行うことができれば、理想的にはN倍の速度になる（下図参照）。
実際にはマルチスレッドのオーバーヘッドがあり、各処理が同時に終わるわけではないので、正確にN倍にはならない。
が、１分を要していた処理が６倍の10秒に短縮されれば体感的は大差になる。

Nクイーン【後編】

C++11からマルチスレッドのためのクラスが追加されたので、それを利用して高速化を図る。
ビット演算のときの backtrackingBitmap() を少しだけ改造し、解の個数を返すようにする。

int backtrackingBitmapMT(int cols,      //  配置可能カラム位置
                    int lt, int rt,   //  1 for 使用済み
                    int n, int NQ)              //  n:配置済みクイーン数, [0, NQ)
{
    int count = 0;
    int flags = ~(lt|rt) & cols;
    while( flags ) {
        int bit = -flags & flags;      //  一番右の１のビットを取り出す
        if( n + 1 == NQ )
            ++count;    // 解を発見
        else
            count += backtrackingBitmapMT(cols^bit, (lt|bit)<<1, (rt|bit)>>1, n+1, NQ);
        flags ^= bit;       //  処理済みビットをOFF
    }
    return count;
}

async(launch::async, 関数名, 引数列…) でスレッドを生成し、std::future:get() で指定した関数の返り値を受け取ることができる。
盤面サイズ N の分だけスレッドを生成し、スレッドを vector> lst に格納する。
※ 本稿ではasync(), get() を使用したが、関数が値を返さない場合は thread(), join() を使用する。
c番目のスレッドは最初の行のcカラム目にクイーンを置いた場合の解の個数を計測する。
std::future はスレッドを保持するクラスで、テンプレート引数（この場合は int）で、スレッド関数が返す値を指定する。

スレッドはCPUのスレッド数上限よりかなり多く（数千？）起動できるが、
物理的に並行処理されるのはスレッド数上限までなの、あまり多くしても意味がない。
Ｎクイーン問題の場合は、せいぜい数10なので、N個のスレッドを起動して問題ない。

N個のスレッドを起動し、解数を合計するコードは以下のように記述できる。

#include <future>
.....
        vector<std::future<int>> lst;
        for (int bit = 1<<nq; (bit>>=1) != 0; ) {
            int cols = (1<<nq)-1;       //  配置可能カラム位置
            int lt = 0, rt = 0;         //  1 for 使用済み
            //  スレッド起動
            lst.push_back(std::async(std::launch::async, backtrackingBitmapMT,
                                        cols^bit, (lt|bit)<<1, (rt|bit)>>1, 1, nq));
        }
        int count = 0;
        for(auto& f: lst)
            count += f.get();   //  スレッド修了を待ち、解回数を合計

マルチスレッドを使用した場合の処理時間計測結果を以下に示す。
処理時間計測を行った環境は、Core i7-6700で8コア・８スレッドで、約７倍高速になった。
マルチスレッドのオーバーヘッドがあるため、８コアで実行しても８倍の速度にはならないが、7倍の速度向上は体感的に大きい。
16コアのCPUであれば10倍以上になるのかもしれない、誰か実験してほしい。

処理時間測定結果：（Core i7-6700 3GHz, 32GB, Windows 10）

N	解の数	BF(ミリ秒)	BT（ミリ秒）	BF（ミリ秒）	Bit（ミリ秒）	MT（ミリ秒）
4	2	0	0	0	0	0
5	10	0	0	0	0	0
6	4	0	0	0	0	0
7	40	6	0	0	0	0
8	92	90	0	0	0	0
9	352	2112	1	1	0	0
10	724	N/A	5	8	0	0
11	2680	N/A	21	23	1	0
12	14200	N/A	113	50	7	1
13	73712	N/A	671	226	31	5
14	365596	N/A	4158	1361	179	29
15	2279184	N/A	N/A	N/A	1128	190
16	14772512	N/A	N/A	N/A	7496	1161
17	95815104	N/A	N/A	N/A	N/A	7427

おわりに

各種アルゴリズムを用いた８クイーン問題を解くプログラムを解説し、筆者の環境で17×17まで処理時間計測を行った。
本稿で解説したアルゴリズムは比較的簡単なもので、
より大きなサイズの問題を解くにはより高度なアルゴリズム、膨大な計算機資源が必要だ。
興味ある人は以下の参考文献を参照してぜひ追試してみてほしい。

参考文献

・対称解の除去方法については、takaken氏による詳しい解説がある
参照：「Ｎクイーン問題（解の個数を求める）」 http://www.ic-net.or.jp/home/takaken/nt/queen/

・2004年、電気通信大学の研究グループが、処理を並列化し、N=24の解の個数を世界で初めて発見。
参照：「N-queens Homepage in Japanese」 http://www.arch.cs.titech.ac.jp/~kise/nq/index.htm

・2009年～10年、萩野谷一二氏（大阪府立大学）の部分解から全体解を構成するというアプローチで従来より10倍の高速化に成功
参照：「NQueens問題」 http://deepgreen.game.coocan.jp/NQueens/nqueen_index.htm

・萩野谷氏（大阪府立大学）はGPUを用いた高速化も研究している
参照：「対称解の特性を用いた N-Queens 問題の求解とGPU による高速化」（情報処理学会研究報告2012/03）
http://deepgreen.game.coocan.jp/NQueens(GPU)/GI27-07.pdf

・27×27の世界記録を更新「Solving the N-Queens Puzzle for 27 Queens using FPGAs」
参照：https://forums.xilinx.com/t5/Xcell-Daily-Blog-Archived/Solving-the-N-Queens-Puzzle-for-27-Queens-using-FPGAs/ba-p/692248