Останні новини
Завдання про розстановку ферзів. Перебір з поверненням.
Завдання про розстановку ферзів.
Невелика підказка до вирішення завдання про розстановку 8 ферзів.
Суть завдання. Необхідно було знайти такі розстановки восьми ферзів на звичайній шаховій дошці, щоб вони не били один одного.
Варто відразу зауважити, що перебирати всі можливі варіанти розстановок ми не в змозі. Точніше можна звичайно написати таку програму, але ми вчинимо інакше, більш оптимально.
Деякі зауваження про спосіб зберігання розстановки.
Давайте прикинемо, як ми будемо зберігати розташування ферзів на дошці. Очевидним рішенням було б завести масив 8Х8 і записувати в нього одиницю або нуль, в залежності від того чи зайнята клітина ферзем чи ні.
Але давайте подумаємо, чи так нам потрібна вся дошка? Виявляється, що ні. Згадуємо, як ходить ферзь. На будь-яку кількість клітин по вертикалі, горизонталі або діагоналі. Очевидно, що якщо на якийсь вертикалі є ферзь, то поставити на цю вертикаль ще одне ферзя ніяк не вийде, тому що вони будуть бити один одного.
Має сенс зберігати лише одновимірний масив з восьми елементів, кожен з яких буде відповідати одній з вертикалей. А значення кожного елемента буде відповідати тій рядку, в якій встановлено ферзь. Наступний малюнок відмінно пояснює цей принцип.
Про перевірку, чи знаходиться поле «під боєм» чи ні.
Опишемо математично, які клітини шахової дошки знаходяться «під боєм» ферзя, встановленого в клітці [i] [j].
Подивіться на наступний малюнок.
Ці умови легко переробити під наш спосіб зберігання розстановки ферзів.
Припустимо, що вже є кілька встановлених ферзів, які не б'ють один одного. Які умови накладаються на наступного ферзя?
Зрозуміло, що потрібно послідовно обробити кожну з попередніх елементів. Нехай ми хочемо поставити ферзя на позицію k.
Починаємо перевірку, з першого елемента, в ньому у нас записано значення вісім. Отже, k не повинно дорівнювати восьми, інакше обидва ферзя виявляться на одній горизонталі. Крім того, k + 4! = 8 + 1 (умова зеленої лінії), інакше ми намагаємося поставити ферзя на зайняту діагональ. І нарешті, k-4! = 8-1 (умова синьої лінії), інакше ми знову потрапляємо на діагональ, яка б'ється іншим ферзем. Перевірку умови червоної лінії здійснювати не потрібно, так як спосіб представлення розстановок в пам'яті не дозволить на одну горизонталь поставити двох ферзів.
Аналогічні перевірки необхідно будемо зробити для всіх ферзів, які до цього моменту вже встановлені на дошці. Логічно буде виділити ці перевірки в функцію, яка приймає два аргументи - рядок і стовпчик клітини, в яку ми хочемо встановити ферзя.
Основний алгоритм рішення. Перебір з поверненням.
Тепер обговоримо основний алгоритм реалізує розстановку ферзів. Діяти будемо так, як ми діяли б, якщо у нас була б реальна дошка перед очима.
Поставимо першого ферзя в першу клітку першої вертикалі. Відповідно в перший елемент нашого масиву збережемо одиничку. Добре, перший ферзь встановлений. Саме час спробувати встановити другого ферзя.
Він повинен стояти на другий горизонталі.
Перевіримо другу клітку, другий вертикалі. Результат перевірки незадовільний, це поле теж б'ється раніше встановленим ферзем.
Тепер перевіримо третю клітку другий вертикалі, може бути вона нам підійде? Дійсно підходить. Встановлюємо туди ферзя. Переходимо до установки третього ферзя на третю вертикаль.
Перевірку починаємо здійснювати з 1 клітини третин вертикалі.
Думаю вже очевидно, що ні перша, ні друга, ні третя, ні навіть четверта клітини нам не підійдуть, так як вони б'ються раніше встановленими ферзями. А ось п'ята клітинка, виявиться в самий раз, так як її ні перший, ні другий ферзі не б'ють. Значить, встановлюємо туди нашого третього ферзя.
Аналогічним способом заповнюємо четверту, п'яту, шосту і сьому вертикалі. Поки що це все можна реалізувати стандартним перебором в два цикли. Зовнішній цикл рухається по вертикалях від 1 до 8, а внутрішній по горизонталях.
Окремо розглянемо установку ферзя на останній вертикалі.
Якщо ви все робили згідно з алгоритмом, то на цьому етапі у вас вийде ситуація, зображена на малюнку справа. Виходить, що поточного ферзя нікуди встановити, так як всі клітини даної вертикалі б'ються раніше встановленими сім'ю ферзями.
Що ж робити? Потрібно повернутися на крок назад і спробувати встановити сьомого ферзя в інше місце.
Це операція називається повернення.
Будемо перевіряти лише клітини з 5 по 8. Неважко переконатися, що жодна з них не підходить. А значить, виконуємо ще один повернення і намагаємося встановити п'ятого ферзя на нове місце.
Перевірку, як ви вже напевно здогадалися будемо починати з третьої клітини п'ятої вертикалі. Вона нам не підійде, так як знаходиться під боєм, причому від двох ферзів відразу, від другого і третього. А ось четверта клітинка вільна, і тому в неї і будемо ставити нашого ферзя.
Продовжуючи в такому дусі (чергуючи установки з поверненнями), рано чи пізно ми натрапимо на таку розстановку ферзів, яка задовольняє всім нашим вимогам. Іншими словами на дошці буде розміщено 8 ферзів, які не будуть бити один одного. Натрапивши на таку розстановку, ми збережемо її в окремий масив, або ж відразу можемо вивести на екран. Після чого, нам необхідно буде продовжити виконання перебору.
Така ось величезна підказка. Використовуючи отримані знання, спробуйте тепер написати відповідну програму.