#include <stdio.h>
#define N 8
void backTrack(int*, int*, int*, int*, int, void (*)(int*));
void print(int*);
int main(void) {
int column[N] = {0}; // 同行是否有皇后
int slash[2 * N] = {0}; // 右上至左下是否有皇后
int backSlash[2 * N] = {0}; // 左上至右下是否有皇后
int queens[N] = {0};
backTrack(column, slash, backSlash, queens, 0, print);
return 0;
}
void backTrack(int* column, int* slash, int* backSlash,
int* queens, int i, void (*take)(int*)) {
// if (queens[0] != 0 ) return;
if(i >= N) {
take(queens);
}
else {
int j;
for(j = 0; j < N; j++) {
if(isVisitable(i, j, column, slash, backSlash)) {
queens[i] = j;
column[j] = slash[i + j] = backSlash[i - j + N] = 1;
backTrack(column, slash, backSlash, queens, i + 1, take);
// column[j] = slash[i + j] = backSlash[i - j + N] = 0;
}
}
}
}
int isVisitable(int i, int j, int* column, int* slash, int* backSlash) {
return !(column[j] || slash[i + j] || backSlash[i - j + N]);
}
void print(int* queens) {
int x, y;
for(y = 0; y < N; y++) {
for(x = 0; x < N; x++) {
printf(" %c", queens
[y
] == x
? 'Q' : '.'); }
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNkZWZpbmUgTiA4IAoKdm9pZCBiYWNrVHJhY2soaW50KiwgaW50KiwgaW50KiwgaW50KiwgaW50LCB2b2lkICgqKShpbnQqKSk7CnZvaWQgcHJpbnQoaW50Kik7CgppbnQgbWFpbih2b2lkKSB7IAogICAgaW50IGNvbHVtbltOXSA9IHswfTsgICAgICAgIC8vIOWQjOihjOaYr+WQpuacieeah+WQjgogICAgaW50IHNsYXNoWzIgKiBOXSA9IHswfTsgICAgIC8vIOWPs+S4iuiHs+W3puS4i+aYr+WQpuacieeah+WQjiAKICAgIGludCBiYWNrU2xhc2hbMiAqIE5dID0gezB9OyAvLyDlt6bkuIroh7Plj7PkuIvmmK/lkKbmnInnmoflkI4gCiAgICBpbnQgcXVlZW5zW05dID0gezB9OyAKCiAgICBiYWNrVHJhY2soY29sdW1uLCBzbGFzaCwgYmFja1NsYXNoLCBxdWVlbnMsIDAsIHByaW50KTsgCiAgICAKICAgIHJldHVybiAwOyAKfSAKCnZvaWQgYmFja1RyYWNrKGludCogY29sdW1uLCBpbnQqIHNsYXNoLCBpbnQqIGJhY2tTbGFzaCwgCiAgICAgICAgICAgICAgIGludCogcXVlZW5zLCBpbnQgaSwgdm9pZCAoKnRha2UpKGludCopKSB7IAogICAgICAgICAgICAgICAJLy8gaWYgKHF1ZWVuc1swXSAhPSAwICkgcmV0dXJuOwogICAgaWYoaSA+PSBOKSB7IAogICAgICAgIHRha2UocXVlZW5zKTsgCiAgICB9IAogICAgZWxzZSB7IAogICAgICAgIGludCBqOwogICAgICAgIGZvcihqID0gMDsgaiA8IE47IGorKykgewogICAgICAgICAgICBpZihpc1Zpc2l0YWJsZShpLCBqLCBjb2x1bW4sIHNsYXNoLCBiYWNrU2xhc2gpKSB7IAogICAgICAgICAgICAgICAgcXVlZW5zW2ldID0gajsgCiAgICAgICAgICAgICAgICBjb2x1bW5bal0gPSBzbGFzaFtpICsgal0gPSBiYWNrU2xhc2hbaSAtIGogKyBOXSA9IDE7IAogICAgICAgICAgICAgICAgYmFja1RyYWNrKGNvbHVtbiwgc2xhc2gsIGJhY2tTbGFzaCwgcXVlZW5zLCBpICsgMSwgdGFrZSk7IAogICAgICAgICAgICAgICAgLy8gY29sdW1uW2pdID0gc2xhc2hbaSArIGpdID0gYmFja1NsYXNoW2kgLSBqICsgTl0gPSAwOwogICAgICAgICAgICB9IAogICAgICAgIH0KICAgIH0KfQoKaW50IGlzVmlzaXRhYmxlKGludCBpLCBpbnQgaiwgaW50KiBjb2x1bW4sIGludCogc2xhc2gsIGludCogYmFja1NsYXNoKSB7CiAgIHJldHVybiAhKGNvbHVtbltqXSB8fCBzbGFzaFtpICsgal0gfHwgYmFja1NsYXNoW2kgLSBqICsgTl0pOwp9Cgp2b2lkIHByaW50KGludCogcXVlZW5zKSB7CiAgICBpbnQgeCwgeTsKICAgIGZvcih5ID0gMDsgeSA8IE47IHkrKykgewogICAgICAgIGZvcih4ID0gMDsgeCA8IE47IHgrKykgewogICAgICAgICAgICBwcmludGYoIiAlYyIsIHF1ZWVuc1t5XSA9PSB4ID8gJ1EnIDogJy4nKTsKICAgICAgICB9CiAgICAgICAgcHJpbnRmKCJcbiIpOwogICAgfQogICAgcHJpbnRmKCJcbiIpOwp9