<p>The game that you describe (let's call it &quot;<code>MineFreePath</code>&quot;) is (very) similar to the &quot;<a href="https://en.wikipedia.org/wiki/Minesweeper_(video_game)" rel="nofollow noreferrer"><code>MineSweeper</code></a>&quot; 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) <code>MineSweeper</code> allows to jump to a random position at any time, and that 2) <code>MineFreePath</code> allows to iterate on the same map. The second difference is interesting, but I think that the first difference is negligible:</p>
<ul>
<li>in practice any winning strategy for <code>MineSweeper</code> follows a path in the mine field (Figure shamelessly taken from <a href="https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/abs/minesweeper-game-percolation-and-complexity/C96A8C5AF6E7FC75C389483020B4DCA3" rel="nofollow noreferrer">2</a>):  <a href="https://i.sstatic.net/mz9ff.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/mz9ff.png" alt="a path in the mine field:" /></a></li>
<li>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 <code>MineSweep</code> sub-instance is similar to that one would imagine for reducing it to a <code>MineFreePath</code> sub-instance (Figure shamelessly taken from <a href="https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/abs/minesweeper-game-percolation-and-complexity/C96A8C5AF6E7FC75C389483020B4DCA3" rel="nofollow noreferrer">2</a>): <a href="https://i.sstatic.net/Bmsob.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Bmsob.png" alt="Gadget to reduce a dis-junction to a MineSweep or MineFreePath" /></a></li>
</ul>
<p><a href="https://en.wikipedia.org/wiki/Elchanan_Mossel" rel="nofollow noreferrer">Elkhanan Mossel</a> studied the percolation complexity of a version of the Minesweeper game on an infinite grid in a <a href="https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/abs/minesweeper-game-percolation-and-complexity/C96A8C5AF6E7FC75C389483020B4DCA3" rel="nofollow noreferrer">2002 article</a> (which you should not download from <a href="https://sci-hub.se/10.1017/s096354830200528x" rel="nofollow noreferrer">SciHub</a> as it would probably be unethical), which is even more relevant to the analysis of the <code>MineFreePath</code> 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.</p>
<p>Should you prove formally any results about this version of <code>MineSweeper</code>, I think that the academic community who gathers every two years at the italian conference <a href="https://sites.google.com/view/fun2022/home" rel="nofollow noreferrer">Fun with Algorithms</a> would be interested :)</p>
<p>I hope it helps!</p>

CC BY-SA 4.0
2022-09-04T15:26:44.290Z
This helped me go to the right track. I know now to reduce it to a decision problem! Thanks for helping a beginner!
Bapcap
CC BY-SA 4.0
2022-09-02T11:37:35.473Z
2022-09-02T11:37:35.473Z
J.y B.y
<p>Let's call this the Path Game.</p>
<p>For this example, lets imagine a 16x16 grid:</p>
<p><a href="https://i.sstatic.net/M0K4e.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/M0K4e.png" alt="The Example of the Game." /></a></p>
<p>Some of the squares in this grid are &quot;deadly.&quot; 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.</p>
<p>However, if you pick a &quot;friendly&quot; grid you will be allowed to &quot;mark&quot; 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.</p>
<p>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.</p>
<p>I have 2 questions:</p>
<p>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 &quot;heuristics&quot; 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.</p>
<p>2.: Is the complexity class and name of the game known already If so, where?</p>
<p>Thank you for your time!</p>

