Parallelization of the dancing links algorithm

摘要

In this paper we provide a parallel formulation of the dancing links algorithm described by Donald E. Knuth. This algorithm uses an efficient encoding of the exact set cover problem. Using backtracking the state space is search in a depth-first manner. We will derive the parallel algorithm and outline some implementation details. We conclude with experimental results for the n-queens-problem showing the nearly linear speed-up of the presented approach.