Comparative Empirical Analysis of Dancing Links Implementations to Solve the Exact Cover Problem
Andrija Sevaljevic, Paul Bodily · 2024
Understanding and efficiently solving NP-complete problems remains a fundamental challenge in computational theory (CT). This paper presents XD, a modified Dancing Links algorithm (DLX) that solves the NP-complete exact cover problem. We implement the algorithm using dictionaries and compare this implementation against a more traditional implementation that uses matrices to assess cases in which each implementation performs best. One of the key strengths of the modified algorithm is its simplicity and adaptability. Our implementation is included in Redux, an online, interactive, dynamic knowledgebase of NP-complete problems, reductions, and solution algorithms.