Algorithm X

Background

In August, 2022, I attempted to solve Constrained Latin Squares, a recently published puzzle by @darkhorse64 on CodinGame. I noticed @5DN1L had, a week earlier, posted a link to Puzzles solvable by Algorithm X / Dancing Links, a post where he had compiled a list of puzzles on CodinGame he had solved with Algorithm X. I love processes that are repeatable and the idea of using a single algorithm to solve a long list of medium/hard puzzles intrigued me.

For the next 18 months, I worked on @5DN1L’s list, reaching out to him over and over again with questions and ideas. I saw tremendous opportunity for not only a reusable software architecture, but also a repeatable engineering process for solving Exact Cover problems. Eventually, he suggested I build an Algorithm X playground, and here we are!

I can’t thank @5DN1L enough for all of his guidance, support, ideas, encouragement, questions, answers, poking, prodding, reviewing, etc. This playground is his creation every bit as much as it is mine. His influence has made a permanent mark on who I am and how I approach problems. I am forever grateful.

What is Algorithm X?

Algorithm X is a promise. If you can build a proper model to a particular problem space, Algorithm X promises to find all solutions to that problem space. Papers have been written and projects have been done to demonstrate “how” Algorithm X works. That is not the goal here. Instead, the focus of this exercise is to build expertise in the realm of modeling. The goal is to build models that Algorithm X easily digests and returns solutions. Only a cursory understanding of Algorithm X is required, and the implementation details will barely be covered. Instead, you will be asked to build models of problems and you will have the opportunity to see how well you modeled each problem simply by seeing how easily Algorithm X converts your models into solutions.

What’s in It for You?

A quick Google search will surely bring you to countless implementations of Algorithm X, usually solving a 9x9 Sudoku grid using the famous Dancing Links (DLX) technique proposed by the brilliant Donald Knuth. This playground is NOT just another Sudoku demonstration. By the time you finish working your way through this material, you should feel confident solving any Exact Cover problem you run across, including…

Exact Cover (Algorithm X Candidate) Puzzles Created for this Playground:
Mrs. Knuth – Part I (+50 XP)
Mrs. Knuth – Part II (+50 XP)
Mrs. Knuth – Part III (+50 XP)
Equation Search (+50 XP)
Ye_ An_th_r W_rd Se_rch (+50 XP)

Support Puzzle Created for this Playground
Shikaku Skill Builder (+50 XP)

Great Candidates for Algorithm X:
Sudoku Solver (+50 XP)
16x16 Sudoku (+50 XP)
25x25 Sudoku (+50 XP)
Mini Sudoku Solver (+50 XP)
Constrained Latin Squares (+50 XP)
Literary Alfabet Soupe (+50 XP)
Shikaku Solver (+50 XP)
Dominoes Solver (+50 XP)
Paving with Bricks (+50 XP)
n Queens (+50 XP)
Finish the Eight Queens (+50 XP)
Optimized Coloring (+50 XP)
Einstein’s Riddle Solver (+50 XP)
Winamax (+250 XP) 🚀🚀🚀
Three Little Piggies (+50 XP)
Breaking Bifid (+50 XP)
Futoshiki Solver (+50 XP)
Suguru Solver (+50 XP)
Dumbbells Solver (+50 XP)
Hitori Solver (+50 XP)
There Is No Spoon – Episode 2 (+250 XP) 🚀🚀🚀
Takuzu Solver (+50 XP)
High-Rise Buildings (+50 XP)
Killer Sudoku Solver (+50 XP)
Kakuro Solver (+50 XP)
Killer Sudoku Extreme Challenge (+50 XP)
Tetris Floor (+50 XP)
Agent X, Mission 2—Mysterious Cryptogram (+50 XP)
Harmless Rooks (+50 XP)
Who Dunnit? (+50 XP)

My Promise to You

I wholeheartedly believe that working through this playground and the accompanying puzzles will be a great experience on multiple levels. How can I say this? All these things happened for me as I studied Algorithm X and applied it to as many puzzles as possible. I promise…

• You will become proficient with a powerful and repeatable problem solving technique known as Algorithm X.
• You will experience the compelling nature of reusable software architectures.
• You will find every puzzle listed above significantly easier than it would have been otherwise. I’m not saying they’ll all be easy, but they will indeed be easier.
• You will have a lot of fun.
• You will earn up to 2200 CodinGame XP!

Prerequisites

• Intermediate level knowledge of Python, including object-oriented programming concepts such as classes and class method overriding. However, if you are new to Python, going through this playground will identify some intermediate level concepts that you might consider moving to the top of your to-study list.

• Cursory understanding of backtracking. To complete this playground, it is more important that you understand the general concept of backtracking than it is you be able to code a backtracking algorithm.

Future Updates

If this is not your first time visiting this playground, be sure to click here to see if any major updates (e.g. new puzzle) have been made since your last visit.