递归回溯法求N皇后问题

时间:2024-01-26 16:43:01

问题描述:在一个NN(比如44)的方格中,在每一列中放置一个皇后,要求放置的皇后不在同一行,同一列,同一斜线上,求一共有多少种放置方法,输出放置的数组。

思路解析:从(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<stdio.h>
#include<string.h>
#include<stdlib.h>
//判断点(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");


}

代码借鉴