OJ_八皇后

题干

C++实现

• 深度优先遍历，注意回溯
• 打表法：先求出所有解，再存入一个容器中

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> queenVec;//用来存在所有合法的皇后序列

void DFSFindQueen(vector<int>& queen, int pos) {
	//打算放下一个皇后，//i就是第pos号皇后打算放的列数
	for (int i = 1; i <= 8; ++i) {
		bool isOk = true;
		//j是用来遍历之前已经放好的皇后 0~pos-1
		for (int j = 0; j < pos; ++j) {
			//同列就是queen[j] == i
			//斜对角就是pos-j == queen[j] - i或pos-j == i-queen[j],行数差距等于列数差距
			if (queen[j] == i || pos - j == queen[j] - i || pos - j == i - queen[j]) {
				isOk = false;
				break;
			}
		}
		if (isOk) {
			queen.push_back(i);//将pos号皇后的列数设置好
			if (pos == 7) {
				//8个皇后都已经放好了
				queenVec.push_back(queen);
				printf("\"");
				for (int k = 0; k < 8; k++)
				{
					printf("%d", queen[k]);
				}
				printf("\",\n");
			}
			else {
				DFSFindQueen(queen, pos + 1);
			}
			//回溯
			queen.pop_back();
		}
	}
}

vector<string> queenString = {
	"15863724",
	"16837425",
	"17468253",
	"17582463",
	"24683175",
	"25713864",
	"25741863",
	"26174835",
	"26831475",
	"27368514",
	"27581463",
	"28613574",
	"31758246",
	"35281746",
	"35286471",
	"35714286",
	"35841726",
	"36258174",
	"36271485",
	"36275184",
	"36418572",
	"36428571",
	"36814752",
	"36815724",
	"36824175",
	"37285146",
	"37286415",
	"38471625",
	"41582736",
	"41586372",
	"42586137",
	"42736815",
	"42736851",
	"42751863",
	"42857136",
	"42861357",
	"46152837",
	"46827135",
	"46831752",
	"47185263",
	"47382516",
	"47526138",
	"47531682",
	"48136275",
	"48157263",
	"48531726",
	"51468273",
	"51842736",
	"51863724",
	"52468317",
	"52473861",
	"52617483",
	"52814736",
	"53168247",
	"53172864",
	"53847162",
	"57138642",
	"57142863",
	"57248136",
	"57263148",
	"57263184",
	"57413862",
	"58413627",
	"58417263",
	"61528374",
	"62713584",
	"62714853",
	"63175824",
	"63184275",
	"63185247",
	"63571428",
	"63581427",
	"63724815",
	"63728514",
	"63741825",
	"64158273",
	"64285713",
	"64713528",
	"64718253",
	"68241753",
	"71386425",
	"72418536",
	"72631485",
	"73168524",
	"73825164",
	"74258136",
	"74286135",
	"75316824",
	"82417536",
	"82531746",
	"83162574",
	"84136275"
};


int main()
{
	//vector<int> queen;//用来记录已经放好的，皇后的位置
	//DFSFindQueen(queen, 0);
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		int b;
		scanf("%d", &b);
		printf("%s\n", queenString[b-1].c_str());
	}
	return 0;
}