This project provides a generic Java solver for exact cover with color problems that implements the solver using dancing links.
Most XCC solvers you find in the internet are faithful recreations of the algorithm described by Donald Knuth in The Art Of Computer Programming, Volume 4B with all the issues that come with "scientific classroom code." This implementation tries to provide an implementation that follows well established good programming practises, is thoroughly documented, as easy to understand as humanly possible with descriptive and human-readable variable names, and accepts the fact that it is not necessarily always possible (or even feasible) to represent the universe with an integer.
A fairly faithful implementation of the algorithm that uses Knuth's array based matrix is also provided for reference.
The main issue with the common XCC implementation is initialization of the data structure. Even a fairly simple XCC problem easily contains thousands of items and hundreds of options and loading up the options into the solver can be tedious. This implementation attempts to solve the problem by extracting the item initialization into s dedicated class: ItemProvider. The user adds options to the DLX implementation and the DLX implementation queries the ItemProvider for the relevant items.
The implementation does not place any restrictions on the objects used to represent options. They can be fully fledged Java domain objects that represent the action being done when the option is included in the solution or Strings or Integers if they are sufficient. The only requirement is that an option can be mapped to items consistently.
For example, the sample implementation of the N queens problem solver defines the option as "placing a queen into a specific location on the chess board" (e.g. "queen to d6"). The option item mapper receives the option and calculates the row-, column- and diagonals that the placement covers.
For primary items, the only restriction is that they implement the equals and hashCode methods correctly. Secondary items must also implement the SecondaryItem iterface and ensure that a possible color attribute is not included in equals and hashCode. I.e. two items that represent the same constraint with different color must always be equal.
Run performance tests by executing command
$ mvn jmh:benchmark
- XCC.java: A common interface for XCC implementations.
- LinkedXCC.java: Implementation that uses pointers for the doubly linked matrix.
- ReferenceXCC.java: Recreation of Knuth's array based solver.
- Sudoku solver
- Pentomino solver
- N-queens solver
- Word box solver
I publish this code into the public domain. Feel free to copy, modify, break and fix it as you see fit. You are under no obligation to share your work to anyone (although I would of course always be curious to know how my code can be improved).
Any questions? E-mail: asb (a) iki.fi