| تبليغات | X |
با سلام خدمت همه شما عزیزان. در پست قبلی فقط جواب مسئله مشهور 8 وزیرو براتون گذاشتم. اما امروز می خوام روش حل مسئله مشهور 8 وزیرو و بطور کلی n وزیرو براتون شرح بدم.
این مسئله بدین صورته که شما باید 8 وزیرو طوری تو صفحه شطرنج قرار بدین تا هیچکدوم نتونه یکی دیگه رو برداره.جالبه بدونین که این مسئله تقریبا قدمتی به اندازه ابداع خود شطرنجهبرای همین معلوم نیست اولین با چه کسی اونو مطرح کرده.ولی ظاهراً آقای Karl Friedrich Gauss ( ریاضی دان آلمانی ) اونو برای اولین بار حل کرد.پیدا کردن تنها یک راه حل آنگونه که در ادامه می بینیم کار سختی نیست اما اگر بخواهیم همه راه حل ها رو بدست بیاریم دیگه کار خیلی سخت می شه.روش بازگشتی ( Backtracking ) ه در طراحی سیستم های خبره کاربرد زیادی داره تنها راه حل شناخته شده برای این مسئله مشهوره. برای 8 وزیر ما 12 راه حل یکتا و با روش متقارن سازی ما 92 روش داریم.
حال شما مسئله رو در حالت کلی n وزیر در نشر بگیرین.اگر n عددی اول باشه یک راه به راحتی با رسم یک خط راست در یک صفحه n*n محدود به وجود می یاد. تا زمانیکه هیچ دو خط راستی همدیگرو در بیشتر از یک نقطه قطع نمی کنن، خط مستقیم y= a*x+b که برابر 1 یا 1- نیست می تونه یک راه حل باشه.طول عرض مختصات از 0 شروع می شه:
N=7 ; y=2x --à (0,0) , (1,2) , (2,4) , (3,6) , (4,1) , (5,3) , (6,5);
حتما می دونین که 8 = 2 * 4 ، بله به سواد خودتون شک نکنین چون صفحه ما بیشتر از 7 خونه نداره مجبور شدیم از اون 7 تا کم کنیم . (-:
با a= 2,3,4,5 و b=0,1,2,3,4,5,6 به راحتی می شه 28 راه حل پیدا کرد.
برای اعدادی که اول نیست یا به عبارتی مختلط هستن که می تونیم اونا رو به صورت n=p * q تعریف کنیم ، ما می تونیم با یک ضرب مستقیم از راه حل های p وزیر و q وزیر تموم راه حل ها رو بدست بیاریم.بدین صورت که هر وضعیت مکانی باری مسئه p وزیر یک راه حل هم برای مسئله q وزیر به حساب می یاد.مثلاً برای 5*7=35 ما می تونیم 10*40 ̂ 7 + 40 * 10 ̂ 5 راه حی داشته باشیم. خیلی بزرگه نه؟
برای ایجاد یک راه حل در حالت کلی n بذارین در نظر بگیریم که یک سطح تقسیم شده به صورت j = 0,1,…,n-1 و i=0,1,…,n-1 داشته باشیم.
حال فرض کنید n یک عدد زوج باشه.داریم:
1) if n is not 6k+2
j=2i+1, for 0 <=i< n/2
j=2i mod n, for n/2 <= i < n
2) if n is not 6k
j= (n/2 + 2i-1) mod n, for 0 <= i < n/2
j=(n/2 + 2i+2) mod n ,for n/2 <= i < n
امیدوارم که مطلب تقریباً براتون روشن شده باشه.
راستی جالبه یه مطلب راجع به سوپر وزیر (SuperQueen ) به شما بگم. در نظر بگیرین علاوه بر حالت فوق وزیر ها نتونن از طریق حرکت اسب یا همون L معروف همدیگرو بزنن! به نظر شما این راه حل وجود داره؟ جالبه بدونین که این راه از صفحه 10 * 10 شروع می شه و در این صفحه تنها 1 مورد راه حل وجود داره!
پایین شما یک جدول از ره های ممکنه برای این مسئله می بینین. نظرتون چیه ؟؟؟!!!!!!!!!
Order < -----
Ordinary Queens -----
> < ---- Superqueens ---- >
Exec
(“N”) Total Solutions Unique
Solutions Total Sol.
Unique Sol. Time
------------------------------------------------------------------------------------------
1
1
1
1 1
2
0
0
0 0
3
0
0
0 0
4
2
1
0 0
5
10
2
0 0
6
4
1
0 0
7
40
6
0 0
8
92
12
0 0
9
352
46
0
0
10
724
92
4 1
11
2,680
341
44 6
12
14,200
1,787
156 22
13
73,712
9,233
1,876 239
14
365,596
45,752
5,180
653 0.2 sec.
15
2,279,184
285,053
32,516 4,089 1.9
sec.
16
14,772,512
1,846,955
202,900 25,411 11.2 sec.
17
95,815,104
11,977,939
1,330,622 166,463 77.2 sec.
18
666,090,624
83,263,591 8,924,976
1,115,871 9.6 min.
19
4,968,057,848
621,012,754 64,492,432
8,062,150 75.0 min.
20
39,029,188,884
4,878,666,808 495,864,256
61,984,976 10.2 hrs.
21
314,666,222,712
39,333,324,973 3,977,841,852
497,236,090 87.2 hrs.
22
2,691,008,701,644 336,376,244,042
34,092,182,276 4,261,538,564 31.9 days
23 24,233,937,684,440
3,029,242,658,210 306,819,842,212 38,352,532,487 296
days
