Обход доски конём

[questioner]

Есть задача: нужно обойти доску конём (каждую клетку ровно один раз) и вернуться в исходную клетку. Реализовывать предполагается на чистом функциональном языке? Как бы это лучше организовать.. Тут всё, по-моему, сводится к полному перебору. Какой вариант посоветуете? Я думал о рекурсивном переборе с возвратом... Тем не менее, реализация у меня страдает -- так как с computer science туго. Может быть кто-то может написать решение псевдокодом?

[cepesh]

Если найдете в инете книгу Вирт Н. — Алгоритмы+структуры данных=программы, то посмотрите там пункт 3.4. В нем все подробно написано.

[photon]

Не знаю, что советует Вирт, я бы реализовал для перебора рекурсивную функцию, на вход которой подается текущее положение и перечень клеток, на которых уже побывал конь. А в теле функции искал бы возможные ходы, по каждому возможному ходу снова запуская эту функцию. Если ходов нет и еще не все клетки обошли - эта ветка закрывается. Если ходов нет и все клетки обошли - ура - найдено решение, записываем результат.

[незваный гость]

Если язык очень чисто функциональный, то списка посещений нет. Вместо него используется функция, возвращающая побывали ли мы на этом поле. А во время рекурсии эта функция "поправляется" (на весьма условно языке-гибриде):

travest = lambda(current, length, checkvisited, printtrace) (
  newcheck = lambda(pos) (
       (pos == current) OR checkvisited(pos)
  )
  newprint = lambda() (
     print(current)
     printtrace()
  )
  if (validpos(current) AND NOT checkvisited(current),
     if(length >= 64, complete_execution(newprint))
     travest(move1(current), length + 1, newcheck, newprint)
     travest(move2(current), length + 1, newcheck, newprint)
     travest(move3(current), length + 1, newcheck, newprint)
     ...
  )
)

validpos() проверяет, что мы не вышли за пределы доски, move1() и ей подобные делает ход, не глядя, попадаем ли мы на доску или нет. Идея все та же -- перебор с возвратом. Но функциональная тонкость -- то, что newcheck() на каждом этапе рекурсии своя (хотя и называется также). Она определяется каждый раз в новом контексте, с новыми current и checkvisited(). Тоже относится и к printtrace().