Implementation of reducing N-Dimensional polyomino packing puzzles to the exact cover problem in python.
Inspired by polyomino-solver.
Test puzzles from puzzlewillbeplayed.
Y25 info from Herbert Kociemba.
Exact cover is solved via xcover python package.
Note: Exact cover problems are NP-complete which means solve times can get very long very quickly as problems get larger.
I tried to solve the "25Y" or "125 cube" puzzle. The puzzle consists of 25 Y-shaped pentomino and the goal is to pack these pieces into a 5x5x5 box. (See images). Ended up with something more general.
Puzzle:
I was able to find 60672 solutions (Which is apparently all of them) in 5 minutes CPU time. These are actually 60672/48=1264 solution if not counting symmetries. Finally I was able to solve this puzzle which laid shattered on my shelf for so long (in 1264 unique ways)!
An example usage for packing N dimensions would be a job scheduler. One axis would be the expected execution time for the job, and the rest would be the system resources, i.e. RAM, CPUs, GPUs, etc. This is however a very inefficient way to implement a job scheduler due to the NP-completeness of the problem, plus by default the scheduler would be offline which is usually undesirable.