Number of opening formations

Want to calculate something or share your results?
Post Reply
aradesh
Posts: 87
Joined: Sat Aug 29, 2009 3:37 pm

Number of opening formations

Post by aradesh »

Warning: The contents of this first post is wrong, see later posts.

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
I wrote a python program which computes these and seems to work well up to 6xn boards using self-generated recursion relations. Beyond 6 it would be extremely slow and use up enormous amounts of memory as it is at the moment. Here is the data I have up to 6x6:

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
Notice that for 1xn and 2xn boards, it is 2F(n) where F(n) is the fibonacci sequence, and for 3xn it is 4F(n)^2.

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
we have a 3x5 board where the area under mine-influence are the #'s and the opening is the -'s. To this we would associate the numbers (3,3,2). A 3 means that we have had 3 (or more) #'s in a row, the 2 means we've had 2 #'s in a row. I also consider boards with 1's:

Code: Select all

. . #     ... 1
. . #     ... 1
. . .     ... 0
This 3x3 board is clearly not a valid configuration, but we need these to help counting the 3x4 board. When we wish to compute the total configurations, we just ignore all of those containing any 1's. The program counts boards with certain end-signatures and then uses these to work out how many boards of certain end-signatures for the next sized board there are.
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()
Last edited by aradesh on Fri Jul 11, 2014 4:25 pm, edited 1 time in total.
aradesh
Posts: 87
Joined: Sat Aug 29, 2009 3:37 pm

Re: Number of opening formations

Post by aradesh »

Just an update. I found out that the method I employed in the last program was flawed, but I've written a new program for the task and it turns out the number of openings is this OEIS sequence: http://oeis.org/A217982 where it has been calculated up to 12x12.
I noticed there was something wrong when I saw that my table started off like that above sequence, but diverged at 4x4 so I tried to verify 4x4 by hand and I realized that the total of 4x4 openings must be 2 (mod 4) and I had a number divisible by 4.

Here is some data:

Code: Select all

1x1   2
2x2   2
3x3   16
4x4   98
5x5   1942
6x6   54504
7x7   3375350
8x8   368335390
9x9   79138501972
10x10 31734389399738
11x11 24359808536352098
12x12 35370314418915229140
Last edited by aradesh on Fri Jul 11, 2014 4:13 pm, edited 3 times in total.
aradesh
Posts: 87
Joined: Sat Aug 29, 2009 3:37 pm

Re: Number of opening formations

Post by aradesh »

Here is the code of my new program. It can handle up to about nx8 now as it doesn't have a huge inefficient matrix which is 0 almost everywhere. I can think of a way to make this program much more efficient and be able to generate the recursion rule table a lot faster, which may be able to get me up to 12x12 like the person who put the sequence on OEIS, but beyond that I can imagine the table will become so huge that limitation of RAM will become an issue, unless I can think of a way to separate all of the cases into classes.

Code: Select all

def single_col(h):
	cols = [[] for i in range(h)]
	cols0 = [[] for i in range(h)]
	cols1 = [[] for i in range(h)]
	cols[0] = [[0],[1]]
	cols[1] = [[0,0],[1,1]]
	cols0[0] = [[0]]
	cols0[1] = [[0,0]]
	cols1[0] = [[1]]
	cols1[1] = [[1,1]]
	for i in range(2,h):
		for col in cols1[i-1]:
			cols1[i] += [col + [1]]
		for col in cols0[i-2]:
			cols1[i] += [col + [1,1]]
			
		for col in cols0[i-1]:
			cols0[i] += [col + [0]]
		for col in cols1[i-2]:
			cols0[i] += [col + [1,0]]
	return cols0[-1] + cols1[-1]
	
def covered_mines(board,width,height):
	mine_board = [[0 for n in range(height)] for m in range(width+2)]
	for m in range(-1,width+1):
		for n in range(height):
			all_1 = True

			for u in range(max(m-1,0),min(m+1,width-1)+1):
				for v in range(max(n-1,0), min(n+1,height-1)+1):
					if board[u][v] != 1:
						all_1 = False
			if all_1: mine_board[m+1][n] = 1
	return mine_board
	
