526互联

下午试题四举例一--N皇后问题

发布时间 2023-11-01 14:57:45作者: yesyes1

学完了前面三种例题，看到算法这里真的对我来说是眼前一花，但也是换思维的好机会；

接下来就是主要看懂学会第四种题型啦~~~~

1、非递归求解N皇后问题

#include<stdio.h>

#define N 4

int q[N + 1];//存放皇后问题的列号

int check(int j) {
	for (int i = 1; i < j; i++) {
		if (q[i] == q[j] || abs(i-j) == abs(q[i]-q[j])) {
			return 0;
		}
	}
	return 1;
}

void queen() {
	//初始化
	for (int i = 0; i < N; i++) {
		q[i] = 0;
	}

	int answer = 0;//方案数量

	int j = 1;
	while (j >= 1) {
		q[j] = q[j] + 1;

		//如果在同一列，进行处理
		if (q[j] <= N && !check(j)) {
			q[j] = q[j] + 1;

		}

		if (q[j] <= N) {
			if (j == N) {
				answer = answer + 1;
				printf("方案%d：", answer);

				for (int i = 1; i <= N; i++) {
					printf("%d ", q[i]);
				}

				printf("\n");
			}
			else {
				j = j + 1;
			}
		}
		else {
			q[j] = 0;
			j = j - 1;
		}
	}

}
int main() {
	queen();
	return 0;
}

2、递归求解N皇后问题--循环、迭代

#include<stdio.h>
#include<math.h>

#define N 4

int answer = 0;//方案数量
int q[N + 1];//存放皇后问题的列号

int check(int j) {
	for (int i = 1; i < j; i++) {
		if (q[i] == q[j] || abs(i-j) == abs(q[i]-q[j])) {
			return 0;
		}
	}
	return 1;
}

void queen(int j) {
	//初始化
	for (int i = 0; i < N; i++) {
		q[j] = i;

		if (check(j)) {
			if (j == N) {
				answer = answer + 1;
				printf("方案%d：", answer);

				for (int i = 1; i <= N; i++) {
					printf("%d ", q[i]);
				}
				printf("\n");
			}
			else {
				queen(j + 1);
			}
		}
	}

}
int main() {
	queen(1);
	return 0;
}