Backtracking in Erlang
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?
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.
精彩评论