codecogs equations

onsdag 29 januari 2020

Minesweeper pt. 3: more gameplay

See part 1 for a description of Tile Domination and Gradient.

Adding the feature from part 2, that guarantees that the instances are solvable makes the game much more satisfying. With this knowledge, I could spend all the time thinking of clever inferences, instead of wondering whether the instance is solvable at all. This post contains some interesting cases that I ran into.

Tile Domination


Typical tile domination. The 2 dominates the upper 1 (sees all tiles of it, plus some more)
Tile domination with very good payoff! The yellow tiles contain exactly one mine.

A nice interdependence between the top three middle tiles, give us that the red tile is a mine. Could also be solved with tile domination between the "1" and one of the "2"s.

Gradient

A hard to spot application of the gradient rule. The yellow tiles must contain exactly one mine.
Another hard to spot gradient, between the middle "1" and the middle "3". The yellow tiles contain exactly one mine. 

Global constraint

(counting total number of mines)

Typical application of the global constraint. The colored area is the only unknown area left in the game. The yellow, orange, and turquoise tiles contain exactly one mine each. Since there are only three mines left in the game, the green tiles must be free.

A larger application of the global constraint. The yellow and orange tiles must contain exactly two mines each. The turquoise tiles contain exactly one mine. Therefore, the green tiles are free.
Applying the global constraint with two remaining separate areas. There is just one way to assign two mines so as to "touch" all unsatisfied tiles. 


 Multi-step inferences

Shared tile domination: the "2" on the lower left must be satisfied by the combined yellow and orange tiles.


Proving that the "box" is filled diagonally. I have marked colored boxes around the tiles that yield the conclusions about the colored tiles. The order of reasoning goes first: yellow, orange, purple, and turquoise must all contain one mine, by straight application of adjacency constraints. Then brown is inferred to contain one mine based on orange, purple, and turquoise. With this, we see that the green tiles are free. 

Yellow, turquoise, and brown fields contain one mine by adjacency constraints. From yellow, we get the orange by tile domination. Using the same reasoning about the box as above, the purple must contain one mine, so the green tiles are free by saturation of the right "1". Using the box in the other direction, the tile directly above the left "3" must be free. 

Inga kommentarer:

Skicka en kommentar