数据结构15：N皇后问题

摘要： N皇后问题是指将 N个皇后放在 N×N的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

这个代码实际上比较考验我们对递归的理解，用到了回溯的方式解决N皇后问题。虽然代码不长，但需要我们真的看透还是有一定难度

一.全部代码

#include 
#define N 20   
    
int q[N];//这里是参照了陈青山同学的，在前面定义数组每个函数都能用

int isPlace(int k, int j)
{
    int i;
    for (i = 1; i < k; i++) 
	{
        //这里其实就是不能在同一列和同一斜线上面 
        if (q[i] == j || abs(i - k) == abs(q[i] - j))
            return 0;
    }
    return 1;
}

//传入的k是用来记录行数的，该找第几行的皇后了 
void Nqueens(int k, int n)
{
    int j;//这里用来记录列数 
    if (k > n)     //这里是出口条件 
    {
    	int i;
    	for(i = 1;i <= n;i ++)
        printf("%d ",q[i]);
		printf("n");	
	}
    else
    {
    	//循环该行每一个位置看能否放皇后 
        for (j = 1; j <= n; j++)   
		 
        {
        	
            if (isPlace(k, j))
            {
                q[k] = j;
                 
                Nqueens(k + 1, n);  
            }
        }
    }
}

int main()
{
    int n;
    printf("请输入皇后个数：");
    scanf("%d", &n);
    Nqueens(1, n);
    return 0;
}

二.运行结果

请输入皇后个数：5
1 3 5 2 4
1 4 2 5 3
2 4 1 3 5
2 5 3 1 4
3 1 4 2 5
3 5 2 4 1
4 1 3 5 2
4 2 5 3 1
5 2 4 1 3
5 3 1 4 2