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