技術文章＞ ゲーム・パズル関係


　

　

N-Queens 問題
Nobuhide Tsuda
26-May-2013

はじめに

力まかせ探索（Brute-force search）

N重ループによるコード： 

    int row[NQ];   //  各行のクイーン位置 [1, NQ]
    for(row[0] = 1; row[0] <= NQ; ++row[0]) {
        ....
        for(row[NQ-1] = 1; row[NQ-1] <= NQ; ++row[NQ-1]) {
            if( 制約を満たしているか？ ) {
                解を発見;
            }
        }
    }

再帰関数によるコード（ボードサイズはテンプレート引数で付与）： 

bool test(const int row[], int n)   //  n:配置済みクイーン数
{
    for(int r = 1; r < n; ++r) {
        for(int i = 0; i < r; ++i) {
            if( row[i] == row[r] || qAbs(row[i] - row[r]) == r - i )
                return false;
        }
    }
    return true;
}
template<int NQ>
void generateAndTest(int row[], int n)      //  配置済みクイーン数
{
    for(row[n] = 1; row[n] <= NQ; ++row[n]) {
        if( n + 1 == NQ ) {
            if( test<NQ>(row) )
                ++g_count;    // 解を発見
        } else
            generateAndTest<NQ>(row, n+1);
    }
}

パフォーマンス測定結果：

N 解の数 末端ノード数 Brute-Force (ミリ秒)
4 2 256 0
5 10 3,125 1
6 4 46,656 1
7 40 823,543 10
8 92 16,777,216 150
9 352387,420,4893,317

バックトラッキング

bool testNth(const int row[], int n)
{
    for(int i = 0; i < n; ++i) {
        if( row[i] == row[n] || qAbs(row[i] - row[n]) == n - i )
            return false;
    }
    return true;
}
template<int NQ>
void backtracking(int row[], int n)     //  n:配置済みクイーン数
{
    for(row[n] = 1; row[n] <= NQ; ++row[n]) {
        if( testNth(row, n) ) {    // 制約を満たしている場合のみ先に進む
            if( n + 1 == NQ )
                ++g_count;    // 解を発見
            else
                backtracking<NQ>(row, n+1);
        }
    }
}

パフォーマンス測定結果：

N 解の数 末端ノード数 Backtracking (ミリ秒) BF (ミリ秒)
4 2 46 0 0
5 10 177 0 1
6 4 746 0 1
7 40 3,073 0 10
8 92 13,756 1 150
9 352 64,337 2 3,317
10 724 313,336 9 N/A
11 2,680 1,642,461 49 N/A
12 14,200 9,261,880 220 N/A
13 73,712 55,214,137 1,434 N/A
14 365,596350,908,442 9,271 N/A

制約テスト高速化（配置フラグ）

template<int NQ>
void backtrackingFlags(
                    bool col[], bool rup[], bool rdn[],    // 垂直・対角線方向に配置済みフラグ
                    int n)      //  n:配置済みクイーン数, [0, NQ)
{
    for(int q = 0; q < NQ; ++q) {
        const int uix = n + q;
        const int dix = q - n + NQ - 1;
        if( !col[q] && !rup[uix] && !rdn[dix] ) {
            if( n + 1 == NQ )
                ++g_count;    // 解を発見
            else {
                col[q] = true;
                rup[uix] = true;
                rdn[dix] = true;
                backtrackingFlags<NQ>(col, rup, rdn, n+1);
                col[q] = false;
                rup[uix] = false;
                rdn[dix] = false;
            }
        }
    }
}

パフォーマンス測定結果：

N 解の数 末端ノード数 Flag (ミリ秒) BT (ミリ秒) BF (ミリ秒)
4 2 46 0 0 0
5 10 177 0 0 1
6 4 746 0 0 1
7 40 3,073 0 0 10
8 92 13,756 0 1 150
9 352 64,337 1 2 3,317
10 724 313,336 3 9 N/A
11 2,680 1,642,461 14 49 N/A
12 14,200 9,261,880 53 220 N/A
13 73,712 55,214,137 316 1,434 N/A
14 365,596350,908,4421,8139,271 N/A

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

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

