[Haskell-beginners] Backtracking

[Daniel Fischer]

Am Freitag 22 Januar 2010 23:33:51 schrieb legajid:
> Hi,
> 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 ?

You get automatic backtracking if you calculate the list of all solutions 
(just in case the starting grid is too underdetermined, be sure to only 
call "take k $ solutions startGrid" for suitably small values of k).

solutions :: Grid -> [Grid]
solutions g = 
  case libres g of
    [] -> return g       -- fini
    (libre:_) -> do
      possibilité <- valeurs libre g
      solutions (place possibilité libre g)

Check if there are any free cells left. If not, we've found a solution.
If there are, try all possibilities for the first free cell and solve from 
then on. Invalid (or wrong) choices lead to an empty list of possibilities 
some time later, in which case that branch is aborted.

For performance, you can see that a simple optimisation is sorting the list 
of free cells by the number of possibilities they allow, so a branch isn't 
kept alive after it is clear that there are no possibilities to fill the 
last cell.

>
> Thanks for your help.
>
> Didier