算法设计与分析 | N皇后问题

2023-12-28 21:25:28
题目描述

会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。

输入

一个整数n( 1 < = n < = 10 )?

输出

每行输出对应一种方案,按字典序输出所有方案。每种方案顺序输出皇后所在的列号,相邻两数之间用空格隔开。如果一组可行方案都没有,输出“no solute!”

样例输入
4
样例输出
2 4 1 3
3 1 4 2

分析:

N皇后问题使用回溯法进行解决,规则是:在 n × n 格的棋盘上放置 n 个皇后,任何 2 个皇后不放在?同一行?或?同一列?或?同一斜线?上。int Place(int* Column, int index)方法用来判断是否放的位置是在?同一行?或?同一列?或?同一斜线?上,如果是则返回0,反之返回1。这里定义逻辑序号从1开始,使用两个while来实现回溯,当Column_Num[index] 里面的index==n的时候,则判断输出Column_Num[n]。?

代码:

//n皇后问题
#include<stdio.h>
#include"stdlib.h"

int Place(int* Column, int index) {
	int i;
	for (i = 1; i < index; i++) {
		int Column_differ = abs(Column[index] - Column[i]);
		int Row_differ = abs(index - i);
		if (Column[i] == Column[index] || Column_differ == Row_differ)
			return 0;
	}
	return 1;
}

void N_Queue(int n) {
	int Column_Num[n + 1];
	int index = 1;
	int i;

	int answer_num = 0;
	for (i = 1; i <= n; i++)
		Column_Num[i] = 0;
	while (index > 0) {
		Column_Num[index]++;
		while (Column_Num[index] <= n && !Place(Column_Num, index))
			Column_Num[index]++;
		if (Column_Num[index] <= n) {
			if (index == n) {
				answer_num++;
				for (i = 1; i <= n; i++) {
					printf("%d ", Column_Num[i]);
				}
				printf("\n");
			}
			else {
				index++;
				Column_Num[index] = 0;
			}
			
		}
		else {
			index--;
		}
		
	}
	if(answer_num==0) printf("no solute!");
}

int main() {
	int n;
	scanf("%d", &n);
	N_Queue(n);
	return 0;
}

文章来源:https://blog.csdn.net/jingling555/article/details/135269459
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。