def extend_influence(board,width,height):
	for m in range(width):
		for n in range(height):
			if board[m][n] == 0:
				for u in range(max(m-1,0),min(m+1,width-1)+1):
					for v in range(max(n-1,0),min(n+1,height-1)+1):
						if board[u][v] == 1:
							board[m][n] = 2
							
	#change the 2's to 1's
	for m in range(width):
		for n in range(height):
			if board[m][n] == 2:
				board[m][n] = 1
			

def find_valid_triples(h):
	cols = single_col(h)
	N = len(cols)
	
	valid_triples = []
	closed_ends = []
	half_closed = []
	lookup_table = [-1 for i in range(N**3)]
	
	count = 0
	
	for i in range(N):
		for j in range(N):
			for k in range(N):
				test_board = [cols[i],cols[j],cols[k]]
				mine_board = [[0 for m in range(h)] for n in range(5)]
				mine_board2 = [[0 for m in range(h)] for n in range(5)]
				mine_board3 = [[0 for m in range(h)] for n in range(5)]
				
				mine_board = covered_mines(test_board,3,h)
				for m in range(h):
					for n in range(4):
						mine_board2[n][m] = mine_board[n][m]
				for m in range(h):
					for n in range(1,4):
						mine_board3[n][m] = mine_board[n][m]
				
				extend_influence(mine_board,5,h)
				extend_influence(mine_board2,5,h)
				extend_influence(mine_board3,5,h)
							
				if mine_board[1:4] == test_board:
					valid_triples += [i*N*N + j*N + k]
					lookup_table[i*N*N+j*N+k] = count
					count += 1
				if mine_board2[1:4] == test_board:
					half_closed += [i*N*N + j*N + k]
				if mine_board3[1:4] == test_board:
					closed_ends += [i*N*N + j*N + k]
					
	return valid_triples,closed_ends,half_closed, lookup_table

def create_recurrsion_table(triple_boards,lookup_table, h):
	cols = single_col(h)
	N = len(cols)
	num_boards = len(triple_boards)
	table = [[] for i in range(num_boards)]
	for iter in range(num_boards):
		board_val = triple_boards[iter]
		k = board_val%N
		board_val //= N
		j = (board_val)%N
		board_val //= N
		i = (board_val)%N
		for x in range(N):
			board = [cols[x],cols[i],cols[j],cols[k]]
			mine_board = covered_mines(board,4,h)
			extend_influence(mine_board,6,h)
			if mine_board[1:5] == board:
				#we must add the position of x*N*N + i*N + j to the table
				table[iter] += [lookup_table[x*N*N + i*N + j]]
	return table
	

def main():
	h = 6
	valid_triples, closed_ends,half_closed, lookup_table = find_valid_triples(h)
	rule_table = create_recurrsion_table(valid_triples,lookup_table, h)
	recurr_data = [0 for i in range(len(valid_triples))]
	recurr_data2 = [0 for i in range(len(valid_triples))]
	N = len(single_col(h))
	for n in half_closed:
		k = n%N;
		n//=N
		j = n%N;
		n//=N;
		i = n%N;
		recurr_data[lookup_table[k*N*N + j*N + i]] = 1
		
	
	total = 0
	for n in half_closed:
		total += recurr_data[lookup_table[n]]
	print(total)
	
	for i in range(10):
		for j in range(len(valid_triples)):
			recurr_data2[j] = recurr_data[j]
		
		for j in range(len(valid_triples)):
			new_val = 0
			for n in rule_table[j]:
				new_val += recurr_data2[n]
			recurr_data[j] = new_val
		total = 0
		for n in half_closed:
			total += recurr_data[lookup_table[n]]
		print(total)
	

	
if __name__ == "__main__":
	main()
Post Reply