一、N皇后问题的概念

n 皇后问题，研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 一个皇后可以向水平、垂直以及向斜对角方向移动，如果一个皇后出现在另一个皇后的同一行，同一列或者斜对角，那它就可以被这个皇后攻击。可以通过列举出在棋盘上所有的情况，然后判断每个组合是不是符合的条件。

二、代码步骤

1、对皇后位置对错的判断

2、递归实现N皇后位置的排列

3、定义N皇后的指针并初始化

4、代码入口

5、运行结果

---

三、代码功能

1、对皇后位置对错的判断

bool place(int* paraSolution, int paraT)
{int j;for(j = 1;j < paraT;j++){if(abs(paraT-j) == abs(paraSolution[paraT]-paraSolution[j]) || paraSolution[paraT] == paraSolution[j])return 0; }return 1;

2、递归实现N皇后位置的排列

void backtracking(int* paraSolution,int paraN,int paraT)
{int i;if(paraT > paraN){for(i = 1; i <= paraN; i++){printf("%d ",paraSolution[i]);//打印出每种符合条件的情况}printf("\r\n");}else{for(i = 1;i <= paraN; i++){paraSolution[paraT] = i;if(place(paraSolution,paraT)){backtracking(paraSolution,paraN,paraT+1);}}}
}

3、定义N皇后的指针并初始化

void nQueen(int paraN)
{int i;int* solution = (int*)malloc((paraN + 1) * sizeof(int));for(i = 0;i <= paraN; i++){solution[i] = 0;}backtracking(solution, paraN ,1);
}

4、代码入口

int main()
{nQueen(5);return 1;
}

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

四、整体代码

#include <stdio.h>
#include <malloc.h>
#include <math.h>bool place(int* paraSolution, int paraT)
{int j;for(j = 1;j < paraT;j++){if(abs(paraT-j) == abs(paraSolution[paraT]-paraSolution[j]) || paraSolution[paraT] == paraSolution[j])return 0; }return 1;
}void backtracking(int* paraSolution,int paraN,int paraT)
{int i;if(paraT > paraN){for(i = 1; i <= paraN; i++){printf("%d ",paraSolution[i]);}printf("\r\n");}else{for(i = 1;i <= paraN; i++){paraSolution[paraT] = i;if(place(paraSolution,paraT)){backtracking(paraSolution,paraN,paraT+1);}}}
}void nQueen(int paraN)
{int i;int* solution = (int*)malloc((paraN + 1) * sizeof(int));for(i = 0;i <= paraN; i++){solution[i] = 0;}backtracking(solution, paraN ,1);
}int main()
{nQueen(5);return 1;
}