TODO: write up this page more thoroughly
TODO: create benchmarking to compare algorithms/implementations

classic

baby elephant

magic

sun shower

chaos

18 pieces

18 pieces (flip side)

Rules of the Game

• → You are given an 8x8 reference board, like one of the examples above
• → There are 18 pieces (above), each of which needs to be packed into the 8x8 board
• → The objective is to pack all pieces to recreate the reference board

Algorithmic Approaches

The naiive algorithm that one would come up with is simple backtracking approach in which we try all piece placements. The first implementation decision I made was to use Rust. At this point, I thought perhaps I should try to generate all possible solutions as it would help answer some of my curiosities:

• → How many ways are there to pack all 18 pieces into an 8x8 grid (pure packing problem)?
• → For a given reference board, how many solutions exist?
• → If I can answer the last question, what is the distribution of reference boards with multiple solutions?

However, before doing that I quickly reasoned about the upper bounds and the size of the database I would need to store all solutions

$S = \text{solutions to the packing problem}$
$|S| \leq 4^{64} = 340,282,366,920,938,463,463,374,607,431,768,211,460 \approx 3.4 * 10^{38}$

TODO: .... finish writing this

See the repository (08.21.2023)