Организация и функционирование компьютеров


Использование указателей для обработки деревьев - часть 5


Под ситуацией понимается расстановка ферзей на первых n горизонталях, а подчиненные ситуации - это расстановки ферзей на (n+1) горизонталях. Входные данные в этой задаче отсутствуют, то есть отсутствует переменная x, обозначающая анализируемый случай. Назовем клетку битой, если она бьется хотя бы одним ферзем из уже имеющейся расстановки. Ситуация тупиковая, если n<8

и все поля (n+1)-й горизонтали бьются ферзями из первых n горизонталей. “Шаг вниз” заключается в выборе первой слева небитой клетки (n+1)?й горизонтали. “Шаг вправо” заключается в выборе следующей с правой стороны небитой клетки в n?й горизонтали. С формальной точки зрения:

  • y - расстановка ферзей на первых n горизонталях;
  • agree(y)=-1, если ферзь на n-й горизонтали бьется другим ферзем;
  • agree(y)=+1, если ферзи не бьют друг друга и n<8;
  • agree(y)=0, если ферзи не бьют друг друга и n=8.

Тогда решение задачи полностью укладывается в схему метода ветвей и границ.




- Начало -  - Назад -  - Вперед -