Variant to Minesweeper

Question

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?

Answer 1

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):

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:

For 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.