递归回溯法求N皇后问题

>问题描述：在一个N*N(比如4*4)的方格中，在每一列中放置一个皇后，要求放置的皇后不在同一行，同一列，同一斜线上，求一共有多少种放置方法，输出放置的数组。 >思路解析：从(1，1）开始，一列一列的放置皇后，第一列放置在(1,1)。第二列（1,2）不行，（2,2）不行，（2,3)可以，自此第2列放置完成。第三列依次判断。 可以看到对于第j列都要从第一行开始判断(1,j),(2,j),(3,j)...(N,j)。如果有一个满足则暂停该列，向后判断下一列，（1，j+1）,(2,j+1),(3,j+1)...(N,j+1), 同样出现第一个满足放置的(i,j+1)就要暂停该列，继续向下一列，直到第N列。第N列判断完成后，返回N-1列继续执行(i,N-1),(i+1,N-1)...可以看出每一列都要重复 判断，可以考虑递归算法queen(int column,int(*a)N) 在queen中若column=N-1(有下标)，则全局变量number++,输出二维数组a,当递归返回时，注意恢复数值为0, 比如suit(i,column,a)满足放置条件，则递归进入queen(column+1,a)，返回后要令a[i][column]==0; ``` #include #include #include //判断点(i,j)是否合适 bool suit(int m, int n,int (*a)[4]) { int i, j; for (j = 0; j < 4; j++) {//判断同一行 if (a[m][j] == 1&&j!=n) return false; } for (i = 0; i < 4; i++) {//判断同一列 if (a[i][n] == 1&&i!=m) return false; } for ( i = m - 1, j = n - 1; i >= 0&& j >= 0; i--, j--) { if (a[i][j] == 1) { return false; } } for ( i = m + 1, j = n - 1; i < 4&&j >= 0; i++, j--) { if (a[i][j] == 1) { return false; } } } void queen(int number,int column,int (*a)[4]) { if (column == 4) { for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { printf_s("%d", a[i][j]); } printf_s("\n"); number++; } } for (int i = 0; i <4; i++) { if (suit(i, column,a)) { a[i][column] = 1; queen(number,column+1, a);//从这里返回 a[i][column] = 0; } } } int main() { int a[4][4]; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { a[i][j] = 0; } } static int number = 0; queen(number,0, a); system("pause"); } ``` >[代码借鉴](https://www.cnblogs.com/xumenger/p/4311970.html)