パフォーマンス測定結果：

N 解の数 末端ノード数 Bitmap (ミリ秒) Flag (ミリ秒) BT (ミリ秒) BF (ミリ秒)
4 2 6 0 0 0 0
5 10 14 0 0 0 1
6 4 50 0 0 0 1
7 40 194 0 0 0 10
8 92 736 0 0 1 150
9 352 2,936 0 1 2 3,317
10 724 12,774 0 3 9 N/A
11 2,680 61,076 2 14 49 N/A
12 14,200 314,730 10 53 220 N/A
13 73,712 1,716,652 50 316 1,434 N/A
14 365,596 10,030,692 298 1,8139,271 N/A
15 2,279,184 62,518,772 1,805 N/A N/A N/A
16 14,772,512415,515,37612,179N/A N/A N/A

対称解除去

パフォーマンス測定結果：

N ユニーク解数 対称形除去(ミリ秒) 解数 Bitmap (ミリ秒) Flag (ミリ秒) BT (ミリ秒)
4 1 0 2 0 0 0
5 2 0 10 0 0 0
6 1 0 4 0 0 0
7 6 0 40 0 0 0
8 12 0 92 0 0 1
9 46 1 352 0 1 2
10 92 0 724 0 3 9
11 341 3 2,680 2 14 49
12 1,787 14 14,200 10 53 220
13 9,233 79 73,712 50 316 1,434
14 45,752 449 365,596 298 1,8139,271
15 285,053 3,001 2,279,184 1,805 N/A N/A
16 1,846,95520,14214,772,51212,179N/A N/A

枝刈りによる高速化

uint g_prohibit;    // 配置可能位置フラグ
template<int NQ>
void backtrackingBitmapSEdge(uint lt, uint dn, uint rt,
                    int n)      //  配置済み個数
{
    uint flags = ~(lt|dn|rt) & ((1<<NQ)-1);
    if( n == NQ - 1 ) {
        flags &= g_prohibit;
        if( flags ) {
            g_row[n] = flags;
            if( symmetryCheck<NQ>() ) {
                ++g_count;
            }
        }
    } else {
        if( !((1<<n) & g_prohibit) )
            flags &= ~(1|(1<<NQ-1));
        while( flags ) {
            uint bit = -flags & flags;
            flags ^= bit;
            g_row[n] = bit;
            backtrackingBitmapSEdge<NQ>((lt|bit)<<1, (dn|bit), (rt|bit)>>1, n+1);
        }
    }
}
template<int NQ>
void backtrackingBitmapS2()
{
    g_count = 0;
    for(uint mask = 1; mask < (1<<(NQ/2)); mask<<=1) {
        g_row[0] = mask;
        if( mask == 1 ) {
            .....
        } else {
            g_prohibit = mask - 1;
            g_prohibit |= reverse<NQ>(g_prohibit);
            g_prohibit = ~g_prohibit;       //  配置可能フラグ
            backtrackingBitmapSEdge<NQ>(mask<<1, mask, mask>>1, 1);
        }
    }
}

パフォーマンス測定結果：

N ユニーク解数 末端ノード数 枝刈(ミリ秒) Uniq(ミリ秒) 解数 末端ノード数 Bitmap
4 1 2 0 0 2 6 0
5 2 5 0 0 10 14 0
6 1 15 0 0 4 50 0
7 6 59 0 0 40 194 0
8 12 212 0 0 92 736 0
9 46 807 0 1 352 2,936 0
10 92 3,479 0 0 724 12,774 0
11 341 16,225 0 3 2,680 61,076 2
12 1,787 82,940 4 14 14,200 314,730 10
13 9,233 443,353 16 79 73,712 1,716,652 50
14 45,752 2,563,413 80 449 365,596 10,030,692 298
15 285,053 15,704,793 480 3,001 2,279,184 62,518,772 1,805
16 1,846,955 103,176,096 3,21620,14214,772,512415,515,37612,179
17 11,977,939713,303,685 21,984 N/A N/A N/A N/A
18 83,263,5915,224,009,865 163,225 N/A N/AN/A N/A

さいごに

参考文献