====== عنوان مطلب ======


===== تعریف =====
 چگونه می توان $n$ مهره‌ی وزیر شطرنج را در یک صفحه‌ی $n*n$ شطرنج چید به طوری که هیچ $2$ مهره از این $n$ مهره یک دیگر را تهدید نکنند؟


===== الگوریتم =====
ساده‌ترین شکل الگوریتم به این صورت است:

از سطر اول صفحه شروع کرده ، در هر سطر به صورت بازگشتی هر دفعه یکی از ستون  $1$ تا $n$ را به وزیر سطر $i$ اختصاص داده و سپس به سطر های بعد می‌رویم. در صورتی که دو وزیر همدیگر را تهدید کنند به مرحله‌ی قبل باز می‌گردیم. در  صورتی که همه‌ی $n$ وزیر را در صفحه قرار دهیم، جواب را گزارش می کنیم.

===== پیچیدگی‌ الگوریتم =====
پیچیدگی الگوریتم بالا  $O(n!)$ است.


===== پیاده‌سازی =====
کد زیر برای حالت شمارش جواب ها ( SINGLE_SOLUTION=0 ) تا $n=14$ جواب می‌دهد و برای حالت گزارش یک جواب تا $n=30$ در زمان خوبی جواب می‌دهد.
<code c queens.cpp>
#include <iostream>
#define SINGLE_SOLUTION 0
#define PRINT_SOLUTIONS 0

using namespace std;
const int maxn = 100;
int n;
int a[maxn];
int mark[maxn];
int markd1[maxn*2];
int markd2[maxn*2];
int ans=0;


void acceptboard(){
    ans++;
    if(PRINT_SOLUTIONS){
	    for(int i = 0 ; i < n ; ++i){
		for(int j = 0 ; j < n ; ++j)
		    if(a[i]==j)
			cout << "Q";
		    else{
			cout << ".";
		    }
		cout << endl;
	    } 
   	    cout << endl;
    }
    if(SINGLE_SOLUTION){
	    exit(0);
    }
}

void backtrack(int depth){
    if(depth==n)
        return acceptboard();
    for(int j = 0 ; j < n ; ++j){
        int l = j+depth;
        int r = n+depth-j;
        if(!mark[j] && !markd1[l] && !markd2[r]){            // اگر در ستون جی، قطر چپ ال و قطر راست آر وزیری نبود

	    mark[j]=markd1[l]=markd2[r]=true;

	    a[depth]=j;
	    backtrack(depth+1);
	    
	    mark[j]=markd1[l]=markd2[r]=false;

	}	    
}

int main() {
    cin >> n;
    backtrack(0);    
    cout << ans << endl;
    return 0;
}

</code>
===== پیاده‌سازی سریع‌تر =====
حالت یافتن یک جواب را می‌توان با روش های پیشرفته تر از روش پس‌گرد تا اندازه‌ی زیادی سریع کرد. مثلا کد زیر در طی چند ثانیه یک جایگشت از ستون های $10000$ وزیر که یک دیگر را تهدید نمی‌کنند به دست می‌آورد.
برای مطالعه ی بیشتر می‌توانید به لینک های زیر در ویکی‌پدیا مراجعه کنید:

   *[[http://en.wikipedia.org/wiki/Hill_climbing|Hill Climbing]]
   *[[http://en.wikipedia.org/wiki/Simulated_annealing|Simulated annealing]]

<code c ‌‌B.c>
#include <iostream>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <deque>
#include <set>
#include <vector>
#include <map>
#include <string>
#include <cstring>
#include <iomanip>
#include <cstdio>
#include <fstream>
#include <sstream>

#define For(i,a,n) for(int i =a ; i < n ; ++i )
#define all(x) (x).begin(),(x).end()
#define n(x) (int)(x).size()
#define pb(x) push_back(x)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 50000;
int n;
int t=100*1000;
int dl[maxn*2];
int dr[maxn*2];
int ja[maxn];
int r(int i , int j)
{
	return j-i+n-1;
}
int l(int i,  int j)
{
	return i+j;
}
ll k;
int it;

int main()
{
	ios::sync_with_stdio(false);
	srand(4131);
	cin >> n;
	For(i,0,n)
		ja[i]=i;

	do
	{
		random_shuffle(ja,ja+n);
		it=0;
		For(i,0,2*n)
			dl[i]=dr[i]=0;
		For(i,0,n)
		{
			dl[l(i,ja[i])]++;
			dr[r(i,ja[i])]++;
		}
		k=0;
		For(i,0,n)
			k-=dr[r(i,ja[i])]-1;
		For(i,0,n)
			k-=dl[l(i,ja[i])]-1;
		k/=2;
		while(it<t)
		{
			For(f,0,n){
				For(s,f+1,n){
					it++;
//					int f=rand()%n;
//					int s=f;
//					while(s==f)
//						s=rand()%n;
					int si=dr[r(s,ja[s])]+dl[l(s,ja[s])]-dl[l(s,ja[f])]-dr[r(s,ja[f])]-2;
					dr[r(s,ja[s])]--;
					dl[l(s,ja[s])]--;
					dl[l(s,ja[f])]++;
					dr[r(s,ja[f])]++;
					int fi=dr[r(f,ja[f])]+dl[l(f,ja[f])]-dl[l(f,ja[s])]-dr[r(f,ja[s])]-2;
					dr[r(f,ja[f])]--;
					dl[l(f,ja[f])]--;
					dl[l(f,ja[s])]++;
					dr[r(f,ja[s])]++;
					if(fi+si>0|| (!(rand()%(5))) && (k < -1000000))
					{
						swap(ja[f],ja[s]);
						k+=fi+si;
					}
					else
					{
						dr[r(s,ja[s])]++;
						dl[l(s,ja[s])]++;
						dl[l(s,ja[f])]--;
						dr[r(s,ja[f])]--;
						dr[r(f,ja[f])]++;
						dl[l(f,ja[f])]++;
						dl[l(f,ja[s])]--;
						dr[r(f,ja[s])]--;
					}
				}
			}
		}
	}while(k);
	const int DBG=0;
	if(DBG)
	{
		For(i,0,n)
		{
			For(j,0,ja[i])
				cout << ".";
			cout << "Q";
			For(j,ja[i]+1,n)
				cout << ".";
			cout << endl;
		}
	}
	else
	{
		For(i,0,n)
			cout << ja[i]+1 << endl;
	}
	return 0;
}
//
//el psy congroo
//
</code>

===== کابردها =====


**مثال**:
صورت مسئله اینجا می‌آید.

<پاسخ>

پاسخ مسئله اینجا می‌آید

</پاسخ>


===== مسائل نمونه =====


  * [[سوالات_المپیاد:دوره‌ی_تابستان:دوره‌ی_۲۴:عملی_مقدماتی_اول:سوال_۱|سوال عملی دوره‌ی تابستان ۲۴]] [سطح: ساده]
===== مراجع =====

  * [[http://en.wikipedia.org/wiki/Eight_queens_puzzle|معمای 8 وزیر]]
  * [[http://en.wikipedia.org/wiki/Hill_climbing|Hill Climbing]]