یکی از معروف ترین سوال ها برای آموزش الگوریتم و روش عقبگرد  (Backtraking)  مسیله هشت وزیر یا n queens  است که علاوه بر سادگی زیبایی خاصی هم دارد .

مسیله  n وزیر به شرح زیر است:

فرض کنید که صفحه شطرنجی به ابعاد  n *n  دارید ، چگونه می توان  n عدد وزیر (نمی دونم چرا ما به ملکه در شطرنج می گوییم وزیر !!) را در صفحات شطرنج قرار داد به طوری که هم را تهدید نکنند.

قبل از شروع حل ابتدا بگذارید نحوه حرکت وزیر را در صفحه شطرنج مرور کنیم ، یک وزیر می تواند همانند تصویر زیر در راستای افقی و عمودی و دو قطر حرکت و آن خانه ها را تحت پوشش خود قرار دهد.

حرکت وزیر در صفحه شطرنج

معرفی روش عقبگرد – backtracking :

عقبگرد یا همان backtracking  روشی است که در آن تمام حالت های ممکن ساخته می شود و هر حالتی که ساخته می شود چک می شود تا درست یا غلط بودن آن بررسی شود و اگر غلط بود حالتی دیگر را تولید می کند و همین طور ادامه می دهد.

برای راحتی در توضیح فرض  کنیم که می خواهیم چهار وزیر را در صفحه شطرنجی با ابعاد ۴ * ۴ قرار دهیم . به شکل زیر که درخت تمام حالت های ممکن برای قرار گیری وزیر ها در صفحه شطرنج هستند دقت کنید :

شکل بالا درخت تمام حالاتی است که ۴ وزیر را می توان در صفحه شطرنج ۴ در ۴ قرار داد . وزیر اول می تواند در ستون های ۱ تا چهار قرار بگیرد ، وزیر دوم هم می تواند در خانه های ۱ تا چهارم قرار بگیرئ و همین طور تا آخر .

ولی جواب را چگونه از روی درخت بالا به دست آوریم ؟ ابتدا ما باید بتوانیم یک حالت را از درخت به دست بیاوریم که این کار با استفاده از پیمایش عمقی یا preorder امکان پذیر است.

در پیمایش پیش ترتیب یا عمقی ابتدا ریشه دیده می شود و بعد از آن فرزندان ، در زیر چند پیمایش preorder اول را می نویسم :

    <1,1><2,1><3,1><4,1>

   <1,1><2,1><3,1><4,2>

   <1,1><2,1><3,1><4,3>

   <1,1><2,1><3,1><4,4>

   <1,1><2,1><3,2><4,1>

   <1,1><2,1><3,2><4,2>

   <1,1><2,1><3,2><4,3>

   <1,1><2,1><3,2><4,4>

    <1,1><2,1><3,3><4,1>

   <1,1><2,1><3,3><4,2>

   <1,1><2,1><3,3><4,3>

   <1,1><2,1><3,3><4,4>

   <1,1><2,1><3,4><4,1>

   <1,1><2,1><3,4><4,2>

   <1,1><2,1><3,4><4,3>

   <1,1><2,1><3,4><4,4>

    <1,1><2,2><3,1><4,1>

   <1,1><2,2><3,1><4,2>

   <1,1><2,2><3,1><4,3>

   <1,1><2,2><3,1><4,4>

   <1,1><2,2><3,2><4,1>

   <1,1><2,2><3,2><4,2>

   <1,1><2,2><3,2><4,3>

   <1,1><2,2><3,2><4,4>

    <1,1><2,2><3,3><4,1>

   <1,1><2,2><3,3><4,2>

   <1,1><2,2><3,3><4,3>

   <1,1><2,2><3,3><4,4>

   <1,1><2,2><3,4><4,1>

   <1,1><2,2><3,4><4,2>

   <1,1><2,2><3,4><4,3>

   <1,1><2,2><3,4><4,4>

       .

       .

       .

همین طور که می بینید اگر درخت حالات را پیمایش پیش ترتیب یا Preorder کنیم تمام حالاتی که ۴ وزیر در صفحه چهار در چهار قرار می گیرد را به صورت منظم به دست می آوریم حالا کل حالت های ممکن را داریم و برای رسیدن به جواب کافی است  که تک تک حالت ها را بررسی کنیم ببینیم که وزیر ها هم را تهدید می کنند یا نه ! اگر هیچ کدام از وزیر ها مورد تهدید نبودند معلوم می شود آن حالت یکی از جوا هاست و آن را چاپ می کنیم و اگر وزیری مورد تهدید بود معلوم می شود که آن حالت جواب ما نیست و ما باید به سراغ حالت بعدی برویم.

برای بررسی اینکه ببینیم وزیر ها هم را تهدید می کنند یا نه تابع promising را در زیر نوشته ام که در آن :

s : آریه ای است که خانه صفرم آن حاوی ستون وزیری صفرم است (وزیری که در سطر صفر) است ، خانه ی یکم آن حاوی ستون وزیر یکم است (وزیری که در سطر صفر) است و …
n : تعداد خانه های آرایه یا همام تعداد وزیران

limit : limit  سطری از درخت است که در آن قرار داریم فرض کنید در سطر دوم  درخت قرار داریم اون موقع برای بررسی این که ببینیم وزیر ها هم را تهدید می کنند یا باید وضعیت دو وزیر اول را چک کینم زیرا وقتی در سطح دوم هستیم فقط از وضعیت دو وزیر اول آگاه هستیم و از وضعیت سایر وزیر ها اطلاع ندارم و limit هم می گوید ما اکنون در کدام سطح از درخت قرار داریم

