Dancing Links用来解决如下精确匹配的问题:

选择若干行使得每一列恰好有一个1。Dancing Links通过对非零元素建立双向十字循环链表。上面的例子建立的链表如下所示：

计算的时候使用搜索的策略。每次选出1最少的一列，比如c，然后选择这一列中的某一行，比如r，(r,c)=1,然后r中所有1所在的列，那些其他行这些列有1的都删掉（这些行不会在r算入答案后也在答案里，否则就有某些列多于一个1出现）。然后这就变成一个规模更小的问题，继续搜索。无解时要回溯。

1 class CDancingLinks  2 {  3 protected:  4     struct DancingLinksNode  5     {  6         DancingLinksNode* left;  7         DancingLinksNode* right;  8         DancingLinksNode* down;  9         DancingLinksNode* up; 10         int col; 11         int row; 12     }; 13  14     typedef DancingLinksNode Node; 15  16     int *m_columnEleNumbers; 17     int m_colNumber; 18     int m_rowNumber; 19     Node* m_pool; 20     Node** m_head; 21     int m_curUsePoolIndex; 22  23  24  25  26  27     void _Remove(Node* cur) 28     { 29         --m_columnEleNumbers[cur->col]; 30         for(Node* p=cur->down;p!=cur;p=p->down) 31         { 32             p->left->right=p->right; 33             p->right->left=p->left; 34         } 35     } 36  37     void _Resume(Node* cur) 38     { 39         ++m_columnEleNumbers[cur->col]; 40         for(Node* p=cur->up;p!=cur;p=p->up) 41         { 42             p->left->right=p; 43             p->right->left=p; 44         } 45     } 46  47  48  49     bool _SearchSolution(const int depth,std::vector
     
       &solution) 50     { 51         Node* p=_GetNode(0); 52         if(p->left==p) return true; 53  54         int Min=m_rowNumber+1; 55         int MinColumnIndex=0; 56         for(Node* q=p->left;q!=p;q=q->left) 57         { 58             if(m_columnEleNumbers[q->col]
      
       col]; 61                 MinColumnIndex=q->col; 62             } 63         } 64  65  66         for(Node* q=_GetNode(MinColumnIndex)->down;q!=_GetNode(MinColumnIndex);q=q->down) 67         { 68             _Remove(q); 69             solution.push_back(q->row); 70             for(Node* rr=q->right;rr!=q;rr=rr->right) _Remove(rr); 71             if(_SearchSolution(depth+1,solution)) return true; 72             for(Node* rr=q->left;rr!=q;rr=rr->left) _Resume(rr); 73             solution.pop_back(); 74             _Resume(q); 75         } 76  77         return false; 78     } 79  80     Node* _GetNode(int id) { return m_pool+id; } 81  82     void _ReleaseMemory() 83     { 84          if(m_columnEleNumbers) 85         { 86             delete[] m_columnEleNumbers; 87             m_columnEleNumbers=nullptr; 88         } 89  90         if(m_pool) 91         { 92             delete[] m_pool; 93             m_pool=nullptr; 94         } 95         if(m_head) 96         { 97             delete[] m_head; 98             m_head=nullptr; 99         }100     }101 102 public:103 104     CDancingLinks():m_colNumber(-1),m_rowNumber(-1),105         m_columnEleNumbers(nullptr),m_pool(nullptr),m_head(nullptr) {}106 107     /***108       列下标为[1,Column]109     ***/110     CDancingLinks(const int Column,const int Row):111         m_columnEleNumbers(nullptr),m_pool(nullptr),m_head(nullptr)112     {113         SetSize(Column,Row);114     }115 116     /***117       列下标为[1,Column]118     ***/119     void SetSize(const int Column,const int Row)120     {121         m_colNumber=Column;122         m_rowNumber=Row;123 124         _ReleaseMemory();125 126         m_columnEleNumbers=new int[m_colNumber+1];127         m_pool=new Node[m_colNumber*(m_rowNumber+1)+1];128         m_head=new Node*[m_rowNumber+1];129         Clear();130     }131 132     void Clear()133     {134         for(int i=0;i<=m_colNumber;++i)135         {136             Node* cur=_GetNode(i);137             cur->left=((i==m_colNumber)?_GetNode(0):_GetNode(i+1));138             cur->right=((0==i)?_GetNode(m_colNumber):_GetNode(i-1));139             m_columnEleNumbers[i]=0;140 141             cur->up=cur->down=_GetNode(i);142             cur->col=i;143             cur->row=0;144         }145         for(int i=1;i<=m_rowNumber;++i) m_head[i]=NULL;146         m_curUsePoolIndex=m_colNumber+1;147     }148 149     ~CDancingLinks()150     {151         _ReleaseMemory();152     }153 154     void AddElement(const int row,const int col)155     {156 157         Node* cur=m_pool+(m_curUsePoolIndex++);158 159         cur->up=_GetNode(col);160         cur->down=_GetNode(col)->down;161         m_pool[col].down->up=cur;162         m_pool[col].down=cur;163 164 165         if(m_head[row]==NULL)166         {167             m_head[row]=cur->left=cur->right=cur;168         }169         else170         {171             cur->left=m_head[row]->left;172             cur->right=m_head[row];173             m_head[row]->left->right=cur;174             m_head[row]->left=cur;175         }176         ++m_columnEleNumbers[col];177         cur->col=col;178         cur->row=row;179     }180 181     bool GetSolution(std::vector
       
         &Solution)182     {183         return _SearchSolution(0,Solution);184     }185 };