I've been trying to calculate the number of possible opening shapes that can exist on an mxn board.
For example on a 3x3 board, there are 16 possibilities i.e. (the positions of the mines are irrelevant, it is the shape of the 0's I'm interested in):
Code: Select all
m 1 0
2 2 1 and it's 4 rotations
1 m 1
m 1 0
2 2 0 and it's 4 rotations
m 1 0
m 1 0
1 1 0 and it's 4 rotations
0 0 0
1 1 1
1 m 1 (i.e. zero openings)
1 1 1
0 1 m
1 2 1 and it's reflection
m 1 0
0 0 0
0 0 0 (everything an opening)
0 0 0
Code: Select all
1 2 3 4 5 6
-+-------------------------------------
1| 2 2 4 6 10 16
2| 2 2 4 6 10 16
3| 4 4 16 36 100 256
4| 6 6 36 116 432 1556
5| 10 10 10 432 2426 12518
6| 16 16 256 1556 12518 93390
The way I computed these was by counting the number of shapes you can make by placing 3x3 squares onto the grid, except for at the edges where they're allowed to be 2x3 or in the corners where they can be 2x2. In otherwords examining the area under influence by mines rather than the openings themselves.
With the python program I made I can calculate up to 6xn, so I could make that table go to 6x10 or 6x20 if I wanted, but the numbers would become very large.
The algorithm works by assiging a vector of numbers from 0 to 3 to the ends of possible configurations, so in the following example:
Code: Select all
- - # # # .... 3
- - # # # .... 3
- - - # # .... 2
Code: Select all
. . # ... 1
. . # ... 1
. . . ... 0
At the moment the program is very inefficient, and considers signatures that never occur in practice, and it also does not simplify using reflections. With these modifications the method as it stands could perhaps get up to 10xn boards or so. Just to put into perspective how inefficient it is at the moment, simply by not using signatures that never occur in practice I suspect that for the n=6 case I could use a 622x622 matrix instead of a 4096x4096 matrx, and I suspect that using simplifying observations it could further be reduced to a 207x207 matrix.
Here is the code I used, sorry for the unreadibility of it! Perhaps someone with a more powerful computer than me (you'll need at least 2GB ram) could run it for h=7 and post the data so that I can add new columns to the table above?
Code: Select all
def num_to_b4(i,height):
# converts i to base 4
t = [0 for i in range(height)]
for j in range(height):
t[j] = i%4
i//=4
return t
def b4_to_num(t):
i = 0
for j in range(len(t)):
i*=4
i+=t[len(t)-1-j]
return i
def first_col(h):
if h == 1:
return [[0],[1]]
if h == 2:
return [[0,0], [1,1]]
if h == 3:
return [[0,0,0], [0,1,1], [1,1,0], [1,1,1]]
if h == 4:
return [[0,0,0,0], [1,1,0,0], [1,1,1,0], [1,1,1,1], [0,1,1,1], [0,0,1,1]]
if h == 5:
return [[0,0,0,0,0],[1,1,0,0,0],[1,1,1,0,0],[1,1,1,1,0],[1,1,1,1,1],[0,1,1,1,1],\
[0,0,1,1,1],[0,0,0,1,1],[0,1,1,1,0],[1,1,0,1,1]]
if h == 6:
return [[0,0,0,0,0,0], [1,1,0,0,0,0],[1,1,1,0,0,0],[1,1,1,1,0,0],[1,1,1,1,1,0],[1,1,1,1,1,1],\
[0,1,1,1,1,1],[0,0,1,1,1,1],[0,0,0,1,1,1],[0,0,0,0,1,1],[0,1,1,1,0,0],[0,1,1,1,1,0],\
[0,0,1,1,1,0],[1,1,0,0,1,1],[1,1,1,0,1,1],[1,1,0,1,1,1]]
if h == 7:
return [[0,0,0,0,0,0,0],[1,1,0,0,0,0,0],[1,1,1,0,0,0,0],[0,1,1,1,0,0,0],[0,0,1,1,1,0,0],\
[0,0,0,1,1,1,0],[0,0,0,0,1,1,1],[0,0,0,0,0,1,1],[1,1,1,1,0,0,0],[0,1,1,1,1,0,0],\
[0,0,1,1,1,1,0],[0,0,0,1,1,1,1],[1,1,1,1,1,0,0],[0,1,1,1,1,1,0],[0,0,1,1,1,1,1],\
[1,1,1,1,1,1,0],[0,1,1,1,1,1,1],[1,1,1,1,1,1,1],[1,1,0,1,1,1,0],[1,1,0,0,1,1,1],\
[1,1,0,0,0,1,1],[1,1,0,1,1,1,1],[1,1,1,0,1,1,1],[1,1,1,0,0,1,1],[1,1,1,1,0,1,1],\
[0,1,1,1,0,1,1]]
def can_follow(t):
height = len(t)
validCols = first_col(height)
templateCol = [0 for i in range(height)]
for i in range(height):
if t[i] in [1,2]:
templateCol[i] = 1
useCols = []
for col in validCols:
keepCol = True
for i in range(height):
if templateCol[i] > col[i]:
keepCol = False
if keepCol:
useCols += [col]
ret_data = []
for col in useCols:
data = [0 for i in range(height)]
for i in range(height):
if col[i] == 0:
data[i] = 0
if col[i] == 1:
data[i] = min(t[i]+1,3)
ret_data += [data]
return ret_data
def main():
height = 5
goal = 15
# we must create and initialize our recurrence matrix
matrix = [[0 for i in range(4**height)] for j in range(4**height)];
for i in range(4**height):
t = num_to_b4(i,height)
data = can_follow(t)
for col in data:
u = col
val = b4_to_num(u)
matrix[i][val] += 1
#matrix is initialized. now to set the first vector
terms = [0 for i in range(4**height)]
new_terms = [0 for i in range(4**height)]
cols = first_col(height)
for i in range(len(cols)):
for j in range(len(cols[i])):
if cols[i][j] == 1: cols[i][j] = 2
terms[b4_to_num(cols[i])] = 1
print(len(cols))
for N in range(goal-1):
for i in range(4**height):
addend = 0
for j in range(4**height):
addend += matrix[j][i]*terms[j]
new_terms[i] = addend
for i in range(4**height): terms[i] = new_terms[i]
valOpen = 0
valClosed = 0
for i in range(4**height):
valOpen += terms[i]
t = num_to_b4(i,height)
if 1 not in t:
valClosed += terms[i]
values = []
for k in range(4**height):
if terms[k] != 0:
if terms[k] not in values:
values += [terms[k]]
print("%d\t%d distinct values"%(valClosed, len(values)))
#what percentage of recursion values were wasted?
non_zero = 0
for i in range(4**height):
if terms[i] != 0: non_zero += 1
print("%d / %d values were non-zero"%(non_zero, 4**height))
if __name__ == "__main__":
main()