程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj3239 Solution to the n Queens Puzzle (n皇後問題)

poj3239 Solution to the n Queens Puzzle (n皇後問題)

編輯:關於C++

Solution to the n Queens Puzzle Time Limit: 1000MS Memory Limit: 131072K Total Submissions: 3494 Accepted: 1285 Special Judge

Description

The eight queens puzzle is the problem of putting eight chess queens on an 8 × 8 chessboard such that none of them is able to capture any other. The puzzle has been generalized to arbitrary n × n boards. Given n, you are to find a solution to the n queens puzzle.

\

Input

The input contains multiple test cases. Each test case consists of a single integer n between 8 and 300 (inclusive). A zero indicates the end of input.

Output

For each test case, output your solution on one line. The solution is a permutation of {1, 2, …, n}. The number in the ith place means the ith-column queen in placed in the row with that number.

Sample Input

8
0

Sample Output

5 3 1 6 8 2 4 7

解題思路:

一、當n mod 6 != 2 或 n mod 6 != 3時:


[2,4,6,8,...,n],[1,3,5,7,...,n-1] (n為偶數)


[2,4,6,8,...,n-1],[1,3,5,7,...,n ] (n為奇數)

二、當n mod 6 == 2 或 n mod 6 == 3時


(當n為偶數,k=n/2;當n為奇數,k=(n-1)/2)


[k,k+2,k+4,...,n],[2,4,...,k-2],[k+3,k+5,...,n-1],[1,3,5,...,k+1] (k為偶數,n為偶數)

[k,k+2,k+4,...,n-1],[2,4,...,k-2],[k+3,k+5,...,n-2],[1,3,5,...,k+1],[n] (k為偶數,n為奇數)

[k,k+2,k+4,...,n-1],[1,3,5,...,k-2],[k+3,...,n],[2,4,...,k+1] (k為奇數,n為偶數)

[k,k+2,k+4,...,n-2],[1,3,5,...,k-2],[k+3,...,n-1],[2,4,...,k+1],[n ] (k為奇數,n為奇數)

(上面有六條序列。一行一個序列,中括號是我額外加上的,方便大家辨認子序列,子序列與子序列之間是連續關系,無視中括號就可以了。第i個數為ai,表示在第i行ai列放一個皇後;... 省略的序列中,相鄰兩數以2遞增。)

參考代碼:

#include
#include
using namespace std;

int main(int i)
{
	int n;  //皇後數
	while(cin>>n)
	{
		if(!n)
			break;

		if(n%6!=2 && n%6!=3)
		{
			if(n%2==0)  //n為偶數
			{
				for(i=2;i<=n;i+=2)
					cout<


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved