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秒に短縮されれば体感的は大差になる。

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）

おわりに

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

参考文献

筆者：津田伸秀 プロフィール：テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員（主席）。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。