N皇後問題

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12904 Accepted Submission(s): 5811

 

Problem Description 在N*N的方格棋盤放置了N個皇後，使得它們不相互攻擊（即任意2個皇後不允許處在同一排，同一列，也不允許處在與棋盤邊框成45角的斜線上。
你的任務是，對於給定的N，求出有多少種合法的放置方法。


Input 共有若干行，每行一個正整數N≤10，表示棋盤和皇後的數量；如果N=0，表示結束。
Output 共有若干行，每行一個正整數，表示對應輸入行的皇後的不同放置數量。
Sample Input

1
8
5
0

Sample Output

1
92
10

好難，好難(⊙o⊙)…百度一份代碼，看一個多小時才懂，是不是智商太低了..........

為了讓更多同學看懂題解，我盡力寫得詳細一點。

 

首先介紹求對角線的方法。x-y求主對角線 x+y求副對角線

舉例：(1,1) (,2,2) (3,3)這些點的x-y都相等，所以能連接成主對角線。同理(1,2) (2,3) (3,4)這些點x-y也相等，也能連成主對角線。

(1,2) (2,1)與(1,3) (2,2),(3,1)這些點的x+y都相等，這些點能連成副對角線。

 

 

 

解題思路： n皇後問題，就是考慮皇後放置的位置，對於每一行，需要枚舉每個可以放置皇後的位置，我們需要判斷當前位置（第i

行）是否滿足條件，即判斷這個位置是否與放置好的前i-1行的皇後的位置相沖突，如果沖突，說明這個位置不合適；則跳到下一列

(注意是列)，若還是沖突，繼續跳到下一列，直到最後一列，如果最後一列也不能放置，則說明此時放置方法出錯，則回到上一個皇

後向之前放置的下一列重新放置。 否則的話，就可以枚舉下一行皇後的位置，直至第n行。

 

具體代碼如下：

 

#include
int num,sum[11],map[11],n,x;

void dfs(int x)
{
	int i,j,sign;
	if(x==n+1)//當放置的皇後超過n時，可行解個數加1
	   num++;
	else
	{
		for(i=1;i<=n;i++)
		{
			sign=1;
			map[x]=i;//將第x個皇後放在第i列 
			for(j=1;j