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?
1条答案
按热度按时间oug3syen1#
回复：我的回溯功能。
这些是通用函数，它们提供了一个框架来处理回溯和逻辑变量，类似于prolog引擎。你必须提供描述程序逻辑的函数（ predicate ）。如果你像在prolog中那样写它们，我可以告诉你如何把它们翻译成erlang。简单地说，你可以翻译如下：
在前奏中
在这里，我忽略了除了延续之外的所有其他论点。
我希望这能给你一些帮助。正如我所说，如果你描述你的算法，我可以帮你翻译它们，我一直在寻找一个很好的例子。当然，你也可以自己做，但这提供了一些帮助。