数独回溯算法（JAVA）

本文介绍了数独回溯算法（JAVA）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我创建了一个数独解算器，将解决数独作为一个人说明可能─通过对应于被检查的方形广场检查的可能性+定值。

（来源： pastebin/KVrXUDBF ）

不过，我想创建一个随机数独发生器（从空网格），所以决定使用一个回溯算法。我理解回溯的概念，但感到困惑的一件事：

我怎么知道哪个previous节点返回（和更改），一旦我知道了一定的解决方案是不允许的？ 我应该简单地返回到通过所有可能的previous节点和周期？ （然后，如果这会产生不正确的答案，返回值之前，等等）。这似乎是一个可行的方法，但也相当低效。这是实现回溯方法的正确方法还是有更好的方法去做？

在此先感谢。

更可以发现有关回溯这里： en.wikipedia/wiki/Backtracking

解决方案

独益智可以减小到图表，直到不存在违反该着色问题，这可以通过简单的回溯来解决像指定颜色到节点（1-9）所有直接连接的节点没有相同的颜色。

从数独构造图： -

  

有两格点之间的直接边缘，如果他们是在同一   行或列或方形。

回溯： -

     

在指定一种颜色（1-9）到节点

  

检查是否存在具有相同的颜色没有其他直接连接的节点

  

如果有效的色彩转移到下一个节点。

  

其他改变颜色并重新检查。

  

如果所有的颜色用尽原路返回至previous节点。

  

请递归，直到所有节点的颜色。

  

一旦你用它做，你可以开始随意去除网格数字，直到你觉得问题无法解决的是如果有更多的数字将被删除。

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 :-

Assign one color (1-9) to node

Check if there is no other directly connected node with same color

If valid color move to next node.

else change the color and recheck.

If all color exhausted backtrack to previous node.

Do recursion till all nodes are color.

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.