Erlang에서 역 추적

Question

우선 내 영어에 대해 죄송합니다.

Erlang에서 역 추적 알고리즘을 사용하고 싶습니다. 그것은 부분적으로 채워진 스도커스를 해결하는 것이 추측 역할을 할 것입니다. 9x9 스도쿠는 81 가지 요소 목록으로 저장되며, 여기서 모든 요소는 해당 셀에 들어갈 수있는 가능한 숫자를 저장합니다.

4x4 Sudoku의 경우 내 초기 솔루션은 [[1], [3], [2], [4], [4], [2], [3], [1], [2,3], 다음과 같습니다. [4], [1], [2,3], [2,3], [1], [4], [2,3]

이 스도쿠에는 2 가지 솔루션이 있습니다. 나는 둘 다 써야한다. 그 초기 솔루션에 도달 한 후에는 역 추적 알고리즘을 구현해야하지만 어떻게 만드는 방법을 모르겠습니다.

내 생각은 고정 요소를 고정식 목록이라는 새로운 목록에 쓰는 것입니다.

위에서 언급 한 예제에서 고정 목록은 [[1], [3], [2], [4], [4], [2], [3], [1], [], [4] , [1], [], [], [1], [4], []

여기에서 나는 "샘플"이 있고, SolutionList에서 가장 낮은 길이를 1과 같지 않으며,이 셀의 첫 번째 가능한 수를 시도하고 그 고정 목록에 넣습니다. 여기에는 셀을 업데이트 할 수있는 알고리즘이 있으며 여전히 해결 가능한 스도쿠인지 여부를 확인합니다. 그렇지 않다면, 나는 하나를 뒤로 물러서 새로운 것을 시도하는 방법을 모른다. 나는 그것의 의사 코드를 알고 있으며, 필수 언어에는 사용할 수 있지만 Erlang에는 사용할 수 없습니다. (Prolog는 실제로 백 트랙 알고리즘을 구현했지만 Erlang은 그렇지 않았습니다)

아이디어가 있습니까?

Answer 1

Re : 내 bactracking 기능.

이들은 프롤로그 엔진과 유사한 역 추적 및 논리적 변수를 처리하기위한 프레임 워크를 제공하는 일반적인 기능입니다. 프로그램 논리를 설명하는 함수 (Predicates)를 제공해야합니다. Prolog에서와 같이 글을 쓰면 Erlang으로 번역하는 방법을 보여줄 수 있습니다. 매우 간단히 다음과 같은 것을 번역합니다.

p :- q, r, s.

프롤로그에서 같은 것으로

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

여기서 나는 무시하고있다 모두 연속성을 제외한 다른 주장.

이것이 도움이되기를 바랍니다. 내가 당신의 알고리즘을 설명하면 나는 당신이 그것들을 번역하는 데 도움을 줄 수 있다면, 나는 좋은 예를 찾고 있습니다. 물론 스스로 할 수는 있지만 이것은 약간의 도움을 제공합니다.

Answer 2

Robert Virding의 블로그 에서이 기사를 확인하십시오.

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