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!