Quell is a single-player grid-based puzzle game. Pearls are scattered across a 2D map and the aim is to collect them all by rolling a drop of water over them. For this challenge we will only consider basic maps containing the drop, pearls, walls, and empty spaces. (The full game includes a variety of additional objects/interactions such as spikes, movable blocks, and teleport rings.) We will also assume that the map is bounded and connected, that is, it is surrounded by walls and a continuous path exists between any two squares.
The drop, initially stationary, may be rolled up, down, left, or right. A distinctive feature of Quell is that once you start the drop rolling, it rolls as far as possible in that direction, stopping only when it hits a wall. Any pearls along the path are collected automatically. Your inability to stop the drop or change its direction until it hits a wall has two consequences:
- There may be empty spaces on the map that the drop can never pass through or pearls that can never be collected (the latter never happens in the real game).
- The order in which pearls are collected matters on some maps because certain moves cut the drop off from areas that were previously accessible.
For example, consider the following map, where O
= drop, @
= pearl, #
= wall, .
= empty space:
#######
#@.#.@#
#..#..#
#O....#
#..####
#@.#
####
We see that the move sequence RULDLUD
(among others) collects all three pearls:
####### ####### ####### ####### ####### ####### ####### #######
#@.#.@# #@.#.@# #@.#.O# #@.#O.# #@.#..# #@.#..# #O.#..# #..#..#
#..#..# R #..#..# U #..#..# L #..#..# D #..#..# L #..#..# U #..#..# D #..#..#
#O....# => #....O# => #.....# => #.....# => #...O.# => #O....# => #.....# => #.....#
#..#### #..#### #..#### #..#### #..#### #..#### #..#### #..####
#@.# #@.# #@.# #@.# #@.# #@.# #@.# #O.#
#### #### #### #### #### #### #### ####
However, if the first move is U
or D
the drop will become trapped in the 'alley' on the left side and then unable to collect the pearl in the top-right corner.
Task
Your goal in this code-golf challenge is to decide whether all pearls in a given map can be collected. Your program/function may take the map in any sensible format (e.g. multiline string, list of lines, matrix), which extends to replacing O@#.
with distinct characters/digits of your choice. To indicate whether the map is solvable or not, output/return either
- any truthy/falsy value (swapping allowed) according to your language's convention, or
- one of two distinct, fixed values of your choice.
For reference, a polynomial-time algorithm for solving this problem is presented here. You are not required to implement this algorithm (though of course you may).
Test cases
Solvable
#########
##....@..#
#.@.O...@#
##....@#.#
#########
(possible solution: RULDR)
######
##@...##
#@.....#
##.....#
###...#
#@O.#
#####
(possible solution: LULDRUL)
#######
#@.#.@#
#..#..#
#O....#
#..####
#@.#
####
(possible solution: RULDLUD)
###############
#..#..........#
#....@.O.@....#
#......@......#
#.@#########@.#
#...@.@.@.@...#
#..........#..#
###############
(possible solution: RLURDRULRDLULDR)
#############
#O........#@#
#.#.........#
#.@....@#...#
#...#@......#
#...@#......#
#........#..#
#..#........#
#..........##
##@........@#
#############
(possible solution: DRULDRULRUDLUDRLUR)
Unsolvable
######
#O...##
#.....#
#..@..#
#@...@#
#######
#####
#.@.#
####...####
#@...O...@#
####...####
#.@.#
#####
#######
#@.#.@#
#..#..#
#O....#
#..#..#
#@.#.@#
#######
###############
#..#..........#
#....@.O.@....#
#....#.@......#
#.@#########@.#
#...@.@.@.@...#
#..........#..#
###############
#############
#O........#@#
#.#.........#
#.@.#..@#...#
#...#@......#
#...@#......#
#........#..#
#..#........#
#..........##
##@........@#
#############