Классической проблемой, решения задачи методом «отслеживание в обратном порядке», является проблема Восьми Королев. Эта трудная проблема соглашения с размещением восьми королев на шахматной доске так, чтобы все королевы не могли атаковать друг друга.
В игру шахмат играют на доске, содержащей 64 квадрата переменного цвета. Два игрока поочередно передвигают ряд фигур по этим квадратам. Цель игры состоит в том, чтобы заполучить самую важную фигуру противника, "короля". В то время как король является самой важной фигурой, "королева" является самой мощной. В игре королевы могут "атаковать" или "получить" другие фигуры двумя различными способами. Во-первых, королева может атаковать фигуры на тех квадратах, которые находятся в той же самой строке или том же самом столбце что и королева. Во-вторых, королева может атаковать фигуры, занимающие квадраты, которые пересекает по диагонали квадратов, который занимает королева. Рисунок 2 показывает два различных способа, которыми атакуют королевы. Отметим, что квадраты, выделенные красным, являются теми, которые королева может атаковать.
Рисунок 2 атака Куинса двумя различными способами
Комбинируя эти два метода вместе, мы видим (снова в красном) все квадраты на шахматной доске, которую королева может атаковать в рисунке 3. Мы полагаем, что королева в рисунке 3 "атакует" любую часть, которая занимает красный квадрат.
Рисунок 3 Все квадраты королева может атаковать
Королеву считают самой мощной шахматной фигурой, так как она атакует наибольшее число квадратов из любой другой части доски. Действительно ли королевы настолько мощны, что восемь из них не могут быть размещены на доске без пересечения линий атакующий друг друга? Проведите некоторое время и см., можно ли создать решение. Если у Вас не будет доступа к шахматной доске, то печатая копию этой страницы даст Вам, от следующей фигуры, пустой платы и восьми королев.
Рисунок 4 пустая плата и восемь королев
Помните, рассматривая решение этой проблемы, следует удостовериться, что не разместили двух королев в ту же самую строку или в тот же самый столбец. Более того, также невозможно разместить двух королев в ту же самую диагональ. Пример non-solution является рисунк 5. Это действительно non-solution, так как королева в левом верхнем углу атакует королеву в правом нижнем углу, и наоборот.
Рисунок 5 non-solution