Eight Queen Problem

8queen.cpp

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

const int N = 12;

int queen_status[N];

/*
 * AAAA
 * BBBB
 * C(C)CC
 * DDDD
*/

bool check(int cur_row, int planned) {
    for (int i = 0; i < cur_row; i++) {
        if (queen_status[i] == planned) return false;
        if (queen_status[i] == planned - (cur_row - i)) return false;
        if (queen_status[i] == planned + (cur_row - i)) return false;
    }
    return true;
}

int ans_cnt = 0;

int record_ans() {
    cout << "Ans #" << ++ans_cnt << endl;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (queen_status[i] == j) cout << "*";
            else cout << ".";
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}

int dfs(int n) {
    if (n >= N) {
        record_ans();
        return 0;
    }
    for (int i = 0; i < N; i++) {
        if (check(n, i)) {
            queen_status[n] = i;
            dfs(n + 1);
        }
    }
    return 0;
}

int main() {
    dfs(0);
    return 0;
}

/* Answers:
Ans #1
*.......
....*...
.......*
.....*..
..*.....
......*.
.*......
...*....

Ans #2
*.......
.....*..
.......*
..*.....
......*.
...*....
.*......
....*...

Ans #3
*.......
......*.
...*....
.....*..
.......*
.*......
....*...
..*.....

Ans #4
*.......
......*.
....*...
.......*
.*......
...*....
.....*..
..*.....

Ans #5
.*......
...*....
.....*..
.......*
..*.....
*.......
......*.
....*...

Ans #6
.*......
....*...
......*.
*.......
..*.....
.......*
.....*..
...*....

Ans #7
.*......
....*...
......*.
...*....
*.......
.......*
.....*..
..*.....

Ans #8
.*......
.....*..
*.......
......*.
...*....
.......*
..*.....
....*...

Ans #9
.*......
.....*..
.......*
..*.....
*.......
...*....
......*.
....*...

Ans #10
.*......
......*.
..*.....
.....*..
.......*
....*...
*.......
...*....

Ans #11
.*......
......*.
....*...
.......*
*.......
...*....
.....*..
..*.....

Ans #12
.*......
.......*
.....*..
*.......
..*.....
....*...
......*.
...*....

Ans #13
..*.....
*.......
......*.
....*...
.......*
.*......
...*....
.....*..

Ans #14
..*.....
....*...
.*......
.......*
*.......
......*.
...*....
.....*..

Ans #15
..*.....
....*...
.*......
.......*
.....*..
...*....
......*.
*.......

Ans #16
..*.....
....*...
......*.
*.......
...*....
.*......
.......*
.....*..

Ans #17
..*.....
....*...
.......*
...*....
*.......
......*.
.*......
.....*..

Ans #18
..*.....
.....*..
.*......
....*...
.......*
*.......
......*.
...*....

Ans #19
..*.....
.....*..
.*......
......*.
*.......
...*....
.......*
....*...

Ans #20
..*.....
.....*..
.*......
......*.
....*...
*.......
.......*
...*....

Ans #21
..*.....
.....*..
...*....
*.......
.......*
....*...
......*.
.*......

Ans #22
..*.....
.....*..
...*....
.*......
.......*
....*...
......*.
*.......

Ans #23
..*.....
.....*..
.......*
*.......
...*....
......*.
....*...
.*......

Ans #24
..*.....
.....*..
.......*
*.......
....*...
......*.
.*......
...*....

Ans #25
..*.....
.....*..
.......*
.*......
...*....
*.......
......*.
....*...

Ans #26
..*.....
......*.
.*......
.......*
....*...
*.......
...*....
.....*..

Ans #27
..*.....
......*.
.*......
.......*
.....*..
...*....
*.......
....*...

Ans #28
..*.....
.......*
...*....
......*.
*.......
.....*..
.*......
....*...

Ans #29
...*....
*.......
....*...
.......*
.*......
......*.
..*.....
.....*..

Ans #30
...*....
*.......
....*...
.......*
.....*..
..*.....
......*.
.*......

Ans #31
...*....
.*......
....*...
.......*
.....*..
*.......
..*.....
......*.

Ans #32
...*....
.*......
......*.
..*.....
.....*..
.......*
*.......
....*...

Ans #33
...*....
.*......
......*.
..*.....
.....*..
.......*
....*...
*.......

Ans #34
...*....
.*......
......*.
....*...
*.......
.......*
.....*..
..*.....

Ans #35
...*....
.*......
.......*
....*...
......*.
*.......
..*.....
.....*..

Ans #36
...*....
.*......
.......*
.....*..
*.......
..*.....
....*...
......*.

Ans #37
...*....
.....*..
*.......
....*...
.*......
.......*
..*.....
......*.

Ans #38
...*....
.....*..
.......*
.*......
......*.
*.......
..*.....
....*...

Ans #39
...*....
.....*..
.......*
..*.....
*.......
......*.
....*...
.*......

Ans #40
...*....
......*.
*.......
.......*
....*...
.*......
.....*..
..*.....

Ans #41
...*....
......*.
..*.....
.......*
.*......
....*...
*.......
.....*..

Ans #42
...*....
......*.
....*...
.*......
.....*..
*.......
..*.....
.......*

Ans #43
...*....
......*.
....*...
..*.....
*.......
.....*..
.......*
.*......

Ans #44
...*....
.......*
*.......
..*.....
.....*..
.*......
......*.
....*...

Ans #45
...*....
.......*
*.......
....*...
......*.
.*......
.....*..
..*.....

Ans #46
...*....
.......*
....*...
..*.....
*.......
......*.
.*......
.....*..

Ans #47
....*...
*.......
...*....
.....*..
.......*
.*......
......*.
..*.....

Ans #48
....*...
*.......
.......*
...*....
.*......
......*.
..*.....
.....*..

Ans #49
....*...
*.......
.......*
.....*..
..*.....
......*.
.*......
...*....

Ans #50
....*...
.*......
...*....
.....*..
.......*
..*.....
*.......
......*.

Ans #51
....*...
.*......
...*....
......*.
..*.....
.......*
.....*..
*.......

Ans #52
....*...
.*......
.....*..
*.......
......*.
...*....
.......*
..*.....

Ans #53
....*...
.*......
.......*
*.......
...*....
......*.
..*.....
.....*..

Ans #54
....*...
..*.....
*.......
.....*..
.......*
.*......
...*....
......*.

Ans #55
....*...
..*.....
*.......
......*.
.*......
.......*
.....*..
...*....

Ans #56
....*...
..*.....
.......*
...*....
......*.
*.......
.....*..
.*......

Ans #57
....*...
......*.
*.......
..*.....
.......*
.....*..
...*....
.*......

Ans #58
....*...
......*.
*.......
...*....
.*......
.......*
.....*..
..*.....

Ans #59
....*...
......*.
.*......
...*....
.......*
*.......
..*.....
.....*..

Ans #60
....*...
......*.
.*......
.....*..
..*.....
*.......
...*....
.......*

Ans #61
....*...
......*.
.*......
.....*..
..*.....
*.......
.......*
...*....

Ans #62
....*...
......*.
...*....
*.......
..*.....
.......*
.....*..
.*......

Ans #63
....*...
.......*
...*....
*.......
..*.....
.....*..
.*......
......*.

Ans #64
....*...
.......*
...*....
*.......
......*.
.*......
.....*..
..*.....

Ans #65
.....*..
*.......
....*...
.*......
.......*
..*.....
......*.
...*....

Ans #66
.....*..
.*......
......*.
*.......
..*.....
....*...
.......*
...*....

Ans #67
.....*..
.*......
......*.
*.......
...*....
.......*
....*...
..*.....

Ans #68
.....*..
..*.....
*.......
......*.
....*...
.......*
.*......
...*....

Ans #69
.....*..
..*.....
*.......
.......*
...*....
.*......
......*.
....*...

Ans #70
.....*..
..*.....
*.......
.......*
....*...
.*......
...*....
......*.

Ans #71
.....*..
..*.....
....*...
......*.
*.......
...*....
.*......
.......*

Ans #72
.....*..
..*.....
....*...
.......*
*.......
...*....
.*......
......*.

Ans #73
.....*..
..*.....
......*.
.*......
...*....
.......*
*.......
....*...

Ans #74
.....*..
..*.....
......*.
.*......
.......*
....*...
*.......
...*....

Ans #75
.....*..
..*.....
......*.
...*....
*.......
.......*
.*......
....*...

Ans #76
.....*..
...*....
*.......
....*...
.......*
.*......
......*.
..*.....

Ans #77
.....*..
...*....
.*......
.......*
....*...
......*.
*.......
..*.....

Ans #78
.....*..
...*....
......*.
*.......
..*.....
....*...
.*......
.......*

Ans #79
.....*..
...*....
......*.
*.......
.......*
.*......
....*...
..*.....

Ans #80
.....*..
.......*
.*......
...*....
*.......
......*.
....*...
..*.....

Ans #81
......*.
*.......
..*.....
.......*
.....*..
...*....
.*......
....*...

Ans #82
......*.
.*......
...*....
*.......
.......*
....*...
..*.....
.....*..

Ans #83
......*.
.*......
.....*..
..*.....
*.......
...*....
.......*
....*...

Ans #84
......*.
..*.....
*.......
.....*..
.......*
....*...
.*......
...*....

Ans #85
......*.
..*.....
.......*
.*......
....*...
*.......
.....*..
...*....

Ans #86
......*.
...*....
.*......
....*...
.......*
*.......
..*.....
.....*..

Ans #87
......*.
...*....
.*......
.......*
.....*..
*.......
..*.....
....*...

Ans #88
......*.
....*...
..*.....
*.......
.....*..
.......*
.*......
...*....

Ans #89
.......*
.*......
...*....
*.......
......*.
....*...
..*.....
.....*..

Ans #90
.......*
.*......
....*...
..*.....
*.......
......*.
...*....
.....*..

Ans #91
.......*
..*.....
*.......
.....*..
.*......
....*...
......*.
...*....

Ans #92
.......*
...*....
*.......
..*.....
.....*..
.*......
......*.
....*...
*/