Backtracking in Erlang

Question

Prima di tutto mi dispiace per il mio inglese.

Mi piacerebbe utilizzare un algoritmo di backtracking in Erlang. Servirebbe come ipotesi per risolvere sudoku parzialmente riempiti. Un sudoku 9x9 è memorizzato come una lista di 81 elementi, in cui ogni elemento memorizza il numero possibile che può entrare in quella cella.

Per un sudoku 4x4 la mia soluzione iniziale è la seguente: [[1], [3], [2], [4], [4], [2], [3], [1], [ 2,3], [4], [1], [2,3], [2,3], [1], [4], [2,3]]

Questo sudoku ha 2 soluzioni. Devo scrivere entrambi. Dopo che la soluzione iniziale è stata raggiunta, ho bisogno di implementare un algoritmo di backtracking, ma non so come farlo.

Il mio pensiero è di scrivere gli elementi fissi in una nuova lista chiamata lista fissa che cambierà le celle a più soluzioni in [].

Per l'esempio sopra menzionato la lista fissa si presenta così: [[1], [3], [2], [4], [4], [2], [3], [1], [ ], [4], [1], [], [], [1], [4], []]

Da qui ho un "campione", cerco la lunghezza più bassa nella solutionlist che non è uguale a 1, e provo il primo numero possibile di questa cella e lo metto in quella lista fissa. Qui ho un algoritmo per aggiornare le celle e controlla se è ancora un sudoku risolvibile o meno. Altrimenti, non so come fare un passo indietro e provarne uno nuovo. Conosco lo pseudo codice e posso usarlo per le lingue imperative ma non per l'erlang. (prolog ha effettivamente implementato l'algoritmo di backtrack, ma non l'ha fatto)

Qualche idea?

Answer 1

Re: Le mie funzioni bactracking.

Queste sono le funzioni generali che forniscono un framework per la gestione di back-tracking e variabili logiche simili a un motore di prolog. È necessario fornire la funzione (predicati) che descrive la logica del programma. Se li scrivi come faresti in prolog, posso mostrarti come tradurli 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 altri argomenti, ad eccezione delle continuazioni.

Spero che questo aiuti. Come ho detto, se descrivi i tuoi algoritmi, posso aiutarti a tradurli, ho cercato un buon esempio. Ovviamente puoi anche farlo da solo, ma questo ti aiuta.

Answer 2

Guarda anche questi articoli nel blog di 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