Backtracking in Erlang

Question

Prima di tutto mi dispiace per il mio inglese.

Vorrei utilizzare un algoritmo di backtracking in Erlang. Sarebbe servire da indovinare per risolvere sudoku parzialmente riempiti. Un sudoku 9x9 viene memorizzato come un elenco di 81 elementi, dove ogni elemento memorizza il numero possibile che può andare in quella cella.

Per un 4x4 sudoku la mia soluzione iniziale assomiglia a questo: [[1], [3], [2], [4], [4], [2], [3], [1], [2,3], [4], [1], [2, 3], [2,3], [1], [4], [2,3]]

Questa sudoku ha 2 soluzioni. Devo scrivere entrambi. Dopo di che ha raggiunto soluzione iniziale, ho bisogno di implementare un algoritmo di backtracking, ma non so come farlo.

Il mio pensiero è quello di scrivere gli elementi fissi in un nuovo elenco denominato fixedlist che cambieranno le cellule multiple-soluzione per [].

Per l'esempio di cui sopra la fixedlist assomiglia a questo: [[1], [3], [2], [4], [4], [2], [3], [1], [], [4], [1], [], [], [1], [4], []]

Da qui ho un "campione", guardo per la lunghezza più basso nel solutionlist, che non è uguale a 1, e cerco il primo numero possibile di questa cella e ho messo a che fixedlist. Qui ho un algoritmo per aggiornare le cellule e controlla se è ancora un sudoku risolvibili o meno. In caso contrario, non so come tornare indietro di un e provare una nuova. So che la pseudo codice di esso e posso usarlo per linguaggi imperativi, ma non per Erlang. (Prologo in realtà implementato l'algoritmo backtrack, ma non lo fece Erlang)

Qualche idea?

Answer 1

Re:. Le mie funzioni bactracking

Queste sono le funzioni generali che forniscono un quadro di riferimento per la gestione di back-tracking e variabili logiche simili a un motore Prolog. È necessario fornire la funzione (predicati) che descrivono la logica del programma. Se li si scrive come si farebbe nel prologo posso mostrarvi come tradurle in Erlang. Molto brevemente si traduce qualcosa come:

p :- q, r, s.

nel prologo in qualcosa di simile

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

Qui sto ignorando tutti di altri argomenti, tranne le continuazioni.

Spero che questo dà qualche aiuto. Come ho detto, se si descrivere gli algoritmi posso aiutarvi a tradurre, ho cercato per un buon esempio. È possibile, ovviamente, altrettanto bene farlo da soli, ma questo fornisce qualche aiuto.

Answer 2

Guarda anche questi articoli nel blog di Robert Virding:

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