Исходник программы, показывающей пример создания шахматной головоломки.
Нам дается доска размером 4x4 с размещенными на ней 6-ю из 12 шахматных фигур. Необходимо разместить остальные 6 фигур на доске таким образом, чтобы соблюдались следующие ограничения:
- Две фигуры мужского пола противоположного цвета не могут занимать один ряд, столбец или диагональ.
- Каждая пешка должна находиться рядом с королем того же цвета.
- В каждом ряду или столбце не более трех человек.
Описание
Пользователь может перетаскивать другие фигуры, чтобы решить пазл. Когда все 12 фигур находятся на доске, они будут проверены на соответствие условиям, указанным выше.
Кнопка «Решить» сбрасывает доску и решает головоломку, используя поиск в глубину с возвратом. Есть флажки для установки параметров, которые применяются при решении:
Случайный порядок ходов рандомизирует порядок, в котором размещаются фигуры. Для некоторых последовательностей потребуется гораздо больше пробных ходов, прежде чем будет найдено решение.
Флажок Animate Moves перемещает визуальные изображения на доске при применении и удалении перемещения.
Пункт «Показать шаги» отображает текстовое описание каждого пробного хода, сделанного и отозванного по мере выполнения поиска.
Поиск в глубину с возвратом - это мощный и довольно простой метод поиска «пространства» потенциальных последовательностей ходов. Мы пробуем фрагменты по порядку, начиная с первого фрагмента в списке. Когда подходящая позиция для фигуры найдена, мы размещаем ее и переходим к установке следующей фигуры. Это продолжается до тех пор, пока все фигуры не будут размещены или, что более вероятно, мы не зайдем в тупик, где для фигуры не существует действительного хода. Когда это происходит, мы удаляем последний ход предыдущей фигуры и ищем другое допустимое место для хода. Если правильный ход найден, мы продвигаемся снова, если не найден, мы делаем резервную копию другой фигуры, пытаясь поместить ее в другое положение и т.д. пока все шесть фигур не будут размещены (успех), или больше не будет возможных вариантов для попытки (неудача).
Базы данных
