Головна |
Класичною проблемою, вирішення завдання методом «відстеження в зворотному порядку», є проблема Восьми Корольов. Ця важка проблема угоди з розміщенням восьми королев на шаховій дошці так, щоб всі королеви не могли атакувати один одного.
У гру шахів грають на дошці, що містить 64 квадрата змінного кольору. Два гравці по черзі пересувають ряд фігур з цих квадратах. Мета гри полягає в тому, щоб роздобути найважливішу фігуру противника, "короля". У той час як король є найважливішою фігурою, "королева" є найпотужнішою. У грі королеви можуть "атакувати" або "отримати" інші фігури двома різними способами. По-перше, королева може атакувати фігури на тих квадратах, які знаходяться в тій же самій рядку або тому ж самому стовпці що і королева. По-друге, королева може атакувати фігури, що займають квадрати, які перетинає по діагоналі квадратів, який займає королева. Малюнок 2 показує два різні способи, якими атакують королеви. Відзначимо, що квадрати, виділені червоним, є тими, які королева може атакувати.
Малюнок 2 атака Куїнса двома різними способами
Комбінуючи ці два методи разом, ми бачимо (знову в червоному) всі квадрати на шаховій дошці, яку королева може атакувати в малюнку 3. Ми вважаємо, що королева в малюнку 3 "атакує" будь-яку частину, яка займає червоний квадрат.
Малюнок 3 Всі квадрати королева може атакувати
Королеву вважають найпотужнішою шаховою фігурою, так як вона атакує найбільше число квадратів з будь-якої іншої частини дошки. Чи справді королеви настільки потужні, що вісім з них не можуть бути розміщені на дошці без перетину ліній атакуючий один одного? Проведіть деякий час і см., Чи можна створити рішення. Якщо у Вас не буде доступу до шахівниці, то друкуючи копію цієї сторінки дасть Вам, від наступної фігури, порожній плати і восьми королев.
Малюнок 4 порожня плата і вісім королев
Пам'ятайте, розглядаючи рішення цієї проблеми, слід упевнитися, що не розмістили двох королев в ту ж саму рядок або в той же самий стовпець. Більш того, також неможливо розмістити двох королев в ту ж саму діагональ. Приклад non-solution є малюнк 5. Це дійсно non-solution, так як королева в лівому верхньому кутку атакує королеву в правому нижньому кутку, і навпаки.
Малюнок 5 non-solution
Відстеження в зворотному порядку. поняття | Рішення
The Call Stack | Divide and Conquer | Backtracking. The Concept | The Problem | The Solution | The Call Stack | Розділяй і володарюй |