[Haskell-beginners] Backtracking

legajid legajid at free.fr
Fri Jan 22 17:33:51 EST 2010

i'm writing a Sudoku solver -a very new idea ;) - , using brute force.
The challenge for me is to keep track of all tries and go back and forward.

My general idea is :
make a list of all cells with value 0
For each of these cells, try values 1 to 9.
If a value matches (that is not used in cells on the same line, column 
or square) then proceed the same way with the next empty cell.
If a value doesn't match, get back to the preceding cell and take the 
next value available : here is my problem, i don't know how to go back.

The calcul function, invoked once, creates the list of empty cells, then 
calls calcul'
Calcul' creates the list of possible values, then calls calcul'' with 
the list.
Calcul'' tries to apply each possible value.If ok, it then calls calcul' 
for the remaining empty cells list. If not, calls itself with the next 
value for the cell.
The calls for different cells are stacked.
In case of backtrack, i must re_call calcul'' with the preceding cell 
number, going on with its list of values, at the point it was stopped.
How to write this ?

Thanks for your help.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: sud2.hs
Type: text/x-haskell
Size: 3953 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/beginners/attachments/20100122/5a62156f/sud2.bin

More information about the Beginners mailing list