首页 > 试题广场 >

八皇后

[编程题]八皇后

热度指数：9648 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。

输入描述:

每组测试数据占1行，包括一个正整数b(1 <= b <= 92)

输出描述:

输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。

示例1

输入

1
92

输出

15863724
84136275

算法知识视频讲解

MEMESOREREMEREDODOLA

发表于 2020-05-16 17:02:06

/* DFS * 行从0到7逐层增加，不会存在重复放到同一行的情况 * 列需要用bool col[8]记录某行是否已经放置 * 对角线则需要用一个bool matrix[8][8](代码里用到矩阵名是dj 展开全文

小帅哥HLB

发表于 2022-02-17 16:06:07

#include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> A; int Q[8][8] = {0}; //因为是从上往下展开全文

健康快乐最重要

发表于 2020-03-27 12:08:10

还没有看大佬的代码，分享我的最朴素的思想。。。遍历一个8*8的图，一行一行进行遍历。每遍历一个点，就把该点的行，列和左斜线，右斜线都进行标记。然后继续访问，如果到了最后一行，那么成功。如果还没到最后一行，就已经都标记完了，则进行回溯。 #include<iostream> #includ 展开全文

小苕

发表于 2023-03-21 20:25:27

#include <stdio.h> #define N 20 int a[N]; int col[N], dg[N], udg[N]; int n; static int m = 1; void Dfs(int u) { if (u == 8) { if(m = 展开全文

牛客440904392号

发表于 2024-10-02 13:40:57

//C++版代码 #include <iostream> #include <vector> #include <unordered_set> using namespace std; unordered_set<int> cols; unordere 展开全文

csyfZhang

发表于 2020-04-23 13:00:16

不到30行代码解八皇后问题：https://blog.csdn.net/csyifanZhang/article/details/105704431↑更好的阅读体验先来看一看洛谷的八皇后问题，有了这个图就显得比较清晰了，就是在8*8或者6*6的棋盘上放置8或者6个棋子，使得棋子所在行列个不相交。建展开全文