Blokk! is the ultimate puzzle game. It is easy to learn, but hard to master. It's also an interesting mathematical and algorithmic puzzle, which this project explores.
| Now | Later |
|---|---|
| - Determine all solutions to the game - Develop an API for set(pieces) -> set(solutions) |
- UX with a 3D viewer of solutions - An AI player (RL?) |
🎯 Goal: Find all subsets of the game pieces that can be assembled into a perfect cube of dimension cube_size with volume cube_size**3.
The first algorithm is based on the Integer Partition problem, scanning through and testing subsets of game pieces based on their volume.
- Generate all the subsets of
blokksthat have a combined voxel volume equal to the perfect volumecube_size**3. This is analogous to the integer partition problem, which is solved with sequential generation, and doesn't parallelize well, so we save these subsets to disk. The saved partitions can then be parallelized and track/resume progress. - Separately generate all possible rotations and translations of the blokk within the cube. Cache these.
- Iterate through the cartesian product of all possible rotations and translations of each blokk in the subset
- Add the blokks together.
- If no voxels overlap, then this subset is a solution!
- If any voxels overlap, this is not a solution. Continue searching.
- If you have processed the last element of the product, and haven't yet found a solution, then this subset is not a solution.
- Save the outcome to disk.
Prerequisites
- Python poetry
- Optionally, duckdb cli Installation steps
- Install with
poetry install - Run tests with
poetry run pytest - Check the available commands with
poetry run poe - Generate and write blokk samples to duckdb
poetry run poe save-blokk-samples - Generate and write blokk rotations and translations to duckdb
poetry run poe save-blokk-positions(coming soon) - Optionally, inspect and analyze the results with the duckdb ui
duckdb -ui blokk.duckdb - ... and more to follow