Правила та умови
На форумі заборонено:
Порушники правил будуть суворо покарані модераторами або адміністратором форуму і їм буде повністю закритий доступ на форум.
Використовуючи цей форум Ви можете:
У цій статті поговоримо про відому логічної головоломці під назвою "вісім ферзів". Суть завдання полягає в тому, що потрібно зуміти розставити на шахівниці (8 х 8) вісім ферзів так, щоб вони не знаходилися під боєм один одного (нагадаю, що ферзь (королева) б'є по прямій і по діагоналі). Скажу, що варіантів розстановки є кілька, але знайти їх вручну не завжди легко, особливо важко поставити останнього ферзя. Один з варіантів розстановок ферзів дивимося нижче на малюнку 1
Для того, щоб вирішити задачу про восьми ферзів, ми напишемо програму на мові програмування С ++, яка і буде розставляти ферзів. Пропоную слідувати такій тактиці:
1. Шахову дошку представити у вигляді двовимірного масиву, розміром 8 х 8.
2. Для кожного осередку масиву задати число, яке буде говорити, скільки з цієї клітки ферзь може побити інших клітин. Дивимося малюнок 2
Як бачите, якщо поставити ферзя на позицію x = 2, y = 1, то під боєм буде перебувати 23 клітини. Таку процедуру потрібно буде виконати для кожної клітини шахової дошки (двовимірного масиву). В результаті отримаємо ось таку картину, показану нижче на малюнку 3
3. Після того, як пріоритети розставлені, потрібно вибрати клітку з мінімальним пріоритетом (ту, з якої менше б'ється інших клітин дошки) і поставити на неї ферзя. Думаю, що тут зрозуміло. тому якщо ставити ферзів на ті клітини, з яких можна побити більшу кількість інших клітин, то до розстановки восьми ферзів ми точно не дійдемо. Продовжуємо міркувати. якщо клітин з мінімальним пріоритетом знайшлося кілька (а в самому початку розстановки буде саме так), то вибирати підходящу будемо випадковим чином. Як це логічно обгрунтовано організувати? Для цього ми повинні спочатку знайти мінімальний пріоритет (припустимо, 21 - саме воно буде найменшим в першій ітерації - див. Малюнок 3), потім порахувати число клітин з цим пріоритетом (в нашому випадку з 21 цих однакових клітин буде аж 28), далі згенерувати випадкове число в інтервалі від 1 до числа однакових клітин (їх 28) і, виходячи з отриманого при генерації числа, поставити ферзя на потрібне місце. Ту клітку, куди ми ставимо ферзя, будемо якось позначати, припустимо, привласнюючи їй значення 100. Можна брати абсолютно будь-яке значення, тільки ось підбирайте так, щоб воно не визначалося як мінімальне при визначенні пріоритетів.
4. Після постановки ферзя, потрібно видалити побиті їм клітини, позначивши їх будь-яким числом. Припустимо, я буду позначати ці клітини для зручності числом 99.
Невелике пояснення. Коли основний алгоритм розстановки ферзів відпрацює і у нас залишаться на шахівниці (двовимірному масиві, емулює шахову дошку) лише осередки з числами 100 (це ферзі) і 99 - побиті клітини, то ми виведемо отриманий результат на екран з умовою, що якщо нам зустрічається число 100 - то малювати ферзя (або в консолі - сніжинку, грати і т.д.), в іншому випадку робити клітку просто порожній (або в консолі для наочності можна їх позначати рискою, точками і т.д.).
5. Далі знову все повторюється з пункту 2 по 4, поки не розставимо всіх ферзів, яких повинно бути вісім. Тут є ще один момент: з першої спроби, навіть використовуючи так званий "розумний" підхід до реалізації завдання, наведений вище алгоритм може не розставити всіх вісім ферзів. Але тут є вихід з цього становища. Після розстановки ми будемо перевіряти: чи вийшло поставити всіх ферзів. Якщо немає, то повторюємо розстановку заново.
На наступному четвертому малюнку я привожу в дію описаний вище алгоритм для наочності. Він може видавати різні варіанти розстановок, але для цього ви повинні перезавантажити вашу веб-сторінку (кнопка "оновити" в браузері, або F5) і тоді результат зміниться. До жалю, web-технологію Ajax я поки що ще не знаю, тому для отримання нової картинки потрібно перезавантажувати сторінку.
Ось вид програми (поки що привожу лише її основну частину - функцію main ()), що реалізує алгоритм
Як бачите, в ньому реалізовано те, що я говорив вище
1) Оголошуємо двовимірний масив board. розмірністю 8 х 8 осередків - це буде наша шахівниця. Також нам будуть потрібні змінні для зберігання координат точок (x і y) і покажчики на них (ptrX і ptrY). Для ініціалізації масиву нулями у нас буде служити функція resetBoard ().
2) Матриця оголошена, инициализирована. Тепер дивимося всередину циклу for. який і буде у нас виконувати розстановку восьми ферзів. Як ми говорили вище в пункті 2, нам потрібно задати для кожного осередку матриці свій пріоритет. Це буде робити функція updateBoard ().
4) Після постановки ферзя, помічаємо вбиті їм клітини. Виконує це функція deleteCell ().
Цей процес повторюється рівно вісім разів, як задано в умовах циклу for. Якщо, як я писав вище, не вийде з першої спроби розставити всі вісім ферзів, то процес розстановки обнуляється за допомогою resetBoard () і цикл розстановки починається заново. Для того, щоб повідомити нам, розставлені чи всі вісім ферзів чи ні, служить функція checkQueens (). повертає брехня. якщо не вийшло розставити, і істину. якщо розстановка вдалася.
Ось, в принципі і все, що я хотів розповісти по даному алгоритму. Повну реалізацію програми наводжу нижче.
Результат роботи програми
P.S. Також на сайті ви можете знайти іншу реалізацію алгоритму "Вісім ферзів", реалізовану програмістом Олексієм і викладену на форумі. за що йому велике спасибі.