Расстановка ферзей

Алгоритм решения достаточно простой поиск с возвратом.
Алгоритм строится на следующем несложном заключении: поскольку доска 8х8 и нам надо расположить на ней 8 ферзей, то из этого следует, что в каждом столбце доски будет точно один ферзь. Остаётся только выбрать правильную позицию ферзя в столбце. Для этого мы просматриваем все столбцы слева направо, начиная с первого столбца (самого левого). Поскольку наша доска пуста, то расположить на ней ферзя (в первом столбце) очень просто: достаточно поставить его на любое место. Для определённости, мы будем предполагать, что просмотр столбца с целью поиска полей, которые не находятся "под боем", начинается с самой верхней строки и идёт вниз. Таким образом, просматривая первый столбец сверху вниз, мы находим первое поле, которое не бьётся другими ферзями. Для первого столбца это будет поле (1,1) - левый верхний угол доски (в шахматах - это поле А8). Итак, первый ферзь поставлен.

Переходим ко второму столбцу, в котором надо подобрать позицию для второго ферзя. Поступаем точно также: просматриваем поля второго столбца сверху вниз - ищем поле, которое не бьётся уже поставленными ферзями. Как только такое поле найдётся - ставим на него ферзя.

Аналогично с третьим, четвёртым и пятым ферзями:

С шестым и седьмым ферзями проблем тоже не возникает. Создаётся иллюзия, что задача сейчас будет решена...

Но посмотрите на доску - в последний столбец невозможно поставить ферзя! Все поля восьмого столбца находятся под боем! Что же делать? Давайте подумаем из-за чего сложилась такая ситуация? Правильно, из-за неправильной расстановки предыдущих ферзей, ведь именно их расположение блокирует последний столбец целиком. Следовательно, надо изменить расположение уже установленных фигур. Возвращаемся на шаг назад к седьмому ферзю. Попробуем изменить его позицию. Как мы уже знаем - в одном столбце находится один ферзь, поэтому двигать его по горизонтали мы не будем. Остаётся попытаться сдвинуть его по вертикали. Очевидно, что двигать ферзя вверх смысла никакого нет, так как там мы уже проверили все поля и они все под боем. Поэтому выход один - сдвигаем седьмого ферзя вниз.

Однако не всё так просто: все поля ниже текущей позиции находятся под боем! Поля выше - тоже! А текущая позиция нас не устраивает, т.к. в совокупности с положением других ферзей, блокирует решение задачи. Убираем седьмой ферзь с доски и возвращаемся к шестому ферзю. Пытаемся скорректировать его позицию, двигая его вниз. Как видно на рисунке, это ничего не даст: все поля ниже находятся под боем.

Убираем шестого ферзя с доски и возвращается к пятому. Корректируем его позицию. В данном случае в пятом столбце есть поле, ниже текущего, которое не под боем. Перемещаем туда пятого ферзя.

Поскольку пятый ферзь установлен - переходим к следующему столбцу (опять движемся вперёд). Впрочем, при таком положении первых пяти ферзей, шестой ферзь установить нельзя. Нам придётся опять вернуться к пятому, затем к четвертому и так далее. В конце концов, двигаясь по столбцам вперёд (слева направо) и возвращаясь назад (справа налево) при неудаче, мы получим решение, приведённое в секции "Результаты" в конце этой статьи.