python/C++专题课程/回溯算法/皇后问题（回溯法）/八皇后-暴力法（剪枝）.cpp

#include<bits/stdc++.h>
using namespace std;

//<2F><>ӡ<EFBFBD><D3A1><EFBFBD>̺ͻʺ<CDBB>
void showQueens(int queenArr[], int nlen, int nSolution) {
	//<2F>ⷨ<EFBFBD><E2B7A8><EFBFBD><EFBFBD>
	cout << nSolution << endl;

	for (int i = 0; i < nlen; ++i) {
		//<2F><>ӡ<EFBFBD>ʺ<EFBFBD>ǰ<EFBFBD><C7B0><EFBFBD>ĸ<EFBFBD><C4B8><EFBFBD>
		for (int j = 0; j < queenArr[i]; ++j) {
			cout << "1";//<2F>ո<EFBFBD><D5B8><EFBFBD>
		}
		cout << "Q";//<2F>ʺ<EFBFBD>
		//<2F><>ӡ<EFBFBD>ʺ<EFBFBD><CABA><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ĸ<EFBFBD><C4B8><EFBFBD>
		for (int z = 0; z < nlen - queenArr[i] - 1; ++z) {
			cout << "1";
		}
		cout << endl;
	}
	cout << "                       " << endl;
}

//<2F>жϼ<D0B6><CFBC>鵱ǰ<E9B5B1>м<EFBFBD><D0BC><EFBFBD>ǰ<EFBFBD>ģ<EFBFBD><C4A3>Dz<EFBFBD><C7B2>ǿ<EFBFBD><C7BF><EFBFBD><EFBFBD>е<EFBFBD>ͨ
bool rule(int queenArr[], int num)
{
	//ÿһ<C3BF>У<EFBFBD>ÿһ<C3BF><D2BB>ȥ<EFBFBD><C8A5><EFBFBD><EFBFBD>
	for (int i = 0; i <= num; ++i) {
		for (int j = 0; j <= i - 1; ++j) {
			//<2F>жϻʺ<CFBB><CABA>Ƿ<EFBFBD><C7B7><EFBFBD>ͬһ<CDAC><D2BB>,<2C><>Ϊ<EFBFBD><CEAA>ʱû<CAB1><C3BB><EFBFBD><EFBFBD>ͬһ<CDAC>зţ<D0B7><C5A3><EFBFBD><EFBFBD><EFBFBD><EFBFBD>в<EFBFBD><D0B2><EFBFBD><EFBFBD>ж<EFBFBD><D0B6><EFBFBD>
			if (queenArr[i] == queenArr[j]) {
				return false;
			}
			//<2F>жϻʺ<CFBB><CABA>Ƿ<EFBFBD><C7B7>ڶԽ<DAB6>45<34><35>
			if (abs(queenArr[i] - queenArr[j]) == abs(i - j)) {
				return false;
			}
		}
	}
	return true;
}


//<2F>ƶ<EFBFBD><C6B6>ʺ<EFBFBD>
void enumQueensPositon(int queenArr[], int& nSolution) {
	//<2F><>һ<EFBFBD><D2BB>
	for (queenArr[0] = 0; queenArr[0] < 8; ++queenArr[0]) {
		//<2F>ڶ<EFBFBD><DAB6><EFBFBD>
		for (queenArr[1] = 0; queenArr[1] < 8; ++queenArr[1]) {
			if (!rule(queenArr,1)) {
				continue;
			}
			else {
				for (queenArr[2] = 0; queenArr[2] < 8; ++queenArr[2]) {
					if (!rule(queenArr,2)) {
						continue;
					}
					else {
						for (queenArr[3] = 0; queenArr[3] < 8; ++queenArr[3]) {
							if (!rule(queenArr,3)) {
								continue;
							}
							else {
								for (queenArr[4] = 0; queenArr[4] < 8; ++queenArr[4]) {
									if (!rule(queenArr,4)) {
										continue;
									}
									else {
										for (queenArr[5] = 0; queenArr[5] < 8; ++queenArr[5]) {
											if (!rule(queenArr,5)) {
												continue;
											}
											else {
												for (queenArr[6] = 0; queenArr[6] < 8; ++queenArr[6]) {
													if (!rule(queenArr,6)) {
														continue;
													}
													else {
														for (queenArr[7] = 0; queenArr[7] < 8; ++queenArr[7]) {
															if (!rule(queenArr,7)) {
																continue;
															}
															else {
																++nSolution;
																showQueens(queenArr, 8, nSolution);
															}
														}
													}
												}
											}
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
}

int main() {
	//ÿ<><C3BF><EFBFBD><EFBFBD><EFBFBD><EFBFBD>λ<EFBFBD><CEBB>ʾһ<CABE><D2BB><EFBFBD>ʺ<EFBFBD>
	int queenArr[8] = {  }; 	
	//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʼ<EFBFBD><CABC>
	memset(queenArr, -1, sizeof(queenArr));
	//<2F>ⷨ<EFBFBD><E2B7A8><EFBFBD><EFBFBD>
	int nSolution = 0;

	//<2F><>ʼ<EFBFBD><CABC><EFBFBD><EFBFBD>
	enumQueensPositon(queenArr, nSolution);

	//printf("%d ",nSolution);
	return 0;
}