• Epsilon Learns to Algo
  • Preface
    • Classic Algorithm Books: A review
  • 1 Start from Something Interests Me
    • 1.1 Dancing Links
      • 1.1.1 Exact Cover Problem
  • 2 Reading A Book
  • 3 Methods
  • References
  • Published with bookdown

Epsilon Learns to Algo

1.1 Dancing Links

Dancing links is a data structure proposed as an efficient implementation of the X algorithm which finds all feasible solutions for an exact cover problem.

In the following, I would like to give a brief introduction to the exact cover problem with several applications. Most of the current contents are adopted from the 2018 Christmas Lecture by Donald Knuth.

  • Exact cover problem, restated in my mathematical wordings;
  • The dancing links data structure and its implementation through c++.

1.1.1 Exact Cover Problem

Exact cover problem can be mathematically thought of as a set cover problem. Formally, given a set \(X\) and a subset of its power set \(S \subset 2^X\), find a subset of \(S' \subset S\), such that \(\forall S'_i \in S\)