bool promising(int* s, int n, int limit)//s array of position , n number of queens
{
	if (limit == 0)
	{
		return true;
	}
	for (int i = 0; i <= limit - 1; i++)
	{
		for (int j = i + 1; j <= limit; j++)
		{
			if ((s[i] >= n) || (s[j] >= n) || (s[i] == s[j] || i - j == s[i] - s[j] || i - j == s[j] - s[i]))
			{
				return false;
			}
		}
	}
	return true;
}

خروجی این تابع یک مقدار منطقی است . اگر وزیر ها هم را تهدید نکنند مقدار  true برمی گرداند اگر نه false بر می گرداند.

سوال دیگری که پیش می آید این است که آیا ما باید تمام درخت را ابتدا تولید کنیم و بعد به سراغ حل سوال برویم ؟ جواب به طرز روشنی منفی است ، ما لزومی به تولید درخت نداریم می توانیم در حین برنامه قسمت های مورد نظر از درخت (مسیر ها ) را تولید کنیم .

برای حل سوال دو تابع دیگر نوشتم n_solve_queen و n_queen که در ادامه توضیح می دهمشان.

تابع n_solve_queen  آرایه s را تولید می کند و تابع اصلی که n_queen  است را فرا می خواند و همین طور وضعیت وزیر صفرم (وزیر سطر صفر) در این تابع فراخوانی می شود

void solve_n_qeen(int n)
{
	int *s;
	s = new int[n];
	
	for (int i = 0; i < n; i++)
	{
		s[0] = i;
		n_queen(s, n, 0);
	}
}

تابع بعدی تابع n_queen است که آرگمان هایش دقیقا مانند تابع promising است . در ابتدا که وارد این تابع می شویم تابع promising چک می کند که آیا تا سطر limit , limit وزیر اول هم را تهدید می کنند یا نه . اگر هم را تهدید بکنند تابع تمام می شود ولی اگر هم را تهدید نکنند یک شرط دیگر بررسی می شود ، شرط جدید می گوید آیا الان در سطر آخر(وزیر آخر) قرار داریم یا نه .اگر در سطر آخر قرار داشتیم یعنی توانسته ایم n وزیر را بدون اینکه هم را تهدید کنند در یک صفحه شطرنج n در n قرار دهیم ولی اگر در سطر آخر نبودیم خود تابع n_queen را برای سطر بعد فرا می خوانیم به طوری که بار اول وزیر در ستون صفرم باشد و بار بعدش ستون یکم و همین طور تا ستون n-1 ام.

void n_queen(int *s, int n, int limit)
{
	static int counter = 0;
	if (promising(s,n,limit))
	{
		if (limit == n-1)
		{
			int row = 0;
			counter++;
			cout << setw(3) << counter << ": ";
			for (int i = 0; i < n; i++)
			{
				cout << setw(2) << "(" << row << "," <<s[i] << ")";
				row++;
			}
			cout << endl;
		}
		else
		{
			for (int j = 0; j < n; j++)
			{
				s[limit + 1] = j;
				n_queen(s, n, limit+1);
			}
		}
	}
}

در زیر کد کامل برنامه n – queens  ( هشت وزیر )  قرار دارد :

// n-Queen.cpp : open-mind.ir
//
#include "stdafx.h"
#include <iostream>
#include <iomanip>

using namespace std;

bool promising(int* s, int n, int limit)//s array of position , n number of queens
{
	if (limit == 0)
	{
		return true;
	}
	for (int i = 0; i <= limit - 1; i++)
	{
		for (int j = i + 1; j <= limit; j++)
		{
			if ((s[i] >= n) || (s[j] >= n) || (s[i] == s[j] || i - j == s[i] - s[j] || i - j == s[j] - s[i]))
			{
				return false;
			}
		}
	}
	return true;
}


void n_queen(int *s, int n, int limit)
{
	static int counter = 0;
	if (promising(s,n,limit))
	{
		if (limit == n-1)
		{
			int row = 0;
			counter++;
			cout << setw(3) << counter << ": ";
			for (int i = 0; i < n; i++)
			{
				cout << setw(2) << "(" << row << "," <<s[i] << ")";
				row++;
			}
			cout << endl;
		}
		else
		{
			for (int j = 0; j < n; j++)
			{
				s[limit + 1] = j;
				n_queen(s, n, limit+1);
			}
		}
	}
}

//open-mind.ir
void solve_n_qeen(int n)
{
	int *s;
	s = new int[n];
	
	for (int i = 0; i < n; i++)
	{
		s[0] = i;
		n_queen(s, n, 0);
	}
}


int main()
{
	int n;
	cout << "Enter n(number of queens in n*n board) ::";
	cin >> n;
	solve_n_qeen(n);
	
	return 0;
}

وقتی برنامه را برای ۸ وزیر اجرا کردم ۹۲ جواب به دست آمد که در زیر بخشی از آن را می بینید

و وقتی برای ۱۶ وزیر اجرا کردم در طی شش ساعت ۸۰۸۰۰۰ جواب مختلف پیدا کردم و اگر می خواستم تمام جواب های ممکن را پیدا احتمالا باید نزدیک به یک روز برنامه را در حال اجرا می گذاشتم و در زیر بخشی از جواب ها را می توانید برای ۱۶ وزیر ببینید :

البته می توانید این برنامه را بدون بازگشتی حل کنید که سرعت خیلی بیشتری هم دارد اما من سوال را برای مقاصد آموزشی به این طریق حل کردم.

و در آخر اگر کد این برنامه را با زبان های دیگر یا روشی دیگر نوشته اید آن را برای ما ایمیل کنید تا در همین پست قرارش دهیم.