# Decidable or not?

English corrected version by Joseph Szabo.
notations:
{A} is the number of mines in region A
[A] is the area of A, the number of covered grids
A\B is the remainder region of A after being deleted by B
A&B is the intersection region of A and B
Theorem 0 : {A} <= [A]
Theorem 1 : If A is a subregion of B and {A} >= {B}, then {B\A} = 0
Theorem 2 : If {A} - {B} >= [A\B], then {A\B} = [A\B] and {B\A} = 0
Only the theorem 2 need to be interpreted. First let see the following
example.
[ ][ ][ ]
[ ] 4 1 [ ]
[ ][ ] [ ]
We have to name the areas.
A B
_____ _____
/ \/ \
/ /\ \
| | | |
\ \/ /
\_____/\_____/
Let A and B be the grids around 4 and 1 respectively.
There are 2 ways to decide this situation. First, since A&B has atmost 1
mine, so A\B must have atleat 3 mines, so 3 grids of A\B have 3 mines.
Second, since A\B has atmost 3 mines, so A&B must have atleat 1 mine, so
B\A has no mine.
Finally, we can mark 3 grids in the left-hand side of 4 and eliminate 2
grids in the right-hand side of 1.
Now let see the abstract meaning of the theorem 2.
A B
_____ _____
/ \/ \
/ /\ \
| | | |
\ \/ /
\_____/\_____/
For the first approach. Since {A&B}<={B}, {A\B}={A}-{A&B}>={A}-{B}. Hence
if {A}-{B}>=[A\B], {A\B}>=[A\B]. By theorem 0, {A\B}=[A\B].
This event can be described by
{A}-{B}>=[A\B]
For the second approach. Since {A\B}<=[A\B], {A&B}={A}-{A\B}>={A}-[A\B].
Hence if {A}-[A\B]>={B}, {A&B}>={B}. By theorem 1, {B\A}={B\(A&B)}=0.
This event can be described by
{A}-[A\B]>={B}
The useful form is
{A} - {B} >= [A\B]
By this way, it's very easy to use it. The easiest way is just find 2
numbers such that has the different satisfies the inequality. For
examples, [p] is a grid should be marked and [x] is a grid should be
eliminated.
[ ][ ][p]
[x] 1 4 [p]
[x] [ ][p]
[x][ ] [p]
[x] 1 [ ] 4 [p]
[x] [ ][p]
[x][ ][ ]
2 3
[x][ ][ ][p]
The last thing I want to say is the symmetry conjecture. It seems that
every symmetry condition makes a symmetry result. For example,
[p][p]
3 [x]
1 [p]
3 [x]
[p][p]
[p][p]
3 [p]
2 [x]
3 [p]
[p][p]
However there exist some counter example
[p][p]
3 [p]
3 [x]
[p][p]
I just suggest that if you can find a symmetry solution for a symmetry
condition, it should be true :P
Please tell me if you can't use my theory to describe any of your
decision, or you can find my fault.
Return to the Minesweeper page