مشکل هشت کوئینز یک مشکل کلاسیک و شناخته شده است. به طور خاص ، هشت ملکه را روی یک تخته شطرنج 8×8 قرار دهید تا هیچ دو ملکه نتوانند به یکدیگر حمله کنند ، به این معنی که هیچ دو ملکه نمی توانند در یک ردیف ، همان ستون یا همان مورب قرار بگیرند. سوال این است: چند راه حل وجود دارد؟
try.demo
هر ردیف یک تخته شطرنج n*n را به عنوان یک دنباله در نظر بگیرید. سلولها را در هر ستون به طور متوالی از 1 تا N. شماره گذاری کنید. هر ملکه باید در یک ردیف منحصر به فرد قرار گیرد ، با یک ملکه در هر ردیف. A1 تعداد ملکه ها را که باید قرار دهد مشخص می کند. A2 موقعیت ملکه را در هر سطر به 0 می رساند. C1 شاخص ردیف فعلی را که بررسی می شود ، از ردیف 1 شروع می کند.
A2 اجرای یک حلقه را شروع می کند ، که وقتی شاخص ردیف I از 0 بیشتر نیست ، خاتمه می یابد. B2 ملکه را در ردیف فعلی به موقعیت بعدی منتقل می کند. B3 تعیین می کند که آیا موقعیت ستون ملکه در ردیف فعلی از N بیشتر است یا خیر. اگر چنین است ، نشان می دهد که تمام موقعیت های موجود در ردیف فعلی محاکمه شده است. در این حالت ، ملکه را در ردیف فعلی برداشته و به ردیف قبلی بازگردید تا به تنظیم موقعیت ملکه ادامه دهید. در خط 4 ، برای مورد تنها یک ردیف ، نیازی به بررسی اعتبار نیست. مستقیماً به قرار دادن ملکه در ردیف دوم ادامه دهید. اگر n 1 است ، سپس مستقیماً به چک های بعدی بروید.
A5 موقعیت ملکه را در ردیف فعلی بدست می آورد. C5 موقعیت های ملکه ها را در تمام ردیف های قبلی بدست می آورد.
B6 تعیین می کند که آیا ملکه فعلی در همان ستون یا مورب مانند هر ملکه قبلی قرار گرفته است. اگر چنین است ، نامعتبر است. در این حالت ، برای تعیین موقعیت بعدی اقدام کنید.
اگر موقعیت ملکه فعلی با هر ملکه قبلی قرار نگرفته است ، سپس شاخص ردیف I را در B7 افزایش دهید ، و تعیین کنید که آیا همه ملکه ها به درستی قرار داده شده اند. در این صورت ، موقعیت های همه ملکه ها را در C7 ثبت کرده و به بررسی اینکه آیا موقعیت معتبر دیگری وجود دارد ، ادامه دهید. در غیر این صورت ، شروع به قرار دادن ملکه بعدی کنید. در SPL ، با استفاده از a.concat@c () می توانید اعضای یک دنباله را به یک رشته جدا شده از کاما اختصاص دهید.
پس از پایان حلقه ، تمام راه حل های ممکن را می توان در C7 مشاهده کرد.
تعداد کل اعضا در دنباله C7 تعداد راه حل ها است. اگر راه حلی وجود نداشته باشد ، هر دو C7 و A8 حاوی مقادیر تهی هستند.
همچنین می توان به صورت بازگشتی با یک زیرروال برای تلاش برای قرار دادن ملکه در ردیف بعدی تماس گرفت:
try.demo
A3 یک ملکه فرعی (A ، R) را تعریف می کند ، جایی که دنباله A موقعیت های هر ملکه را ثبت می کند ، و R نشان دهنده ردیف است که در حال حاضر ملکه در آن قرار دارد. B3 تعیین می کند که آیا همه ملکه ها به درستی قرار داده شده اند یا خیر. در صورت صحت ، راه حل فعلی را در B1 ضبط کرده و برگردانید. B4 از طریق هر ستون در ردیف فعلی حلقه ها را حلقه می کند. C4 تعیین می کند که آیا موقعیت فعلی در همان ستون یا مورب است مانند هر ملکه ای که قبلاً در ردیف های قبلی قرار داده شده است یا خیر. در این صورت ، نشان می دهد موقعیت فعلی نامعتبر است و موقعیت بعدی بررسی می شود. اگر موقعیت ملکه فعلی معتبر است ، این موقعیت را در A ثبت کنید و به قرار دهید ملکه را در ردیف بعدی قرار دهید.
C1 برای شروع قرار دادن ملکه ها با شروع ردیف اول ، یک زیرروال را فراخوانی می کند. پس از اجرای ، نتایج قرارگیری را می توان در B1 بدست آورد و تعداد کل راه حل ها را می توان در D1 بدست آورد.
در SPL ، زیرمجموعه ها را می توان به صورت بازگشتی خواند ، و باعث می شود کد به این روش مختصر تر و خواندن آن آسان تر شود.
Esprocspl منبع باز و رایگان و منبع باز است
