4
$\begingroup$

The following game is a variant of minesweeper:

There is a 7 by 7 grid of squares. Each square either has a skull or a number indicating the number of squares containing skulls surrounding that square (the number can be 0, equivalent to a blank square in minesweeper). There are exactly 7 skulls, and a skull-free path is guaranteed.

You start from the bottom row of the board and the goal of the game is to move past the top row of the board without traveling through any squares containing skulls. You must enter the grid through one of the squares on the bottom row and must exit the grid through one of the squares on the top row. From each square, you can travel to the neighboring square in each of the 8 directions (the 4 cardinal directions + northeast, northwest, etc.), provided that this neighboring square does in fact exist.

The bottom row is guaranteed to be free of skulls.

If you play with optimal strategy, is this game always winnable without guessing? (I feel like it is not, but I can't currently find a construction proving this, though I have not thought about it that much). If not, what is the approximate probability of winning?

$\endgroup$
  • 1
    $\begingroup$ Can you be more careful in defining the game? Can we assume that the identity of squares are unknown until you move to them, when they are revealed? And are we assuming that the game is winnable by some path? $\endgroup$ – noedne May 13 '18 at 1:04
  • 1
    $\begingroup$ What do you mean by "probability of winning?" What are you taking a probability over? $\endgroup$ – noedne May 13 '18 at 1:11
  • 1
    $\begingroup$ There are always 7 skulls (so yes, a skull free path is guaranteed). Cells are covered from the start and revealed when we travel to them. The player can only travel to a square neighboring it in 8 directions. $\endgroup$ – Max May 13 '18 at 1:13
  • 2
    $\begingroup$ What if the $7$ skulls form a row? $\endgroup$ – noedne May 13 '18 at 1:14
  • 2
    $\begingroup$ If the top three rows are ??XXXXX, 13X4332, and 0111000, then you must guess. $\endgroup$ – noedne May 13 '18 at 1:25
4
$\begingroup$

Here's an idea.

Here I'm going to describe a particular (only?) class of conforming puzzles that require guessing.


Consider this structure, which paints the board with a barrier of ambiguous skull layouts (using a generalization of the notion of a minesweeper circuit): enter image description here

Here, the solid squares of each of the 3 colors represent 3 possible skull layouts (e.g., one possible layout, represented as red, has a skull on each of the three red squares); their corresponding contributing counts are shown below with numbers.


This structure forms the core of a triply ambiguous layout, and requires only 3 skulls (note that there are only 2 each of orange/green, but there's 3 of red; if you can work out that you have 2 skulls left, you can rule out red... for that reason it's required to "bury" a skull if you want the full structure; for example, you might have problems using the full length ambiguity barrier on the top row).


The catch in this layout is highlighted by the boxed numbers; those counts disambiguate the possibilities. For example if the clue at the far right indicates +0 (with respect to the skulls above, which is how the numbers should be read), then our skulls are definitely orange. If that clue instead indicates +1, our skulls are definitely not orange. Note, however, that you can remove this disambiguation simply by placing a skull on that boxed square. This implies that we can force a guess using only 5 skulls (including the "possibly buried" skull).

Of course, you don't need to use the entire ambiguity structure here; you simply need a length sufficient to force passing over when taking into account unambiguous skulls. Both of @noedne's examples use just the left two orange/red ambiguous paths hooked onto a barrier known skulls; as such, they are special cases of this class.

Generally speaking then:

This class of impassible arrangements involves using a subset of anywhere from two squares in this ambiguity barrier to the entire length (on a single row), filled in with squares such that a solid path from left to right (possibly going up/down) is established across either ambiguous squares or skulls; doing so will make travel past the barrier impossible without a guess. Use of this barrier requires covering each end's "box clue" square if squares of this "color" are needed to establish this path; in addition, if the entire barrier is used, one skull must be "buried" (as described above).

...and:

Examples:

enter image description hereFor all member examples I highlight the "solid path" in dark black.


Example A is a non-member because it lacks a "buried skull". We count five skulls, and we know there are 7; that leaves only 2 skulls. Red possibility requires 3 skulls; only orange and green have two skulls. So we might not know whether it's orange or green, but we know it's safe to step in the red areas, and thus we're not blocked.


Example B is a non-member because the leftmost clue is 1, meaning we definitely don't have green squares (you can also work this out the "typical" way; "one of those two, one of those three means that one is safe"). However, I think example B points to a possible class I wasn't describing (it looks like we can layer these ambiguity rows), which is interesting.


Examples C and D are noedne's as mentioned in the comments.


Example E was the one alluded to in the text requiring five skulls (one "virtually" buried; that is, in the consideration of orange or green it could be hidden above the barrier, in contrast to non-member example A; this allows the full barrier strip to be ambiguous).


Example F shows one possible other arrangement, where two "holes" poked into a known skull row are covered to create the blocking solid path using a portion of the ambiguity structure.

$\endgroup$
  • $\begingroup$ an you include some explanation of your notation here? I have no idea what the diagram is trying to tel me $\endgroup$ – Kate Gregory May 14 '18 at 3:39
  • $\begingroup$ @KateGregory The three colors correspond to three possible board layouts. For instance, the green numbers 0111111 in the bottom row indicate the placement of the $2$ green mines in the row above. $\endgroup$ – noedne May 14 '18 at 3:42
  • $\begingroup$ @HWalters Can you be more specific about the "class" that you describe? $\endgroup$ – noedne May 14 '18 at 3:49
  • $\begingroup$ @noedne Does that suffice? (Beyond this it's still at this point just meant as a partial) $\endgroup$ – H Walters May 14 '18 at 4:07
  • 1
    $\begingroup$ Interesting, but there are definitely other possible ambiguous rows, e.g., above X32223X. This is in some sense the "complement" of X21112X. $\endgroup$ – noedne May 14 '18 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.