Fill Solver
I made a solver for the game Fill (on Google Play and Apple Store). The solver works for stages that have unique solutions, plus some that do not.
The basic algorithm solves by inspection and runs in O(nα(n)) time and O(n) space for n cells. It can solve most but not all stages.
Consider a tree representing where guesses have to be made. For each node, we check its immediate children. If exactly one child is feasible, we continue traversing without counting it towards the depth. Depth-first search (DFS) can explore the tree to depth D in O(n²4Dα(n)) time and O(n + D) space.
The Hamiltonian path problem for general grid graphs is an NP-Complete problem.
These 13 stages cannot be solved, as they break the assumption of a unique solution: 2611, 2672, 2726, 2730, 2745, 2755, 2759, 2821, 2825, 2835, 2845, 2849, 2879
| Depth | 0 | 1 | 2 | 3 | 4 | 5 | 6 | ≥7 |
|---|---|---|---|---|---|---|---|---|
| Solved | 2234 | 2632 | 2708 | 2743 | 2768 | 2783 | 2786 | 2787 |
| Solved % | 79.79 | 94.00 | 96.71 | 97.96 | 98.86 | 99.39 | 99.50 | 99.54 |
| Unsolved | 566 | 168 | 92 | 57 | 32 | 17 | 14 | 13 |
| Unsolved % | 20.21 | 6.00 | 3.29 | 2.04 | 1.14 | 0.61 | 0.50 | 0.46 |
Level 27 and 28 are alternate versions of Level 1: stages 27xx and 28xx are alternate versions of 1xx.