Backtracking in Erlang

Question

First of all sorry for my English.

I would like to use a backtracking algorithm in Erlang. It would serve as a guessing to solve partially filled sudokus. A 9x9 sudoku is stored as a list of 81 elements, where every element stores the possible number which can go into that cell.

For a 4x4 sudoku my initial solution looks like this: [[1],[3],[2],[4],[4],[2],[3],[1],[2,3],[4],[1],[2,3],[2,3],[1],[4],[2,3]]

This sudoku has 2 solutions. I have to write out both of them. After that initial solution reached, I need to implement a backtracking algorithm, but I don't know how to make it.

My thought is to write out the fixed elements into a new list called fixedlist which will change the multiple-solution cells to [].

For the above mentioned example the fixedlist looks like this: [[1],[3],[2],[4],[4],[2],[3],[1],[],[4],[1],[],[],[1],[4],[]]

From here I have a "sample", I look for the lowest length in the solutionlist which is not equal to 1, and I try the first possible number of this cell and I put it to that fixedlist. Here I have an algorithm to update the cells and checks if it is still a solvable sudoku or not. If not, I don't know how to step back one and try a new one. I know the pseudo code of it and I can use it for imperative languages but not for erlang. (prolog actually implemented backtrack algorithm, but erlang didn't)

Any idea?

Answer 1

Check out these articles in Robert Virding's blog:

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

Answer 2

Re: My bactracking functions.

These are the general functions which provide a framework for handling back-tracking and logical variables similar to a prolog engine. You must provide the function (predicates) which describe the program logic. If you write them as you would in prolog I can show you how to translate them into erlang. Very briefly you translate something like:

p :- q, r, s.

in prolog into something like

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

Here I am ignoring all other arguments except the continuations.

I hope this gives some help. As I said if you describe your algorithms I can help you translate them, I have been looking for a good example. You can, of course, just as well do it by yourself but this provides some help.