This game has 3 parameters: capacity "c" (of each vial), number of colors "m", and number of empty vials "e". So total number of vials is m+e. Usually e=2 so that's what I've been thinking about. I'm interested in which (c, m) parameter values can yield unsolvable boards. An example unsolvable board for c=3, m=7 (notation is bottom-to-top):
[4 1 5] [2 1 4] [5 6 6] [2 0 0] [2 6 3] [5 0 3] [4 1 3]
A few results that aren't hard to figure out:
- if (c, m) has an unsolvable board, then (c+1, m) has an unsolvable board
- if (c, m) has an unsolvable board, then (c, m+1) has an unsolvable board
- c=2 is always solvable
- m=2 is always solvable
- there are unsolvable boards
These combined imply that there's an interface in (c, m) space between always-solvable parameters (low-cm) and not-always-solvable parameters (roughly, high-cm).
Picture is what I've figured out about this interface. Here are unsolvable boards for c=3, 4, 5:
[4 1 5] [2 1 4] [5 6 6] [2 0 0] [2 6 3] [5 0 3] [4 1 3]
[4 1 5 1] [2 3 3 5] [2 0 0 5] [2 0 0 4] [2 1 1 5] [4 4 3 3]
[1 3 4 2 2] [3 2 0 0 4] [0 3 4 4 1] [3 2 0 0 1] [1 3 4 2 1]
(I'm omitting the 2 empty vials when I report these btw)
I've validated by exhaustive search that (c=3, m=6) is always solvable, and likewise for (c=4, m=5) and (c=5, m=4). And finally I've validated that (c=6, m=4) is always solvable. All these results are just heavy computational searching.
I also have a construction of an unsolvable board for m=3 using very large capacity (c=27): 3 identical vials of
[1 1 1 1 1 1 1 1 2 2 2 2 2 2 0 0 0 0 0 0 0 0 0 2 2 2 1]
The open questions are thus:
- what is the minimal capacity at which unsolvable boards exist for m=3?
- what is the minimal capacity at which unsolvable boards exist for m=4?
can you share the algorithm you've used for the exhaustive search?
>>3mqurbmqxa72l
- Best-first search with heuristic “sum over colors ( number of vials containing color)”, ie how spread out the colors are. The heuristic can be updated for cheap as you discover the state space.
- isometry group is “permutation of colors x permutation of vials.” Quotient by both when enumerating initial boards to check, quotient only by vial permutations when checking an individual board
- skip moves involving completed vials
- represent vials as ints, the board as a tuple, numba-fy and parallelize.
All told, each core ends up determining whether a board is solvable in about 100us on average
Sign in to reply.