エイト・クイーン問題を解く

現在セール中で安くなっていたこともあり懐かしのレイトン教授のスマホゲームを暇つぶしにやっていた。

レイトン教授と不思議な町 EXHD for スマートフォン

• Level-5 Inc.
• ゲーム
• ¥960
• 

play.google.com
すると、攻略後の裏ステージでエイト・クイーン問題が出題された。普通に試行錯誤していてもなかなか解けなかったことと、自分で実装したことがなかったこともあり、プログラムを組んで解を探すことにした。
エイト・クイーン - Wikipedia

解法

愚直に実装したら64マスにクイーンを8個おくので、
通り試せば良い。 計算量だとになるのでまあできそう。

ただ、割と自明な必要条件として、各クイーンは同じ筋、または段に2個以上あってはならないことが言える。クイーンは将棋の飛車の動きもすることを使った条件だ。この条件を課すと、組み合わせとしては通りになる。10万分の1の計算量になるのでこれだけの条件でも計算量がめちゃくちゃ小さくなることが分かる。

回転対称性等を利用すればもっと高速でできそうですが、計算量4分の1にしかならないのであまりやる気がしないです。

よって、方針としては、各筋におけるクイーンの配置方法全通りを挙げ、その配置方法が可能であるかどうかをチェックすることにした。

C++による実装

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool control_table[8][8];
int queen_rank[8] = {0, 1, 2, 3, 4, 5, 6, 7}; 

//解の描画
void draw_board(){
    cout << "a b c d e f g h" << endl;
    for(int file = 0; file < 8; file++){
        for(int rank = 0; rank < 8; rank++){
            if(queen_rank[file] == rank) cout << "q ";
            else cout << ". ";
        }
        cout << file + 1;
        cout << endl;
    }
}

void init_control_table(){
    for(int i = 0; i < 8; i++){
        for(int j = 0; j < 8; j++){
            control_table[i][j] = true;
        }
    }
}

//queenをfile, rankにおいた時に生まれる利きの追加
void addQueen(int file, int rank){
    //縦の利き
    for(int tmp_file = 0; tmp_file < 8; tmp_file++){
        control_table[tmp_file][rank] = false;
    }
    //横の利き
    for(int tmp_rank = 0; tmp_rank < 8; tmp_rank++){
        control_table[file][tmp_rank] = false;
    }
    //斜めの利き
    for(int i = 0; i < 8; i++){
        if((file + rank - i >= 0) && (file + rank - i < 8)){
            control_table[file + (rank - i)][i] = false;
        }
        if((file - rank + i >= 0) && (file - rank + i < 8)){
            control_table[file - (rank - i)][i] = false;
        }
    }
}

int main(){
    int count = 0;
    do{
        bool flag = true;
        init_control_table();
        for(int i = 0; i < 8; i++){
            if(control_table[i][queen_rank[i]]){
                addQueen(i, queen_rank[i]);
            }else{
                flag = false;
                break;
            }
        }
        if(flag){
            count += 1;
            cout << "solution No." << count << endl;
            draw_board();
            cout << endl;
        }
    }while(next_permutation(queen_rank, queen_rank + 8));


}

出力結果例

solution No.91
a b c d e f g h
. . . . . . . q 1
. . q . . . . . 2
q . . . . . . . 3
. . . . . q . . 4
. q . . . . . . 5
. . . . q . . . 6
. . . . . . q . 7
. . . q . . . . 8

solution No.92
a b c d e f g h
. . . . . . . q 1
. . . q . . . . 2
q . . . . . . . 3
. . q . . . . . 4
. . . . . q . . 5
. q . . . . . . 6
. . . . . . q . 7
. . . . q . . . 8

解は全部で92個あることがわかりました。
ということで92番目の解をレイトン教授に提出したところ

良かったです。