What Complexity Class is this? Is this already known?

Question

Let's call this the Path Game.

For this example, lets imagine a 16x16 grid:

Some of the squares in this grid are "deadly." If you step on it, you must restart and try to go over again. We will assume that the placement of these deadly squares is random.

However, if you pick a "friendly" grid you will be allowed to "mark" it. In logical terms this means that we know that the square is safe. If you need to start over again, you have knowledge that the square is not deadly.

You may only start from one of the 4 sides of the large 6x6 square and only go horizontal, vertical, or diagonal. No skipping squares.

I have 2 questions:

1.: What is the complexity class of this game? I know that when done by brute force, it should be in the NP class of problems, but with heuristics, it seems to be EXPTIME or PSPACE. By "heuristics" I want the complexity class with when the algorithm can take into account the squares it knows is safe. I already know that with brute force without taking into account the friendly squares it is in NP but I am unaware of the complexity class of this question when memory of the safe squares are taken into account.

2.: Is the complexity class and name of the game known already If so, where?

Thank you for your time!

Answer 1

The game that you describe (let's call it "MineFreePath") is (very) similar to the "MineSweeper" game, a logic puzzle video game, created by Microsoft in the 1990s, where one search for the mines in a mine field. The differences would be that 1) MineSweeper allows to jump to a random position at any time, and that 2) MineFreePath allows to iterate on the same map. The second difference is interesting, but I think that the first difference is negligible:

• in practice any winning strategy for MineSweeper follows a path in the mine field (Figure shamelessly taken from 2):
• the decision problem versions of both problems (deciding if the field can be de-mined) would be of similar complexity, using the same kind of gadgets to show reductions to other problems: for instance, a gadget to reduce a dis-junction to a MineSweep sub-instance is similar to that one would imagine for reducing it to a MineFreePath sub-instance (Figure shamelessly taken from 2):

Elkhanan Mossel studied the percolation complexity of a version of the Minesweeper game on an infinite grid in a 2002 article (which you should not download from SciHub as it would probably be unethical), which is even more relevant to the analysis of the MineFreePath game: check it for yourself, but I am pretty sure that Elkhanan's results (or at least his approach) will generalize, namely that the probability that an instance can be solved depends on the density of the mines in the map.

Should you prove formally any results about this version of MineSweeper, I think that the academic community who gathers every two years at the italian conference Fun with Algorithms would be interested :)

I hope it helps!