CC BY-SA 4.0
2022-09-02T11:02:04.140Z
Minor comment: in order to discuss whether the problem is within classes such as NP, PSPACE or else, you might want to parameterize the input size (e.g. either the size $n$ of the largest side of the grid (16 in your example) or the number of points of the grid (256 in your example)), or to redefine the problem on an infinite grid (as Elkhanan Mossel did for the Minesweeper game).
J.y B.y
CC BY-SA 4.0
2022-09-02T11:42:22.660Z
I don't understand the part of the question " I want the complexity class with heuristics specifically"? And the complexity of remembering ALL squares is just polynomial ($n^2$) in the size $n$ of the largest side of the grid?
J.y B.y
CC BY-SA 4.0
2022-09-02T13:13:14.473Z
*"What is the complexity class of this game?"*  Games don't belong to complexity classes, decision problems do.  What decision problem do you have in mind?  Can you please state it explicitly?  And (as mentioned in another comment) what does "with heuristics" mean?
Neal Young
CC BY-SA 4.0
2022-09-02T16:16:07.000Z
@J..yB..y What I mean by "with heuristics" is if the algorithm can remember which squares are safe. I hope that answers it. Sorry for not clarifying, I was tired when i wrote this.
Bapcap
CC BY-SA 4.0
2022-09-02T16:22:24.393Z
@NealYoung I edited my question to make it clear. I hope the reply to J..y B..y's comment also helps you understand.
Bapcap
CC BY-SA 4.0
2022-09-02T22:57:55.757Z
"if you pick a "friendly" grid" -> you mean "if you pick a "friendly" SQUARE", right?
J.y B.y
CC BY-SA 4.0
2022-09-02T22:59:24.920Z
You still did not describe your problem as a decision problem (and there are several ways to project such a game to a decision problem).
J.y B.y
CC BY-SA 4.0
2022-09-05T18:28:29.313Z
@J..yB..y I will elaborate in case somebody else suffering from the same problem sees this, YES I meant friendly Squares.
Bapcap
<cc.complexity-theory><complexity-classes><time-complexity><gt.game-theory>
What Complexity Class is this? Is this already known?
Bapcap
# What Complexity Class is this? Is this already known?

(Asked by: username_0 on 2022-09-01)

Let's call this the Path Game.

For this example, lets imagine a 16x16 grid:

[![The Example of the Game.](https://i.sstatic.net/M0K4e.png)](https://i.sstatic.net/M0K4e.png)

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!

**Tags:** cc.complexity-theory, complexity-classes, time-complexity, gt.game-theory
> **Comments:**
> **username_1**: Minor comment: in order to discuss whether the problem is within classes such as NP, PSPACE or else, you might want to parameterize the input size (e.g. either the size $n$ of the largest side of the grid (16 in your example) or the number of points of the grid (256 in your example)), or to redefine the problem on an infinite grid (as Elkhanan Mossel did for the Minesweeper game).  
> **username_1**: I don't understand the part of the question " I want the complexity class with heuristics specifically"? And the complexity of remembering ALL squares is just polynomial ($n^2$) in the size $n$ of the largest side of the grid?  
> **username_2**: *"What is the complexity class of this game?"*  Games don't belong to complexity classes, decision problems do.  What decision problem do you have in mind?  Can you please state it explicitly?  And (as mentioned in another comment) what does "with heuristics" mean?  
> **username_0**: @J..yB..y What I mean by "with heuristics" is if the algorithm can remember which squares are safe. I hope that answers it. Sorry for not clarifying, I was tired when i wrote this.  
> **username_0**: @NealYoung I edited my question to make it clear. I hope the reply to J..y B..y's comment also helps you understand.  
> **username_1**: "if you pick a "friendly" grid" -> you mean "if you pick a "friendly" SQUARE", right?  
> **username_1**: You still did not describe your problem as a decision problem (and there are several ways to project such a game to a decision problem).  
> **username_0**: @J..yB..y I will elaborate in case somebody else suffering from the same problem sees this, YES I meant friendly Squares.  

---

## 1 answers

### Answer by username_1 on 2022-09-02. Score: 1 | Accepted answer

The game that you describe (let's call it "`MineFreePath`") is (very) similar to the "[`MineSweeper`](https://en.wikipedia.org/wiki/Minesweeper_(video_game))" 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](https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/abs/minesweeper-game-percolation-and-complexity/C96A8C5AF6E7FC75C389483020B4DCA3)): [![a path in the mine field:](https://i.sstatic.net/mz9ff.png)](https://i.sstatic.net/mz9ff.png)
* 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](https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/abs/minesweeper-game-percolation-and-complexity/C96A8C5AF6E7FC75C389483020B4DCA3)): [![Gadget to reduce a dis-junction to a MineSweep or MineFreePath](https://i.sstatic.net/Bmsob.png)](https://i.sstatic.net/Bmsob.png)

[Elkhanan Mossel](https://en.wikipedia.org/wiki/Elchanan_Mossel) studied the percolation complexity of a version of the Minesweeper game on an infinite grid in a [2002 article](https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/abs/minesweeper-game-percolation-and-complexity/C96A8C5AF6E7FC75C389483020B4DCA3) (which you should not download from [SciHub](https://sci-hub.se/10.1017/s096354830200528x) 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](https://sites.google.com/view/fun2022/home) would be interested :)

I hope it helps!

> **Comments:**
> **username_0**: This helped me go to the right track. I know now to reduce it to a decision problem! Thanks for helping a beginner!  

---

