8queens problem

اذهب الى الأسفل

8queens problem

پست  Movahedi في الجمعة 12 ديسمبر 2008 - 17:29

سلام
دوستاني كه جلسه پيش سر كلاس استاد رهنمون بودند مي دونند درس اين جلسه مسأله 8 وزير بود.توضيح اينكه:
ما 8 وزير داريم مي خواهيم اين 8 وزير رو به گونه اي روي صفحه شطرنج قرار بديم كه همديگر رو تهديد نكنن(مي دونيم صفحه شطرنج يه صفحه 8*8 و حركت هاي مجاز وزير سطري،ستوني،قطر اصلي و فرعي است)پس اگر وزيري درسطر iام و ستون jام قرار داره در اون سطر و ستون و نيز روي قطرهاي اصلي و فرعي كه آن وزير قرار گرفته نبايد وزير ديگه اي قرار بگيره.
كه براي حل اين مسئله از تكنيك promising استفاده كرديم .يه توضيح مختصرم راجب اين تكنيك بدم كه تابع promising در واقع هرس كردن بخشي از گراف يا درخت فضاي حالته كه اين تابع جاهايي كه بديهيه جوابي وجود نداره ديگه ادامه نمي ده.يعني اگه درخت اين مسأله رو رسم كنيم به طوريكه در هر سطر فقط يك وزير داشته باشيم (تهديد سطري نداريم) سطر اول مي تواند از ستون 1 تا 8 مقدار بگيره (1و1 تا 8و1)و در سطر دوم هم براي تمام مقادير سطر اول مي تونه از 1 تا 8 مقدار بگيره (1و2 تا 8و2) و همين طور ادامه مي ديم تا سطر آخر.اما اگر وزير اول در سطر 1 و ستون 1 باشه و وزير دوم در سطر 2 وستون 1 باشه اين دو وزير تهديد ستوني خواهند داشت و ادامه دادن اين زير شاخه بي فايدس،همچنين وزير رو نمي تونيم در سطر 2 و ستون 2 قرار بديم چون تهديد قطري داريم پس از ستون سوم تا ستون هشتم مي تونيم وزير رو قرار بديم كه تهديد ستوني نداشته باشيم.يعني اومديم يه قسمتايي از گراف رو هرس كرد.
اين مقدمات رو گفتم كه آخرش بگم:
source الگوريتم nوزير رو مي تونيد اينجا ببينيد:http://snippets.dzone.com/posts/show/4604
اينجا هم مي تونيد فايل اجرايي اين الگوريتم رو دانلود كنيد و براي n هاي مختلف نتيجه رو ببينيد،جالبه:
http://www.hamedhabibi.com/fa/projects/AiQueen.aspx
avatar
Movahedi

تعداد پستها : 31
تاريخ التسجيل : 2008-11-30

خواندن مشخصات فردي

بازگشت به بالاي صفحه اذهب الى الأسفل

سلام

پست  حمیدرضا زواری في الجمعة 19 ديسمبر 2008 - 17:15

من در جوانی این برنامه رو نوشته بودم و الآن برای دوستان قرار میدم که استفاده کنن
اساس کار برنامه هم همین هستس که شما مطرح کردین
برنامه از Graphics.h برای رسم صفحه شطرنج استفاده می کنه بنا بر این با Visual C اجرا نمیشه لطفا از IDE های تحت DOS استفاده کنید مثل Turbo C
در ضمن برنامه را در انفوان جوانی و در دوره دبیرستان به رشته تحریر در اورده ام پس مرا به سبب مشکلاتم ملامت نفرمایید.


برنامه را فقط برای مطالعه قرار می دهم و راضی به هیچ گونه استفاده دیگری از آن نیستم
8Vazir
avatar
حمیدرضا زواری

تعداد پستها : 13
تاريخ التسجيل : 2008-11-30
العمر : 32

خواندن مشخصات فردي http://360.yahoo.com/AdActivator

بازگشت به بالاي صفحه اذهب الى الأسفل

بازگشت به بالاي صفحه


 
صلاحيات هذا المنتدى:
شما نمي توانيد در اين بخش به موضوعها پاسخ دهيد