PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
Since Smart Chef must provide a route that can solve the maze regardless of which maze Evil Chef constructs, we can imagine that Evil Chef constructs all of the mazes and places a robot in each. Then Smart Chef needs to provide a sequence of moves that will lead all of the robots to their respective exits.
The simplest way to do this is one maze at a time. Pick any maze, and construct a sequence a sequence of moves that will move the robot in that maze to its exit. Have all of the other robots execute these moves as well. Then repeat until all robots are at their exits. Moving a single robot to its exit can be accomplished with a depth-first-search.
The winning solution used beam search. As a heuristic, it uses the sum of the minimum number of moves it would take each robot individually to reach its exit. It looks ahead 10 moves to try to find the state with the lowest heuristic. However, it doesn’t actually try all possible sequences of length 10, as this would exceed one million sequences. Instead, it limits the search to the best 160 sequences at each depth. Once it’s looked ahead 10 moves, it executes the first move of whichever sequence resulted in the lowest heuristic. However, it is possible for this algorithm to get stuck in loop where it alternates between 2 states. To prevent this, the solution hashes each position, and makes sure it never visits the same state twice. It also improves speed by precalculating a table in order to move a single robot 3 times with a single array lookup.
At this time I suspect the problem to be NP-complete, but do not have a proof. However, the variant of the problem where each maze is allowed to have up to 3 exits is NP-complete, via reduction from 3-SAT.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.