八皇后问题的相关C++代码解答示例
需积分: 9 30 浏览量
2020-12-31
09:20:44
上传
评论
收藏 73KB PDF 举报
八皇后问题的相关八皇后问题的相关C++代码解答示例代码解答示例
八皇后问题即指在一个8*8的棋盘上放置8个皇后，不允许任何两个皇后在棋盘的同一行、同一列和同一对角线上。关键字：
递归、上溯.通用技巧：
经观察发现，对8 x 8的二维数组上的某点a[i][j](0<=i,j<=7)
其主对角线（即左上至右下）上的每个点的i-j+7的值（范围在(0,14)）均相等；
其从对角线（即右上至左下）上的每个点的i+j的值（范围在(0,14)）均相等；
且每个主对角线之间的i-j+7的值均不同，每个从对角线之间的i-j+7的值亦不同；
如a[3][4]:
主：3-4+7=6
从：3+4=7
因此可设两个数组b[15],c[15]分别表示主、从对角线是否安全
（为1表示有皇后，不安全；为0表示安全）
每行有且仅有一个皇后：
每i个皇后放在每i行(0<=i<=7)
void eightQueens( int line );
题目描述：题目描述：
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方
格），使它们谁也不能被吃掉！这就是著名的八皇后问题。
对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2…b8，其中bi为相应摆法中第i行皇后所处的列
数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。
给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。
输入：
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1 <= b <= 92)
输出：
输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。
样例输入：
2
1
92
样例输出：
15863724
84136275
思路思路
先贴出一个可以ac的摆放位置出来，防止大家连国际象棋棋盘的样子都不清楚。
由于八个皇后不能处在同一行，那么可以肯定每个皇后占据一行。我们可以先定义一个数组column[9],数组中的第i个数字表示
位于第i行皇后的列号(因为数组下标从0开始，因此这里想表示1-8需要申请9个整型的数据空间)。
先把column数组初始化为1-8,忽略开始的第一个元素
接下来，对column做无重复的全排列，因为我们使用不同的数字对column进行初始化，所以八皇后肯定在不同的列。
接下来，我们只需要判断八皇后是否在同一对角线即可，学过数学的都知道，可以表示为y = x + b 或者 y = -x + b
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define EIGHT 8
struct result
{
评论0