我创建了一个数独解算器,将解决数独作为一个人说明可能─通过对应于被检查的方形广场检查的可能性+定值。
(来源: pastebin/KVrXUDBF )
不过,我想创建一个随机数独发生器(从空网格),所以决定使用一个回溯算法。我理解回溯的概念,但感到困惑的一件事:
我怎么知道哪个previous节点返回(和更改),一旦我知道了一定的解决方案是不允许的? 我应该简单地返回到通过所有可能的previous节点和周期? (然后,如果这会产生不正确的答案,返回值之前,等等)。这似乎是一个可行的方法,但也相当低效。这是实现回溯方法的正确方法还是有更好的方法去做?
在此先感谢。
更可以发现有关回溯这里: en.wikipedia/wiki/Backtracking
解决方案独益智可以减小到图表,直到不存在违反该着色问题,这可以通过简单的回溯来解决像指定颜色到节点(1-9)所有直接连接的节点没有相同的颜色。
从数独构造图: -
有两格点之间的直接边缘,如果他们是在同一 行或列或方形。
回溯: -
一旦你用它做,你可以开始随意去除网格数字,直到你觉得问题无法解决的是如果有更多的数字将被删除。
I've created a Sudoku solver that will solve a Sudoku as a human might- by checking possibilities + definite values in squares corresponding to the square being checked.
(Source: pastebin/KVrXUDBF)
However, I would like to create a random Sudoku generator (from a blank grid), and so have decided to use a backtracking algorithm. I understand the concept of backtracking, but am confused about one thing:
How do I know which previous node to return to (and change) once I know a certain solution is not allowed? Should I simply return to the previous node and cycle through all possibilities? (And then if this yields no correct answers, return to the value before, etc.). This seems like a viable method, but also quite inefficient. Is this the correct way of implementing a backtracking method or is there a better way to go about it?
Thanks in advance.
More can be found about backtracking here: en.wikipedia/wiki/Backtracking
解决方案Sudoku Puzzle can be reduced to graph coloring problem which can be solved using simple backtracking like assigning colors to node (1-9) till the there is no violation that all directly connected nodes have no same color.
Constructing Graph from Sudoku : -
There is an direct edge between two grid points if they are in same row or column or square.
Backtracking :-
Once You are done with it you can start removing numbers from the grid at random till you think the problem is unsolvable if any more numbers are removed.
更多推荐
数独回溯算法(JAVA)
发布评论