عنوان مطلب

چگونه می توان $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