Nクイーン【後編】


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

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

ビット演算(ビットマップ)による高速化

前章では配列の配置フラグを使用することで高速化を達成したが、本章ではビット演算によりさらに高速化してみよう。
int cols の各ビットが、各カラムにクイーンを配置可能かどうかを表すものとする。
最初は全てのカラムに配置可能なので、初期値は全ビットが立っている (1<<NQ)-1となる。
32ビット変数であれば32が、64ビット変数であれば64がサイズ上限となり、配列に比べるとスケーラビリティに劣る。
が、2016年に更新された世界記録でも N = 27なので、32が上限でも当分の間は問題にならない。

斜め方向にクイーンを配置したかどうかをビットマップのフラグで表す(lt, rt)。
ビットマップであれば、シフトにより高速にデータを移動できる。
フラグ配列ではデータをひとつ右または左に移動するのに O(N) の時間がかかるが、
ビットマップであればシフト命令ひとつだけで状態を移動可能なので O(1) で可能だ。
なので、前章のフラグ配列のように斜め方向に2*N-1の要素を用意するのではなくNビットで充分となる。
最初は、どこにもクイーンを配置していないので、lt, rt の初期値は0となる。

配置可能なビット列を flags に入れ、-flags & flags で順にビットを取り出し処理する。
これはビット演算(ビットマップ)でよく使用するテクニックのひとつである(4×4オセロ完全解析の時も使用した)。
なぜそうなるかは、-x = ~x + 1であることを考えると、分かりやすいと思う。

以上を踏まえたコードは以下のようになる。

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

上記関数を呼び出す場合は、以下のように記述する。

        int cols = (1<<nq)-1;		//  配置可能カラム位置
        int lt = 0, rt = 0;			//  1 for 使用済み
        backtrackingBitmap(cols, lt, rt, 0, nq);

配置フラグにビットマップを使用した場合の処理時間計測結果を以下に示す。
処理オーダーはO(N!) で変わらないが、配列の配置フラグの場合に比べて7倍以上の高速化を達成できた。

処理時間測定結果:(Core i7-6700 3GHz, 32GB, Windows 10)

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倍にはならない。
が、1分を要していた処理が6倍の10秒に短縮されれば体感的は大差になる。

Nクイーン【後編】

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;      //  一番右の1のビットを取り出す
        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<std::future> lst に格納する。
※ 本稿ではasync(), get() を使用したが、関数が値を返さない場合は thread(), join() を使用する。
c番目のスレッドは最初の行のcカラム目にクイーンを置いた場合の解の個数を計測する。
std::future はスレッドを保持するクラスで、テンプレート引数(この場合は int)で、スレッド関数が返す値を指定する。

スレッドはCPUのスレッド数上限よりかなり多く(数千?)起動できるが、
物理的に並行処理されるのはスレッド数上限までなの、あまり多くしても意味がない。
Nクイーン問題の場合は、せいぜい数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コア・8スレッドで、約7倍高速になった。
マルチスレッドのオーバーヘッドがあるため、8コアで実行しても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

おわりに

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

参考文献

・対称解の除去方法については、takaken氏による詳しい解説がある
参照:「Nクイーン問題(解の個数を求める)」 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

関連記事

Nクイーン【後編】

ビット演算(ビットマップ)による高速化 前章では配列の配置フラグを使用することで高速化を達成したが、本章ではビット演算によりさらに高速化してみよう。 int cols の各ビットが、各カラムにクイーンを配置可能かどうかを […]
コメントなし

Nクイーン【前編】

はじめに Nクイーン問題(N-Queens puzzle) Nクイーン問題とは、NxNの盤面にチェスのクイーンN個を互いに効きが無い(クイーンは縦・横・斜め45度方向に効きがある)ように配置する問題だ。 一般的には8&# […]
コメントなし
筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。
  • このエントリーをはてなブックマークに追加

PAGE TOP