Simultaneous Maze Solving is NP-Hard!
What is this all about?
The Simultaneous Maze Solving Problem is explained here. On this site, we present an implementation of the NP-hardness reduction from CNF-SAT to the Simultaneous Maze Solving Problem which was given in the paper The Simultaneous Maze Solving Problem.Rules
You are given a set of mazes where you can walk on the white fields but cannot enter the gray fields and you can move up, down, left, and right. The move is executed in all mazes at the same time. If you stand next to a blocked (i.e., gray) field and you move in this direction then you stay in the same field in this maze.Try for yourself
Enter a SAT formula in conjunctive normal form and press generate to generate the resulting mazes of the reduction. You can then make moves using the buttons or the arrow keys of your keyboard (if this does not work, try clicking on a maze first). As we reduce to the decision problem, there is a number of goal moves. The SAT formula is satisfiable if and only if this set of mazes is solvable in the required number of moves.
Moves: 0
Goal: 0
