Sure! Here's how the tightest (known) packing of 67, 6767 and 676767 squares in a larger square looks like:
I made the most optimized algorithm to find out the tightest packing of n smaller squares in a larger square
test it out:
forloopcodes.github.io/least… (runs on your gpu)
more details:
input: n (number of squares)
intermediate: s (side length)
output: [[x, y, angle]*n] (array of position of each square)
solver (squarepack): pack(n) returns (s, [[x, y, angle], …])
scale: n=100000 in about 4 s, 0.08 s in browser, n=1000001 in 0.2 s.
verifier: p_ij = ½ + (|cos φ| + |sin φ|)/2 − max_a |a·(c_i − c_j)|, φ = θ_j − θ_i
flow:
1. best of all in O(n): Grid ⌈√n⌉, Göbel strip/square families, L-extensions, the √7 family, DeVincentis,Wainwright 19, Schadt 50/171
2. cache lookup
3. tilted-block search: p×q block rotated 45°, remaining space filled by walls anchoring
4. numerical compaction: Penalty energy E = Σ max(0,penetration)² + Σ max(0,protrusion)², analytic gradient, L-BFGS, shrink s by bisection, basin-hopping.
github:
github.com/forloopcodes/leas…
I'm sure you always wanted to know how the tightest (known) packing of "n" squares within a larger square looks like... 😍