Counting minesweeper boards up to symmetry.

[aradesh]

After recent chat in the IRC I've been trying to compute number of boards, yet counting boards that can be achieved by symmetries of the board to be equivalent.

Some group theory:

Let B be the set of (n x n)-boards (restricted to certain number of mines if desired. Let D8 be the group of symmetries of the square.
D8 looks like this:

D8 = {I, a, a^2, a^3, x, ax, a^2x, a^3x}

where a = 90 degree rotation, x = horizontal reflection. (Then we have that a^2x is vertical reflection and ax, a^3x are the diagonal reflections.
D8 naturally acts on B and gives us a group action

Some terminology.
Let x in B be a board.
The orbit of x is the set:
Orb(x) = (D8)x = {gx | g in D8}.
This is the set of all boards that can be obtained from x via applying any symmetry in D8 to it. For example if x is a board which has no symmetries, then Orb(x) contains 8 boards. If x is fixed under 90 degree rotations, but no reflections, then Orb(x) contains only two different boards. So the size of the orbit gives us an idea as to "how symmetric" the board x is. The bigger the orbit, the less symmetric x is.
For any g in D8, define
B^g = {x in B | gx = x}.
So this is the set of boards which are fixed under the symmetry g. This is in general quite easy to calculate for each g.

Strategy.
Now what we want to calculate is the number of distinct orbits of B. i.e. splitting B up into subsets, each of which contain boards which are all obtainable by actions of D8. The set of all orbits of B is called the quotient of the action and is denoted:
B/D8 = {Orb(x) | x in B}.
So what we want to calculate is |B/D8|.
So we just apply Burnside's Lemma (http://en.wikipedia.org/wiki/Burnside%27s_lemma):
|B/D8| = (1/|D8|)Sum{|B^g|, g in B}
= (1/8)[B^e+ B^a + B^(a^2) + B^(a^3) + B^x + B^(ax) + B^(a^2x) + B^(a^3x)]
and this gives us the answer.

Specific examples.

Example 1.
Let B be the set of 4x4 boards containing only 4 mines.
B^e = Binom(16,4) = 1820
B^a = B^(a^3) = Binom(4,1) = 4
B^(a^2) = B^x = B^(a^2x) = Binom(8,2) = 28
B^(ax) = B^(a^3x) = Binom(4,0)*Binom(6,2) + Binom(4,2)*Binom(6,1) + Binom(4,4)*Binom(6,0) = 1*15 + 6*6 + 1*1 = 52.

So by Burnside's Lemma:
|B/D8| = (1820 + 2*4 + 3*28 + 2*52)/8 = 2016/8 = 252

So there are 252 distinct 4x4 boards with 4 mines up to symmetry.

Example 2: Beginner boards.
Let B be the set of beginner boards.
B^e = Binom(64,10) = 151,473,214,816
B^a = B^(a^3) = 0
B^(a^2) = B^(x) = B^(a^2x) = Binom(32,5) = 201,376.
B^(ax) = B^(a^3x) = Binom(8,0)*Binom(28,5) + Binom(8,2)*Binom(28,4) + Binom(8,4)*Binom(28,3) + Binom(8,6)*Binom(28,2) + Binom(8,8)*Binom(28,1)
=1*98,280 + 28*20,475 + 70*3,276 + 28*378 + 1*28 = 911,512
So by Burnside's Lemma:
|B/D8| = (151,473,214,816 + 2*0 + 3*201,376 + 2*911,512)/8 = 151,475,641,968/8 = 18,934,455,246

So there are 18,934,455,246 distinct beginner boards.

I'll let everyone else have fun checking my working and calculating distinct intermediate and expert boards!

[Tjips]

I did the same calculation for the int boards and come up with:
13115156192346373485000211099954895788134532256
or 1.312 x 10^46 boards.

[aradesh]

Verifying your int board calculation, I get the same result:

Code: Select all

def factorial(n):
   if n < 2: return 1
   else: return n*factorial(n-1)
   
def ncr(n,r):
   return factorial(n)/(factorial(r)*factorial(n-r))

diag_fixed = 0
for i in xrange(8+1): diag_fixed+= ncr(16, 2*i)*ncr(120, 20-i)
total_boards = (ncr(256,40) + 3*ncr(128,20) + 2*ncr(64,10) + 2*diag_fixed)/8

print total_boards

output: 13115156192346373485000211099954895788134532256
~= 1.3*10^46

[aradesh]

And follow the link to see wolframalpha getting the same result (link was too long for ordinary format :

Code: Select all

http://www.wolframalpha.com/input/?i=%28Binomial[256%2C40]+%2B+3*Binomial[128%2C20]+%2B+2*Binomial[64%2C10]+%2B+2*sum[Binomial[16%2C2*i]*Binomial[120%2C20-i]%2C+{i%2C0%2C8}]+%29%2F8