# 舞蹈链

The Dancing Links algorithm solving a polycube puzzle

## 算法实现

### 主要思想

```x.left.right ← x.right;
x.right.left ← x.left;
```

```x.left.right ← x;
x.right.left ← x;
```

Knuth 发现用朴素算法实现Algorithm X会花费大量的时间来搜索1。当要选择一列的时候，要搜索整个矩阵来找到1。当选择一行的时候，需要在整列中搜索1。为了把搜索时间从 complexity O(n) 降到 O(1)， Knuth 使用了一个 稀疏矩阵 ，只存放所有1 的位置。

### 有可能出现的制约因素

It is also possible to solve one-cover problems in which a particular constraint is optional, but can be satisfied no more than once. Dancing Links accommodates these with primary columns which must be filled and secondary columns which are optional. This alters the algorithm's solution test from a matrix having no columns to a matrix having no primary columns, but doesn't require any further changes. Knuth discusses optional constraints as applied to the n queens problem. The chessboard diagonals represent optional constraints, as some diagonals may not be occupied. If a diagonal is occupied, it can be occupied only once.

## 參考資料

1. ^ Knuth, Donald. Dancing links. Millenial Perspectives in Computer Science. P159. 2000, 187 [2006-07-11]. arXiv:cs/0011047.
2. ^ Hitotumatu, Hirosi; Noshita, Kohei. A Technique for Implementing Backtrack Algorithms and its Application. Information Processing Letters. 1979, 8 (4): 174–175. doi:10.1016/0020-0190(79)90016-4.