The n=17 Square Packing Problem
The image below is the most efficient n=17 square packing arrangement yet discovered. It was proposed by John Bidwell in 1998. It is unbeaten, but not proven optimal.
As a valid square packing arrangement, it contains squares which do not overlap, inside a larger square container. The container is the width/height of ~4.675530 squares.
It won’t have escaped the reader’s attention that this square packing arrangement is quite messy. It has 10 axis-aligned squares, 6 squares tilted at a ~39.8° angle, and a single square at a ~53.4° angle.
An interesting feature of the n=17 square packing problem is that the best provable lower bound on the size of the container is ~4.4452 squares. That means that the highest lower bound discovered so far is very nearly a quarter of a square’s width smaller than the best known solution.
The best known lower bound more precisely:
$$ \frac{40\sqrt 2+19}{17} $$I thought it would be fun to spend some time looking into which offers so much room for improvement: the smallest known arrangement, or the greatest known lower bound?
The project involved machine learning. A model was created that could take a randomised arrangement of squares, and pack them more efficiently with small adjustments. The square packing code (and data, trained model weights etc.) are available on Github.
The world record was not broken. A new lower bound, however, may have been established.