تبلیغات
دست نوشته ها - معمای ۸ وزیر (N-Queens) | برنامه نویسی + لینوکس و متن باز + روزنوشت + موسیقی

نویسنده: "feeruzy ارسال شده در: " درسی ، "، زمان ارسال: " 22 مهر 90 ساعت 19:20"
معمای ۸ وزیر، مساله ایست در ارتباط با جایگزاری ۸ مهره وزیر شطرنج در یک میز ۸‌‌در‌۸ شطرنج بطوریکه هیچ وزیری مورد حمله وزیر دیگری قرار نگیرد.یک جواب برای این مسأله این گونه است که هیچ دو وزیری در یک سطر، ستون و یا قطری قرار نگیرند.
این مساله قابل تعمیم به تعداد بالاتری مهره در تخته بزرگتر است که به مسأله n-وزیر (N-Queens) مشهور است.(جایگزاری n وزیر در یک میز n در n )
پاسخ این مسأله برای تمامی n‌های طبیعی به استثنای ۲ و ۳ موجود است.

۸ وزیر


تاریخچه :
‌۸-‌وزیر در ابتدا توسط "مکس بزل" یکی از بازیکنان شطرنج در ۱۸۴۸ پیشنهاد شد و در سال‌های بعد بسیاری از ریاضی دانان روی آن کار کردند و سرانجام  "گاوس" مسأله را به n-وزیر تعمیم داد.
اولین پاسخ برای این مسأله در سال ۱۸۵۰ توسط "فرانز ناک" آماده شد.گانتر متد پیدا کردن پاسخ برای مسأله بوسیله دترمینان‌ها ارائه داد.
"دایکسترا " در ۱۹۷۲ این مسأله را برای نشان دادن قدرت آنچه که وی "برنامه نویسی ساخت یافته " بکار گرفت. او در این رابطه تعریفی کامل به نام "الگوریتم جستجوی بازگشتی اول‌عمق " منتشر کرد.

۸-وزیر بعنوان تمرینی در طراحی الگوریتم:
پیدا کردن تمامی پاسخ ها برای ۸-وزیر نمونه‌ای بسیار عالی از مسأله ای ساده اما غیر بدیهی است. به همین دلیل این پازل معمولا برای مثالی از   تتنوع تکنیک های برنامه نویسی همچون "برنامه نویسی تحت محدودیت"، " برنامه نویسی منطقی" یا "الگوریتم تکوینی (وراثتی)" استفاده می گردد.
این پازل  اغلب با الگوریتم بازگشتی بدین صورت که ابتدا n-1 وزیر جایگزین شده و سپس یکی یکی به تعداد مهره ها اضافه می گردد، حل می شود.

نمونه ای از پاسخ های این پازل در تصویر زیر قابل دستیابی است:

"نمایش تصویر"

در ادامه برنامه ای از نیکولاس وایرس به زبان پاسکال درج شده که یکی از جواب های مسأله ۸-وزیر را محاسبه می کند:

program eightqueen1(output);
var i : integer; q : boolean;
    a : array[ 1 .. 8] of boolean;
    b : array[ 2 .. 16] of boolean;
    c : array[ -7 .. 7] of boolean;
    x : array[ 1 .. 8] of integer;
procedure try( i : integer; var q : boolean);
var j : integer;
begin j := 0;
  repeat j := j + 1; q := false;
    if a[ j] and b[ i + j] and c[ i - j] then
    begin x[ i] := j;
      a[ j] := false; b[ i + j] := false; c[ i - j] := false;
      if i < 8 then
      begin try( i + 1, q);
        if not q then
        begin a[ j] := true; b[ i + j] := true; c[ i - j] := true;
        end
      end else q := true
    end
  until q or (j = 8);
end;
begin
for i := 1 to 8 do a[  i] := true;
for i := 2 to 16 do b[  i] := true;
for i := -7 to 7 do c[  i] := true;
try( 1, q);
if q then
  for i := 1 to 8 do write( x[ i]:4);
writeln
end.


آخرین ویرایش در: " 22 مهر 90 ساعت 19:36"
برچسب ها: "8وزیر" ، "nوزیر" ، "الگوریتم" ،
در این ارتباط بخوانید: "8-queens
نظرات