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

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]]

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

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

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

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

Есть идеи?

Answer 1

Re: Мои функции бактрекинга.

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

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