Shikaku Solver

Published Difficulty: Medium

Algorithm X Complexity: The Puzzle Will Make You Smile

Strategy

I distinctly remember when I first finished the Shikaku Solver puzzle. I had just gotten started with Algorithm X and, if I remember correctly, this was the first exact cover puzzle I solved that did not feel like some sort of Sudoku. I came up with an exhaustive list of rectangles that could be placed on the grid, I fed those rectangles into Algorithm X and I was immediately rewarded with a list of solutions. I remember thinking to myself, "Wow, this is so cool!" I did not have to think about the backtracking at all. Algorithm X simply worked as advertised.

The skill building in the last section should have given you a strong foundation with which to get started on this puzzle, but you still have some challenging work to do. Even if you successfully build a full list of possible rectangles and Algorithm X gives you solutions, determining the correct output will require some attention to detail.

At the time of this writing, only 180 CodinGamers had finished this puzzle in the 5 years since it was published. I hope this playground inspires many, many more people to finish it. I believe the skills learned by this deep dive into Shikaku will serve you well as you move into some of the more complex exact cover problems still to come.