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）