Powrót w Erlang

Question

Po pierwsze przepraszam za mój angielski.

Chciałbym użyć algorytmu cofania w Erlang. Byłoby to zgadywanie, aby rozwiązać częściowo wypełniony sudokus. Sudoku 9x9 jest przechowywane jako lista 81 elementów, gdzie każdy element przechowuje możliwą liczbę, która może wejść do tej komórki.

Dla sudoku 4x4 moje początkowe rozwiązanie wygląda następująco: [[1], [3], [2], [4], [4], [2], [3], [1], [ 2,3], [4], [1], [2,3], [2,3], [1], [4], [2,3]]

To sudoku ma 2 rozwiązania. Muszę napisać oba. Po osiągnięciu tego wstępnego rozwiązania muszę zaimplementować algorytm wycofywania, ale nie wiem, jak to zrobić.

Moją myślą jest napisanie stałych elementów do nowej listy o nazwie fixedlist, która zmieni komórki wielokrotnego rozwiązania na [].

Dla powyższego przykładu lista ustalona wygląda następująco: [[1], [3], [2], [4], [4], [2], [3], [1], [ ], [4], [1], [], [], [1], [4], []]

Z tego miejsca mam "próbkę", szukam najniższej długości w liście rozwi nie jest równy 1 i próbuję pierwszej możliwej liczby tej komórki i umieszczam ją na tej stałej liście. Tutaj mam algorytm do aktualizacji komórek i sprawdzenia, czy jest to nadal możliwe do rozwiązania sudoku, czy nie. Jeśli nie, nie wiem jak cofnąć jeden i spróbować nowego. Znam jego pseudo kod i mogę go używać do imperatywnych języków, ale nie do erlangu. (Prolog faktycznie zaimplementował algorytm cofania, ale erlang nie)

Czy masz pomysł?

Answer 1

Re: Moje funkcje bactracking.

Są to ogólne funkcje, które zapewniają ramy do obsługi śledzenia wstecznego i zmiennych logicznych podobnych do silnika prolog. Musisz podać funkcję (predykaty), które opisują logikę programu. Jeśli napiszesz je tak, jak w prologu, pokażę ci, jak przetłumaczyć je na erlang. Bardzo krótko tłumaczyć coś takiego:

p :- q, r, s. 

w prologu do czegoś jak

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

Oto jestem ignorując wszystkie inne argumenty z wyjątkiem kontynuacji.

Mam nadzieję, że to pomoże. Jak już powiedziałem, jeśli opisaliście swoje algorytmy, pomogę wam je przetłumaczyć, szukałem dobrego przykładu. Możesz oczywiście równie dobrze zrobić to sam, ale to zapewnia pewną pomoc.

Answer 2

Wyjazd tych artykułów w blogu Roberta Virding za:

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