Возврат в Эрланге

Question

Прежде всего извините за мой английский.

Я хотел бы использовать алгоритм возврата в Erlang.Это будет служить угадыванием для решения частично заполненного судоку.Судоку 9x9 хранится в виде списка из 81 элемента, где каждый элемент хранит возможное число, которое может войти в эту ячейку.

Для судоку 4х4 мое первоначальное решение выглядит так:[[1],[3],[2],[4],[4],[2],[3],[1],[2,3],[4],[1],[2, 3],[2,3],[1],[4],[2,3]]

У этого судоку есть два решения.Мне нужно выписать оба.После того, как это первоначальное решение достигнуто, мне нужно реализовать алгоритм возврата, но я не знаю, как это сделать.

Моя мысль состоит в том, чтобы записать фиксированные элементы в новый список, называемый фиксированным списком, который изменит ячейки с несколькими решениями на [].

Для вышеупомянутого примера фиксированный список выглядит следующим образом:[[1],[3],[2],[4],[4],[2],[3],[1],[],[4],[1],[],[], [1],[4],[]]

Отсюда у меня есть «образец», я ищу наименьшую длину в списке решений, которая не равна 1, пробую первое возможное число этой ячейки и помещаю его в этот фиксированный список.Здесь у меня есть алгоритм обновления ячеек и проверки, является ли это решаемой судоку или нет.Если нет, то я не знаю, как отступить от одного и попробовать новый.Я знаю его псевдокод и могу использовать его для императивных языков, но не для эрланга.(пролог фактически реализовал алгоритм возврата, но эрланг этого не сделал)

Есть идеи?

Answer 1

Ре:Мои функции возврата.

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

p :- q, r, s.

в прологе во что-то вроде

p(Next0) ->
    Next1 = fun () -> s(Next0) end,
    Next2 = fun () -> r(Next1) end,
    q(Next2).

Вот я игнорирую все другие аргументы, кроме продолжений.

Я надеюсь, что это поможет.Как я уже сказал, если вы опишете свои алгоритмы, я могу помочь вам их перевести, я искал хороший пример.Вы, конечно, можете сделать это и сами, но это поможет.

Answer 2

Прочтите эти статьи в блоге Роберта Вирдинга:

http://rvirding.blogspot.com/2009/03/backtracking-in-erlang-part-1-control.html http://rvirding.blogspot.com/2009/04/backtracking-in-erlang-part-2-passing.html