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

براي فهم بهتر مساله تئوري بالا را با يک مثال توضيح خواهيم داد. فرض کنيد 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+

queens(i+

}

}

}

bool promising(index i){

index k;

bool switch;

k =

switch = true;

while(k«i && switch){

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

switch = false;

k++;

}

return switch;

}

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