Algorithm X

Polyominoes

Puzzle: Polyominoes

Author: @VizGhar

Published Difficulty: Medium

Algorithm X Complexity: Textbook Exact Cover

Strategy

Donald Knuth covers Algorithm X and Dancing Links in The Art of Computer Programming, Volume 4B Combinatorial Algorithms, Part 2. The PDF I purchased from informIT is 734 pages! In November, 2000, Knuth published a 26 page PDF titled Dancing Links on arXiv.org where it can be downloaded for free.

Knuth’s short paper is a great read. Not only does he cover Dancing Links in detail, he provides some interesting history of exact cover research and some powerful combinatoric data. Most importantly (for this page of this playground anyway), he provides significant detail on applying Algorithm X to Pentominoes, a subset of Polyominoes where every puzzle piece is made up of exactly 5 squares. Knuth’s Pentominoes explanation should provide any guidance you need to finish this puzzle.

Polyominoes uses the CodinGame Game Engine Software Development Kit (SDK). The SDK provides a viewer used to display a visual aspect to any game. Using the viewer, @VizGhar creates a beautiful visual of the polyominoes, twisting and turning as they gracefully fly across the gameboard and into place. In the words of @darkhorse64, “This [puzzle] creates a new standard for exact cover puzzles.”