Eight-queens-problem

雨恨云愁，江南依旧称佳丽。水村渔市，一缕孤烟细。

天际征途，遥认行如缀。平生事，此时凝睇，谁会凭栏意？

Question

在8x8格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

Analysis

使用递归回溯法，从棋盘的第一行开始尝试摆放第一个皇后，摆放成功后，递归一层，再遵循规则在棋盘第二行摆放第二个皇后。如果当前位置无法摆放成功，则向右移动一格再次尝试，如果摆放成功，则继续递归一层，摆放第三个皇后。。。如果某一层看遍了所有格子，都无法成功摆放，则回溯到上一个皇后，让上一个皇后右移一格，再进行递归。如果八个皇后都摆放完毕且符合规则，那么就得到了其中一种正确的解法。

Answer

#include <stdio.h>  
#include <stdlib.h>  
   
#define max 8  
   
int queen[max], sum=0; /* max为棋盘最大坐标 */  
   
void show() /* 输出所有皇后的坐标 */  
{  
    int i;  
    for(i = 0; i < max; i++)  
    {  
         printf("(%d,%d) ", i, queen[i]);  
    }  
    printf("\n");  
    sum++;  
}  
   
int check(int n) /* 检查当前列能否放置皇后 */  
{  
    int i;  
    for(i = 0; i < n; i++) /* 检查横排和对角线上是否可以放置皇后 */  
    {  
        if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i))  
        {  
            return 1;  
        }  
    }  
    return 0;  
}  
   
void put(int n) /* 回溯尝试皇后位置,n为横坐标 */  
{  
    int i;  
    for(i = 0; i < max; i++)  
    {         
        queen[n] = i; /* 将皇后摆到当前循环到的位置 */  
        if(!check(n))  
        {             
            if(n == max - 1)  
            {  
                show(); /* 如果全部摆好，则输出所有皇后的坐标 */  
            }           
            else  
            {  
                put(n + 1); /* 否则继续摆放下一个皇后 */  
            }  
        }  
    }  
}  
   
int main()  
{  
    put(0); /* 从横坐标为0开始依次尝试 */  
    printf("%d", sum);  
    return 0;  
}

参考：http://blog.csdn.net/sxhlovehmm/article/details/46763305