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

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

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

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

کد زیر برای حالت شمارش جواب ها ( SINGLE_SOLUTION=0 ) تا $n=14$ جواب می‌دهد و برای حالت گزارش یک جواب تا $n=30$ در زمان خوبی جواب می‌دهد.

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;
}

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

• Hill Climbing
• Simulated annealing

‌‌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
//

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

• سوال عملی دوره‌ی تابستان ۲۴ [سطح: ساده]

• معمای 8 وزیر
• Hill Climbing