Головна

проблема

  1. III. Проблема сенсу життя і призначення людини.
  2. А. Реформація і конфесійна проблема
  3. АВТОР ЯК ПРОБЛЕМА
  4. адміністративна проблема
  5. Аналіз роботи Г. Алмонда і С. Верби «Громадянська культура і стабільність демократії»: основна проблема, головні тези, висновки.
  6. Аналіз роботи Дж. С. Ная-мл. і Р. Кохен «Транснаціональні відносини та світова політика»: основна проблема, головні тези, висновки.
  7. Аналіз роботи Н. І. Бірюкова та В. М. Сергєєва «Соборність як парадигма політичної свідомості»: основна проблема, головні тези, висновки.

Класичною проблемою, вирішення завдання методом «відстеження в зворотному порядку», є проблема Восьми Корольов. Ця важка проблема угоди з розміщенням восьми королев на шаховій дошці так, щоб всі королеви не могли атакувати один одного.

У гру шахів грають на дошці, що містить 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 | Розділяй і володарюй |

© 2016-2022  um.co.ua - учбові матеріали та реферати