Fit is an interactive square packing game that challenges players to arrange identical squares within the smallest possible bounded region.
The Square Packing Problem
Square packing is a classic problem in combinatorial optimization and computational geometry. Given a set of identical squares, the goal is to arrange them so that they fit within the smallest possible rectangular bounding box. While this may seem simple at first glance, finding optimal or even near-optimal packings becomes computationally difficult as the number of squares increases.
The square packing problem is related to broader questions in discrete geometry, such as circle packing, bin packing, and the more general packing problem where objects of various shapes must be arranged efficiently. These problems have applications in manufacturing, logistics, computer graphics, and materials science.
How Fit Works
In Fit, players manually place and manipulate squares on a board. Each square can be moved and rotated in 90 degree increments. The challenge is to find arrangements that minimize the bounding box dimensions, the smallest rectangle that can contain all squares.
By allowing players to explore different configurations through direct manipulation, Fit creates an intuitive interface for understanding the structure of square packing solutions. Players can experiment with rotations, positions, and spatial relationships that might not be immediately obvious to algorithmic approaches.
Why It Matters
Square packing problems, while seemingly simple, remain open research questions in many cases. Optimal packings for even moderate numbers of squares are not always known, and proving optimality can be extremely difficult. Through collective exploration in Fit, we hope to discover patterns, symmetries, and structural insights that could inform both theoretical understanding and practical algorithms.
The data collected from Fit gameplay contributes to ExtSearch's broader mission of mapping solution spaces and understanding the landscape of combinatorial optimization problems. Each player's solutions add to a growing dataset that may reveal hidden regularities or suggest new approaches to these challenging problems.