- 1 Description This Code Will Solve The Butterfly Puzle Problem The Press Of The Puzzle Slown In Figure 1 Figure 1 The 1 (246.49 KiB) Viewed 67 times
"""
Puzzle picture to label correspondence:
* Letters A, B, C, D denote butterfies with heads showing
* Letters a, b, c, d denote butterflies without heads
showing
* Letters (A,a): Orange and black (Monarch) butterfly
* Letters (B,b): Blue butterfly
* Letters (C,c): Orange and gray butterfly
* Letters (D,d): Yellow and black butterfly
"""
"""
f(T, R, I, X, E): partial placement (T,R) with pool I of puzzle
(X,E)
T: 2-dim array with non-zero entries holding tile indices
indicating placement
R: 2-dim array with non-zero entries holding rotation indices
for placed tile
I: unplaced tiles
X: dictionary of tiles
E: dictionary indicating edge alignments
"""
def f(T, R, I, X, E):
# if no tiles in I to place then puzzle is complete
if not I: return True
# p holds location of first empty position in T
p = np.array(np.where(T == 0)).T[0]
# iterate over all unplaced tiles i in I
for i in I:
# iterate over all four rotations
for j in range(1, 5):
# check if position p holds tile i with rotation j
if h(p, i, j, T, R, X, E):
# place tile i with rotation j in position p, remove from I
T[p[0],p[1]], R[p[0],p[1]] = i, j
I.remove(i)
# return True if this placement leads to a solution
if f(T, R, I, X, E): return True
# dead end: place tile back in pool I
T[p[0],p[1]], R[p[0],p[1]] = 0, 0
I.append(i)
return False
# dictionaries of four rotations of a tile x
def g(x):
return {
1 : { 1: x[0], 2: x[1], 3: x[2], 4: x[3] },
2 : { 1: x[3], 2: x[0], 3: x[1], 4: x[2] },
3 : { 1: x[2], 2: x[3], 3: x[0], 4: x[1] },
4 : { 1: x[1], 2: x[2], 3: x[3], 4: x[0] }
}
# check if tile index i with rotation index j may be placed in
position p
# i.e., check the positions neighboring p to see if the tile (if
any) aligns
def h(p, i, j, T, R, X, E):
# tile index i in rotation index j
x = g(X)[j]
# T side length
n = T.shape[0]
# edges of tile x are interpreted as follows:
# 1: north, 2: east, 3: south, 4: west
# north edge exists and a tile is present and doesn't match its
south edge
if p[0]>0 and T[p[0]-1,p[1]]:
# tile index and rotation index for tile north of p
i_n, j_n = T[p[0]-1,p[1]], R[p[0]-1,p[1]]
# fail if placed tile's north edge mismatches north tile's south
edge
if E[x[1]] != g(X[i_n])[j_n][3]: return False
# east edge exists and a tile is present and doesn't match its
west edge
if p[1] < n-1 and T[p[0],p[1]+1]:
# tile index and rotation index for tile east of p
pass
# fail if placed tile's east edge mismatches east tile's west
edge
pass
# south edge exists and a tile is present and doesn't match its
north edge
if p[0] < n-1 and T[p[0]+1,p[1]]:
# tile index and rotation index for tile south of p
pass
# fail if placed tile's south edge mismatches south tile's north
edge
pass
# west edge exists and a tile is present and doesn't match its
south edge
if p[1] > 0 and T[p[0],p[1]-1]:
# tile index and rotation index for tile north of p
pass
# fail if placed tile's west edge mismatches west tile's east
edge
pass
# no edge misalignments are present
return True
# print_puzzle(T, R, X): print the puzzle in readable format
# To do: generalize this code to print n x n puzzles
def print_puzzle(T, R, X):
n = T.shape[0]
print('-'*13)
for i in range(n):
print('| ', end='')
for j in range(n):
eN = g(X[T[i,j]])[R[i,j]][1]
print('{} |'.format(eN),end='')
print(' ', end='') if j < n-1 else print('')
print('|', end='')
for j in range(n):
eW = g(X[T[i,j]])[R[i,j]][4]
ti = T[i,j]
eE = g(X[T[i,j]])[R[i,j]][2]
print('{}{}{}|'.format(eW, ti, eE),end='')
print('', end='') if j < n-1 else print('')
print('| ', end='')
for j in range(n):
eS = g(X[T[i,j]])[R[i,j]][3]
print('{} |'.format(eS),end='')
print(' ', end='') if j < n-1 else print('')
print('-'*13)
if __name__ == "__main__":
# Five quantities for solution: T, R, I, X, E
# T: tiles: 3x3 numpy array, initalized to zero, holds tile
indices
# R: rotations: 3x3 numpy arra, initialized to zero, holds
rotation indices
# I: indices: list of tile indices not yet placed in board
# X: tile dictionary with indices as keys and sides as values
(from puzzle)
# E: edge dictionary indicating compatible edge pairs
# Initializations
n = 3
T = np.zeros((n,n), dtype=int)
R = np.zeros((n,n), dtype=int)
I = list(range(1, n**2+1))
# Tile dictionary
X = {
1: ['a','B','C','d'],
2: ['a','d','C','B'],
3: ['a','D','A','b'],
4: ['A','B','c','D'],
5: ['A','D','c','b'],
6: ['d','c','B','D'],
7: ['A','b','c','D'],
8: ['A','C','b','C'],
9: ['a','d','b','c']
}
# edge alignment dictionary
E = {
'a': 'A',
'A': 'a',
'b': 'B',
'B': 'b',
'c': 'C',
'C': 'c',
'd': 'D',
'D': 'd'
}
if f(T, R, I, X, E):
print("Solution:")
print_puzzle(T, R, X)
else: print("No solution found")
**Write code for lines with "pass" in them**
1 Description This code will solve the butterfly puzle problem. The press of the puzzle slown in Figure 1 Figure 1: The nine pieces of the butterfly puzzle. The picture pole is created by "dele, inc. http://www.b-duale.com) Each of the nine puzle pieces a square, and each side of a square shows one of aglathall-butterflies, namely, traballar body hall of one of the four lutterly types, my deange, blue, yellow, and card. , A solution to the page is a rangement of the nine pieces into 3x3 grid, stach that all butterfly Balves are aligned, i..., bedlal is made with body hall and both have have the same type. An arrangement consists of both a placement of space into the 3 x 3 grid and a rotation of that place in ce of four possibile contains. A little thought shows there are 9-96.125,814,72095 billion possille arges. It is worth writing the brute fort" approach to the solution, trying hard ducking if it is sution. Howe, one you start to run it, you will likely be waiting a long time. Bruteforce is not the best appeach for this problem. Our good approach is to se constraint satisfaction, is died in lecture. In this case, a partial con of a partial arts of the 9 pies lave Bet plancha pielus been given in Griestation. Find all possible pieces and creates for the first open position in the partial arrangement, and call "solve with each such extended partial rangement. If mo artinia is pull, tham ladiumth. May 4, 2122 Dept. of ECE 2 Starter code The lots of functies in the starter code is given below. List of variables 1. T: 2-lim mpyarry with one holding tileindes indisting plant 2. R: 2-lim mumpy array with non-zero et holding rotation indices for placed the 3. I list of placed tiles, initialized to 1,..., I 4. Is ditary of tiles with key for each tile index, and respotuling value given by a list of length 4. This list shows the edge content on the four edges of the tale in dockwise des. Note, I is a personat of the prize pics 6. E. dictionary indicating exige alignments. There are four butterfly types, and two vertly have had and body), so eight possible valus. A. b. B. , c, d, D, where the letters are the types and uppercase kowe) dotes head(body), respectively. The edge alignment in Eis simply the dictionary with eight kry, vale pairs, i.e. :A, A:A, b: Bib. Ci Cie, d:D, Did. (1) Tuo tiles with an adjacent ediye align if their exige content pair is in ie, the two butterfly labelse the same butterly type and together foem the whole tittely List of functions The Sollowing functions are defined in the code 1. (T.R.1.X.E): the main le routine. Note, I.E are in the lout. The argumes 1. representa partial solution and I love the placed tilee The variable polls the first open position (FOP) in the partial solution: it is a tuple, ay p - (p[0].p[:]), indicating the now am column of that position. After finding the metion itemte over the ti in I, where for each tile there is further itestion out the for possible orientations. Placing tile i injin piip is du by calling metion described below, to see if it is compatible. If yes, then T. an extended by cling 1.j, respectively, and i is wed from I. The extended solution is used to call f, and if this met call metus true then the "outer call returns tres, as well. Otherwise, the init call to fus fue, them the extension fails 1.jazeremoved from T.,then iis placed back in I am the outer" call return false 2. g(x): dietaries of four rotations of a tile. Here, I is a dictionary with key in the set 0.1.2.3. If you label the four side of a square, och side label a distinct string, then there are four posible stations of that square, corresponding to the rotations of o, 90°, 180, 270°. The function () returns a dictionary with lays in the set (1.2.3.4} (ench ly corresponding to the four possible rotations), and the conspeling was a diction. wwwx when rotated 3. (p. 1. j. T. R, X. E): chucka tile index iwith rotation index may be placed in position pie, check the positioniglisering p to see if the tile (if any) sligi. 4. print puzzle(T, R, X): print the puzzle of pics I with proper solution T. Discussion of the main function The main functions: May 4, 2122 Dept. of ECE Five quantities for solution: T.R.I.T.E T: tile spy array. In ta zero, balde tile indices .: rotation aupy arra, daitialized te zero, holde rotation dadices - I: adicaa: lat af tile adica not yet placed in board .: le dictionary with a way and sides a value ros puzzle) E: edge dictionary indicating compatible adge padre Initialisti Terona). dtype=) 2 - sp.zeros(..). dtype-sat) I - Sat Crangai, 3-2-13) () • Tile dictionary I- 1: t'a','1','c','d']. 4:30) ,נילי, "',יפי, יבין : 14,20) 4 de aliat dictionary 'c': "C 'c': יםי :י4י > 11 (1, 2, I, I, E): print("Slution:") priat.peale, R, X) al print(" solution found This end • 3 Initialias 3 for at ne board Initializes the tile rotation partial solution Temptym wional array Initializes the list of available to Isl...., (1.0, 1.,...,9) Initialias the tile dictionary I. i..., the edge content on each of the ninetes is derived • Initializes the edge sige diety E Your segment is to complete function. Once completed, the code should solve the pude