首页 > 代码库 > LeetCode----Sudoku Solver+精确覆盖问题解法（Dancing Links）
LeetCode----Sudoku Solver+精确覆盖问题解法（Dancing Links）
BackGround：
做完LeetCode上的数独题目好长时间了，今天将做题时参考的Algorithm X 以及 Dancing Links 整理出来。话说理解算法+写出程序一共用了三天，智商果然余额不足。。。
介绍：
由于Dancing Links 是为了解决数独问题学习的，那就从数独问题下手，围绕数独问题展开对Algorithm X 和 Dancing Links的介绍，最后将数独问题的解法以及Java源码放出来。
精确覆盖问题：
没错，解数独的问题就是一个解 精确覆盖 问题的过程，即数独问题是精确覆盖问题的一个特例。
精确覆盖问题可以用下面的例子来说明：
假设有集合S = { a , b , c , d , e , f } ， 还有一些S的子集 S1 = { a , c , f} , S2 = {b , d } , S3 = { e } , S4 = { b , d , f , e} ，从这些子集中选出n个集合，使得这些集合的并集为S ， 并且子集中的元素有且只能出现一次。很容易看出我们可以选择S1 、 S2 、 S3 。 但是不能选择 S1、 S4 因为f元素重复出现了。
精确覆盖问题的形式化表达：
我们可以用一个01矩阵来形式化表达精确覆盖问题，还是上面的例子，我们可以表达为如下的矩阵：
每一行代表一个子集，那么问题就是选择某些行，使得a-f列出现且仅出现一个1。
精确覆盖问题的解法：
Knuth大神给出的解法就是Algorithm X 。 其思想就是从01矩阵入手。解法的过程（不考虑回溯的次数多少）为：
设01矩阵为A
如果 A 是空的，
问题解决；成功终止。
否则，
选择一个列 c（确定的）
选择一个行 r，满足 A[r, c]=1 （不确定的）
把 r 包含进部分解
对于所有满足 A[r,j]=1 的 j
从矩阵 A 中删除第 j 列；
对于所有满足 A[i,j]=1 的 i，
从矩阵 A 中删除第 i 行。
在不断减少的矩阵 A 上递归地重复上述算法。
这个算法的有点麻烦，其实过程很简单。用上面的例子来解释就是
1、选择一个列，这里我们选择a列，找到这一列中有1的所有行，记为row1 , row2 , row3....
2、首先选择row1作为解的一部分，这里为选择第一行，然后将这一行中所有 为1的 列删除（这个行中已经满足了这些列有1）。在上面的例子中就是a , c , f列。
3、在删除a 、 c 、 f 列的过程中，还要删除这一列中有1的行（避免当前列中重复出现1）。以删除f列为例，由于选择第一行了，所以f列的1不能重复出现，即最后一行不能再选择了，所以要删除最后一行。
4、重复上面的1-3步骤，如果矩阵最后为空，那么问题已经解决。否则，说明row1不能选择，我们再回溯问题，不选择row1，选择row2。
X算法的实现：
算法有了，那么怎么实现呢？我们可以递归解决问题，每一步复制一个矩阵，但是如果搜索次数很多的话，需要的空间会比较大。所以又有了Dancing links 的实现（后面叫DLX）。DLX虽然听起来很麻烦，但是他实现起来确实麻烦-，-！本质上DLX就是一个双向十字链表。如下（图是挖别人的。。）：
h是整个链表的表头，A、B、.....G是每一列的列头，其他的是节点。用这个链表来代表上述的01矩阵（这一步应该很容易理解）。然后将矩阵的操作转化为链表的操作。
用DLX的好处是：
1、X算法在链表的列头上进行搜索。==========》如果需要删除某一列，直接删除对应的列头即可。
2、可以方便的进行恢复，假如要删除C列，只需要两个操作便可删除
C.L.R = C.R
C.R.L = C.L
恢复时
C.R.L = C.L
C.L.R = C.R
3、扫描列是否都满足时，不必扫描全部的列，只需判断表头.L 是否 表头即可。
代码：
用Java写的LeetCode的解题数独的解题代码。
public class Solution {
private static final int colmns = 324; //9 * 9 * 3 + 81
private Node head;
private Node[] cols;
private int[] solution = new int[81];
private boolean flag =false;
String sudoku = "53..7...." +
"6..195..." +
".98....6." +
"8...6...3" +
"4..8.3..1" +
"7...2...6" +
".6....28." +
"...419..5" +
"....8..79";
char[][] sudoku1;
private int[][] sudokuArray = new int[9][9];
////////////////////////THE LEETCODE MAIN//////////////////////
public void solveSudoku(char[][] board) {
StringBuilder sb = new StringBuilder();
for(char[] t : board){
for(char tt : t) {
sb.append(tt);
}
}
sudoku1 = board;
init();
construct(sb.toString());
search(0);
}
///////////////////////////////////////////////////////////////
public void init(){
head = new Node();
head.L = head;
head.R = head;
cols = new Node[colmns];
for(int i = 0 ; i < cols.length ; i++){
Node temp = new Node();
temp.C = temp;
temp.U = temp;
temp.D = temp;
temp.R = head;
temp.L = head.L;
temp.r = i;
head.L.R = temp;
head.L = temp;
cols[i] = temp;
}
}
public void link(int r , int[] cs){
Node rowHead = null;
for(int i = 0 ; i < cs.length ; i++){
int c = cs[i];
Node columnHeader = cols[c].C;
Node temp = new Node();
temp.r = r;
if(i == 0){
rowHead = temp;
rowHead.R = rowHead;
rowHead.L = rowHead;
}
///////////
temp.R = rowHead;
temp.L = rowHead.L;
rowHead.L.R = temp;
rowHead.L = temp;
///////////
temp.D = columnHeader;
temp.U = columnHeader.U;
//set the columnHeader
temp.C = columnHeader;
columnHeader.U.D = temp;
columnHeader.U = temp;
columnHeader.count++;
}
}
/**
* remove the column c
* @param c the column obj
*/
public void remove(Node c){
//The column head
Node cHead = c.C;
cHead.R.L = cHead.L;
cHead.L.R = cHead.R;
//System.out.println("remove -----" + cHead.r);
//delete the row of this column
for(Node row = cHead.D ; row != cHead ; row = row.D){
//delete the row
for(Node rowNode = row.R ; rowNode != row ; rowNode = rowNode.R){
rowNode.D.U = rowNode.U;
rowNode.U.D = rowNode.D;
rowNode.C.count--;
}
}
}
/**
* resume the column
* @param c
*/
public void resume(Node c){
Node cHead = c.C;
//resume the row
for(Node row = cHead.U ; row != cHead ; row = row.U){
for(Node rowNode = row.L ; rowNode != row ; rowNode = rowNode.L){
rowNode.D.U = rowNode;
rowNode.U.D = rowNode;
rowNode.C.count++;
}
}
//resume the head
cHead.R.L = cHead;
cHead.L.R = cHead;
}
/**
*
* @return the column header
*/
public Node chooseColumn(){
int min = Integer.MAX_VALUE;
Node result = null;
for(Node c = head.R ; c != head ; c = c.R){
if(c.count < min){
result = c;
min = c.count;
}
}
return result;
}
public boolean search(int k){
//System.out.println(java.util.Arrays.toString(solution));
if(flag == true)
return true;
if(head.R == head){
//System.out.println(java.util.Arrays.toString(solution));
printSolution1();
flag = true;
return true;
}
Node c = chooseColumn();
remove(c); //remove the c
for(Node solutionRow = c.D ; solutionRow != c ; solutionRow = solutionRow.D){
solution[k] = solutionRow.r; //add the solution
//remove the column in the right
for(Node rightNode = solutionRow.R ; rightNode != solutionRow ; rightNode = rightNode.R){
remove(rightNode);
}
//continue searching
search(k+1);
//after searching , resume the state
for(Node leftNode = solutionRow.L ; leftNode != solutionRow ; leftNode = leftNode.L){
resume(leftNode);
}
}
resume(c);
return false;
}
/**
* Construct the two direction circular linked list according to the puzzle which is in the form of
* 2.2.2.2......
* @param puzzle
*/
public void construct(String puzzle){
if(puzzle.length() != 81){
return;
}
for(int i = 0 ; i < puzzle.length() ; i++){
char current = puzzle.charAt(i);
int r = i / 9 ;
int c = i%9;
if(current == '.'){
for(int val = 1 ; val <= 9 ; val++){
link(r*100 + c * 10 + val , getColumnIndex(r,c,val));
}
}else{
int number = current - '0';
link(r*100 + c * 10 + number , getColumnIndex(r,c,number));
}
}
}
public void construct(char[][] puzzle){
for(int pr = 0 ; pr < puzzle.length ; pr++){
for(int pc = 0 ; pc < puzzle[pr].length ; pc++){
int i = pr * 9 + pc;
char current = puzzle[pr][pc];
int r = i / 9 ;
int c = i%9;
if(current == '.'){
for(int val = 1 ; val <= 9 ; val++){
link(r*100 + c * 10 + val , getColumnIndex(r,c,val));
}
}else{
int number = current - '0';
link(r*100 + c * 10 + number , getColumnIndex(r,c,number));
}
}
}
}
/**
* given the row and column and the value , return the four column index of it
* @param r
* @param c
* @param val
* @return System.out.println(java.util.Arrays.toString(solution));
*/
public int[] getColumnIndex(int r , int c , int val){
int[] array = new int[4];
array[0] = r * 9 + val - 1;
array[1] = 81 + c * 9 + val - 1;
// int b = (r / 3) * 3 + c % 3;
int tr = r / 3;
int tc = c / 3;
int b = tr * 3 + tc;
array[2] = 162 + b * 9 + val - 1;
array[3] = 243 + r * 9 + c;
return array;
}
public void printSolution(){
for(int i = 0 ; i < solution.length ; i++){
int r = solution[i] / 100;
int c = solution[i] / 10 % 10;
int val = solution[i] % 10;
sudokuArray[r][c] = val;
}
for(int[] rr : sudokuArray){
for(int vv : rr){
System.out.print(vv + " ");
}
System.out.println();
}
}
public void printSolution1(){
for(int i = 0 ; i < solution.length ; i++){
int r = solution[i] / 100;
int c = solution[i] / 10 % 10;
int val = solution[i] % 10;
sudoku1[r][c] = (char)(val + '0');
}
}
}
class Node{
int r; //represent the solution ****rcv****
//direction pointer
Node U;
Node D;
Node L;
Node R;
//---------
Node C; //the header
int count; //Used to store the count of 1 in column
}LeetCode----Sudoku Solver+精确覆盖问题解法（Dancing Links）