. : Пасьянс Колья : .

Исходник программы, показывающей пример создания пасьянса, в котором нужно удалить колышки, перепрыгивая их другим колышком в любом из 4 направлений, пока один колышек не останется в центральном отверстии.

Для решения данной головоломки используется поиск в глубину.

Данная версия выполняет поиск от 250 000 проверяемых позиций в секунду (на моем ноутбуке с частотой 266 МГц) до 750 000 позиций в секунду на новом Celeron с частотой 800 МГц. Самый долгий поиск решения требует около 13 000 000 проверок позиций.

Заметки для программиста

Объект TBoard содержит квадратный массив B позиций на доске поля типа TOccupied со значениями Empty, Occupied или NotAvailable. Потенциальное перемещение считается допустимым, если 1) проверяемый слот занят 2) соседнее отверстие в проверяемом направлении занято и 3) следующая позиция в том же направлении пуста. Из-за этого двойная строка неиспользуемых (NotAvailable) записей массива определяется по всей доске (так что плата определяется как 11 X 11 с только средними 7 позициями в каждом из когда-либо использовавшихся направлений. Когда мы находим колышек, мы всегда можем проверить две позиции слева, справа, сверху и снизу, беспокоясь об исключении «индекс вне допустимого диапазона».

Moves - основная функция, выполняющая поиск. Она рекурсивно вызывает себя после каждого хода, чтобы найти следующий возможный ход. TBoard также содержит Path, который содержит ходы, которые привели нас к текущей позиции на доске. Когда допустимый ход найден, мы добавляем его в Path, корректируем массив колышков, чтобы отразить ход, уменьшаем счетчик колышков и вызываем Moves для проверки следующей позиции. При входе в Moves мы проверяем наличие единственного колышка в центре доски и возвращаем true, если он найден. Если мы проверим все позиции, не найдя допустимого хода, мы вернем false. Если мы возвращаемся после вызова Moves с ложным результатом, мы отменяем только что сделанное перемещение привязки и продолжаем поиск.

Запись перемещения TMove - это динамически размещаемая запись с переменными Frompoint и ToPoint. TMove изначально был объектом, однако ходы могут создаваться и удаляться миллионы раз за один прогон - замена формы объекта записью сокращает время выполнения примерно на 20%.