8クイーン問題をバックトラック方法を用いて解く方法

AIDU ONLINE JUDGEの8クイーン問題を解いてみたいと思います。

8クイーンの例題

8 クイーン問題とは、8×8 のマスから成るチェス盤に、どのクイーンも他のクイーンを襲撃できないように、8 つのクイーンを配置する問題です。
チェスでは、クイーンは次のように８方向のマスにいるコマを襲撃することができます。
すでにクイーンが配置されている k 個のマスが指定されるので、
それらを合わせて８つのクイーンを配置したチェス盤を出力するプログラムを作成してください。

入力

１行目に整数 k が与えられます。続く k 行にクイーンが配置されているマスが２つの整数 r, c で与えられます。
r, c はそれぞれ０から始まるチェス盤の行と列の番号を表します。

出力

出力は 8×8 のチェス盤を表す文字列で、クイーンが配置されたマスを 'Q'、配置されていないマスを '.' で表します。

単純な計算量を考える

配置する8つのクイーンのすべての組み合わせを考えると、
8×8のマス目から8個を選ぶ組み合わせなので、
${}_64 \mathrm{ C }_8$ = 4426165368通りになります。

ここから、1つの行に1つしかクイーンを配置することができないので、$8^8 = 16777216$通りに、
さらに、2つ以上のクイーンが同じ列に配置できないことを考えると、8! = 40320通りになります。

バックトラックを用いた解法

バックトラックという方法を用いて、問題を解いてみます。
以下のように処理をします。

1.1行目の任意のマスにクイーンを配置する

2.1行目に配置したクイーンに襲撃されない位置に2行目のマスにクイーンを配置する

処理をまとめますと、

各クイーンが他のどのクイーンも襲撃しないように、i個のクイーンを最初のi行に配置した状態で、
これらのどのクイーンにも襲撃されない(i + 1)行目のマスに、クイーンを配置する

もし、そのようなマスが(i + 1)行目にないならば、i行目に戻り、i行目で行なっていた
他のクイーンに襲撃されないマス目探しを続けます。
そのようなマス目がなければ、さらに(i - 1)行に戻り、処理を続けていきます。

このように、可能性のある状態を調べていき、現在の状態からは得られないとわかった時点で
探索を打ち切り、一つ前の状態に戻って、途中から探索を再開する手法をバックトラックというそうです。

8クイーン問題のバックトラック手法に用いる変数と役割

クイーンの配置状態を記録するために、以下の変数を定義します。

変数名例	役割
row[N]	rox[i]に行が襲撃されているかどうかを記録する(rowは行の意味)
col[N]	col[j]に列が襲撃されているかどうかを記録する(colは列の意味)
dpos[2N - 1]	dpos[i + j]に左下方向の列が襲撃されているかどうかを記録する
dneg[2N - 1]	dneg[i - j + (N - 1)]にに右下方向の列が襲撃されているかどうかを記録する

下図が変数dposがどういう状態を表すかを示した図になります。
斜めに領域を取るので、dposの容量は2N - 1になります。
この図を左右反転させるとdnegになります。

row[i],col[j],dpos[i + j],dneg[i - j + N + 1]のいずれかに襲撃フラグが立っていると、
マス目が襲撃されていることになるので、
row[i],col[j],dpos[i + j],dneg[i - j + N + 1]のすべてのフラグがオフならば、クイーンが配置できることになります。

c++による8クイーン問題のバックトラック手法の解法

では、最後にc++でのプログラムの解法を載せます。

#include <iostream>

using namespace std;

#define N 8
#define FREE -1
#define NOT_FREE 1

int row[N],col[N],dpos[2 * N - 1],dneg[2 * N - 1];

// 入力時に置かれたqueenを記録しておく配列,true = queenが置かれた
bool X[N][N];

void init(){
    for(int i = 0;i < N;++i){
        row[i] = col[i] = FREE;
    }
    for(int i = 0;i < 2 * N - 1;++i){
        dpos[i] = dneg[i] = FREE;
    }
    
    for(int i = 0;i < N;++i){
        for(int j = 0;j < N;++j){
            X[i][j] = false;
        }
    }
}

/**
 出力関数
*/
void printBoard(){
    for(int i = 0;i < N;++i){
        for(int j = 0;j < N;++j){
            // 入力時に置かれたクイーンと同じでない場合は出力しない
            if(X[i][j]){
                if(row[i] != j){
                    return;
                }
            }
        }
    }
    
    for(int i = 0;i < N;++i){
        for(int j = 0;j < N;++j){
            // rowにqueenの置かれた位置を記録している
            cout << ((row[i] == j) ?  "Q" : ".");
        }
        cout << endl;
    }
}

void recursive(int i){
    // 最後の行までクイーンを置くことができた
    if(i == N){
        printBoard();
        return;
    }
    
    for(int j = 0;j < N;++j){
        // (i,j)が他のクイーンに襲撃されている場合は飛ばす
        if(col[j]  == NOT_FREE || dpos[i + j] == NOT_FREE || dneg[i - j + N - 1] == NOT_FREE){
            continue;
        }
        // (i,j)にクイーンを配置する
        // rowにqueen置かれた位置を記録する、行番号iの何列目にqueenが置かれたのかを示す
        row[i] = j;
        col[j] = dpos[i + j] = dneg[i - j + N - 1] = NOT_FREE;
        // 次の行を試す
        recursive(i + 1);
        // 次の行がダメだった場合(i,j)に配置されたクイーンを取り除く
        row[i] = col[j] = dpos[i + j] = dneg[i - j + N - 1] = FREE;
    }
    // クイーンの配置に失敗した
}

int main(){
    init();
    
    int k;
    cin >> k;
    for(int i = 0;i < k;++i){
        int r,c;
        cin >> r >> c;
        X[r][c] = true;
    }
    
    recursive(0);
    
    return 0;
}

参考
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造