Demo
Dissertation
Dissertation stats:
|
|
Download
"This project has covered a lot of new ground and involved the creation of many algorithms for tackling the sub-problems within the larger goals of generating and solving 3D puzzles. These include:
- How voxelization can be used to create 3D puzzles from existing polygonal models.
- How to construct the leftmost and rightmost solutions for a 2D line by first finding the naïve solutions and then iteratively shifting blocks until all existing state is accounted for.
- Finding all possible solutions for a 2D line by recursively finding the set of spreads for a line then moving these along to find the set of shifts.
- How to measure the ‘leftness’ of a given solution to extract the leftmost and rightmost solutions from the set of all solutions.
- A simplified approach to the linesolver algorithm which uses just two deduction techniques: one to find solid cells and one to find empty cells. The situations where these techniques could lead to false positives are described and handled appropriately. It was also shown how empty lines and lines with a complete description can be detected and solved immediately as early-outs.
- How 2D solving techniques can be applied to 3D puzzles by treating 3D clues as simultaneous sets of 2D clues.
- How to expand a 3D clue into a set of 2D clues, known as finding the compositions of n, where n is the block size. Specific algorithms for finding the double expansion and triple+ expansion of n were described.
- A discussion of different approaches to applying linesolvers to the puzzle space with the goal of using fewer linesolvers and having a lower bad guess rate. A performance comparison of the brute-force, hierarchical and heuristic solvers was conducted and the results discussed.