مساله‌‌ وزیران

برای فهم بهتر مساله تئوری بالا را با یک مثال توضیح خواهیم داد. فرض کنید n‌وزیر را در یک صفحه شطرنج قرار دهیم به‌طوری که هیچ وزیری دیگری را تهدید نکند. می‌دانیم که وزیر در صفحه شطرنج به‌صورت افقی و عمودی و مورب حرکت می‌کند.

برای حل مساله، وزیر اول را در سطر اول و ستون اول قرار می‌دهیم، وزیر بعدی باید در ستون وزیر اول نباشد و با آن به‌صورت مورب رابطه نداشته باشد یعنی اگر مختصات وزیر اول (i,j) باشد و وزیر دوم در مختصات (x,y) باشد، باید رابطه‌های زیر برقرار باشد:

اگر مساله را سطر به سطر یا ستون به ستون حل کنیم یکی از دو رابطه اول خودبه‌خود حذف می‌شود. فرض می‌کنیم که مساله را سطر به سطر حل کنیم، در این صورت رابطه i!=x هیچ‌وقت برقرار نخواهد شد، پس این رابطه را اصلا در محاسبات ذکر نمی‌کنیم.

حال با توجه به مفروضات باید یک درخت رسم کنیم که به آن درخت وضعیت حالت گفته می‌شود. اگر صفحه شطرنج را m*m فرض کنیم، مسیری که از ریشه درخت باید طی کرد تا به برگ‌هایی که در سطح m درخت است برسیم می‌شود جواب مساله ما.

در حل مسائلی که به روش پسگرد حل می‌شود یک تابع به نام Promising وجود دارد که چک می‌کند آیا این مسیری که شروع کردیم منجر به جواب خواهد شد یا خیر، اگر جواب “بله” بود ادامه می‌دهیم و اگر “نه” بود به آخرین وضعیت درست قبلی برمی‌گردیم.

حال تمام مطالب گفته شده را با یک مثال ساده بررسی می‌کنیم.

فرض کنید قرار است 4 وزیر در یک صفحه شطرنجی 4*4 قرار بگیرند به‌طوری که هیچ‌کدام دیگری را تهدید نکند، در زیر تمام حالات ممکن این اتفاق را نشان می‌دهیم.

وزیر اول قرار است در یکی از خانه‌های سطر اول قرار بگیرد.

فرض می‌کنیم ابتدا در خانه (1,1) قرار بگیرد، وزیر دوم در خانه (2,1) و (2,2) نمی‌تواند قرار بگیرد پس تعداد حالات ممکن برای آن دو نقطه‌ است (2,3) و (2,4). حال فرض می‌کنیم که وزیر دوم در خانه (2,3) قرار گرفته‌ باشد، وزیر سوم در هیچ کدام از خانه‌های سطر سوم نمی‌تواند قرار بگیرد، اگر در (3,1) قرار بگیرد وزیر اول آن‌را تهدید می‌کند، اگر در خانه (3,2) قرار بگیرد وزیر دوم به‌صورت مورب آن‌را تهدید می‌کند و همین‌طور الی آخر. در این مرحله به آخرین وضعیت درست بازمی‌گردیم که قرار گرفتن وزیر دوم بود، پس به‌جای اینکه وزیر دوم در (2,3) قرار بگیرد در (2,4) قرار می‌گیرد و نقطه‌ای که وزیر سوم باید قرار بگیرد به‌طوری که وزیر‌های دیگر آن‌را تهدید نکنند خانه (3,2) است (البته (3,2) تنها نقطه‌ای است که وزیر سوم می‌تواند در آن قرار بگیرد).

بسیار خب، واضح است که وزیر چهارم در هیچ نقطه‌ای نمی‌تواند قرار بگیرد، بنابراین به آخرین وضعیت درست مرحله قبل می‌رویم و یکی دیگر از حالات درست آن‌را بررسی می‌کنیم.

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

وزیر اول 3 حالت درست دارد که تست نشده است بنابراین وزیر اول را به وضعیت درست بعدی یعنی نقطه (1,2)‌ می‌بریم و همین‌طور مانند توضیحات بالا مساله را حل می‌کنیم. حال به این نتیجه می‌رسیم که اگر وزیر اول در خانه (1,1) باشد هیچ‌وقت مساله ما حل نخواهد شد.

این روش حل کردن مساله کاربرد‌های فراوانی دارد و در حل خیلی مسائل ما را کمک خواهد کرد. هفته‌های بعد مسائل دیگری را که با این روش حل می‌شوند بررسی خواهیم کرد.

شبه کد:

queens(index i){

index jl

if(promising(i))

if(i == n)

print "col[i] through col[n]”;

else{ for(j=0;j«n;j++){

col[i+1] = j;

queens(i+1);

}

}

}

bool promising(index i){

index k;

bool switch;

k = 1;

switch = true;

while(k«i && switch){

if(col[i] == col[k] || abs(col[i] - col[k]) == i – k)

switch = false;

k++;

}

return switch;

}

امیربهاالدین سبط الشیخ