Algorithm X
Going Forward
This playground was first published in December 2024. I have no doubt many more exact cover problems will come my way, and I look forward to seeing how well the techniques laid out here apply to each one.
Instead of inserting new puzzles into the sections to which they might have been assigned during playground construction, those puzzles will be placed here. My hope is to provide an overview of each puzzle, but maybe a bit less guidance as to which techniques I believe fit the puzzles best.
If you find a puzzle you would like me to consider adding to this section, please leave a comment or reach out to me in the CodinGame Forum. Below are links to all the major topics you may want to revisit if you get stuck. Good luck!
Actions
The individual steps you can take to build a solution.
Requirements
The necessary details a solution must satisfy.
Optional Requirements
Details a solution may or may not satisfy, but if satisfied, they must only be satisfied one time.
Mutual Exclusivity
Using optional requirements to enforce situations where two elements must not both be part of the same solution.
Multiplicity
Handling situations where certain requirements must be covered more than one time.
Steering Algorithm X
Keeping track of your problem's state outside the Algorithm X matrix so you can redirect Algorithm X when certain search paths are known to lead to dead ends.
Coloring Your Requirements
Handling situations where certain requirements may be covered more than one time as long as they are covered by the same “color”.
All-or-None Sets of Events
Identifying situations where certain actions must happen together or certain elements must be the same.
Enforcing Sameness with Complex Actions
Bundling simple steps into a group of steps that must be added to a solution as a whole.
Customizing Your Solver’s Row and/or Column Selection
Influencing the order in which Algorithm X selects columns and/or rows as it searches the matrix for solutions.
Problem-Space Reduction
Using logic to solve part of a problem, leaving a more manageable task for Algorithm X.