Topics Covered 1. Graphs 2. Graph Traversals and Search Algorithms (DFS, BFS, IDS, etc.) 3. Numpy ndarrays, Permutations

[answerhappygod]

Topics Covered 1 Graphs 2 Graph Traversals And Search Algorithms Dfs Bfs Ids Etc 3 Numpy Ndarrays Permutations 1 (69.11 KiB) Viewed 26 times

Topics Covered 1 Graphs 2 Graph Traversals And Search Algorithms Dfs Bfs Ids Etc 3 Numpy Ndarrays Permutations 2 (33.25 KiB) Viewed 26 times

Topics Covered 1 Graphs 2 Graph Traversals And Search Algorithms Dfs Bfs Ids Etc 3 Numpy Ndarrays Permutations 3 (43.86 KiB) Viewed 26 times

Topics Covered 1. Graphs 2. Graph Traversals and Search Algorithms (DFS, BFS, IDS, etc.) 3. Numpy ndarrays, Permutations, Transpositions, and Linear Algebra 4. Optimization and Game Al 5. Event-Driven Programming Instructions Fifteen Puzzle Objective: practicing with classes, modules, graph ADT, graph traversals, optimization techniques, game Al, and event-driven programming Supplementary Material: 15 puzzle - Wikipedia, Taxicab geometry - Wikipedia, TkDocs Tutorial - Basic Widgets Description In this assignment you will write a program that emulates a game Fifteen, a sliding puzzle made of 15 tiles. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 The tiles are arranged in the 4 x 4 layout made of 4 rows and 4 columns. Since there are 16 spaces (positions) and only 15 tiles, one space is empty. Your program should generate a GUI window with the game layout that is controllable by the mouse button clicks. The user can play the game (or solve the puzzle) by selecting an adjacent tile to the empty space and moving it to the empty space position: up, down, left, or right depending on the tile location. By default, the solution to the Fifteen puzzle is positioning of all tiles in order from left to right and top to the bottom as shown in the picture above. Optionally, the user may change the default final solution to any possible arrangements, for example, the arrangement in the reverse order from 15 to 1. It is worth to mention that there are 16! possible permutations of 15 tiles and an empty space; however, only a half of them is solvable given the constrains of the tile movements. This property is known as an invariant of the puzzle that is unchanged after puzzle transformations and is due to the parity of the permutation and the parity of the Manhattan (taxicab) distance. So, a half of 16! permutations is unsolvable for given initial conditions! Your program should generate only correct (allowed) permutations that preserve the invariant. It can be achieved if only correct transformations are applied to the tiles such as only an empty space can be exchanged with its neighbors. However, the problem arises if the user enters the final solution of the puzzle that cannot be reachable (this property of the game is optional). You can find the puzzle invariant by calculating the parity of a permutation: if the empty square is in the lower right corner as shown on the picture above, then the puzzle is solvable if and only if the permutation is even. Even permutations have a sign +1 and odd permutations have a sign-1 that are calculated by the following formula: sign = (-1) N(s)

class Vertex:: definit__(self, key): self.id = key self.connected To = {} self.color='white' def addNeighbor(self, nbr,weight=0): self.connected To [nbr] = weight def_str_(self): * return str(self.id) + connected To: + str{[x.id for x in self.connectedTo]) def getConnections (self): return self.connected To.keys () def getId(self): return self.id def getWeight (self, nbr): return self.connected To [nbr] class Graph: definit_(self): self.vertList = {} self.numVertices = 0 def addVertex(self,key): pass def getVertex(self,n): pass def _contains (self,n): return n in self.vertList def addEdge(self, f, t, weight=0): pass def getVertices(self): return self.vertlist.keys() defiter (self): return iter(self.vertList.values()) def breadth_first_search(self, s): pass def depth_first_search(self): pass def DFS (self, vid, path): pass

class Fifteen: # create a vector (ndarray) of tiles and the layout of tiles positions (a graph) #tiles are numbered 1-15, the last tile is (an empty space) def _init__(self, size=4): self.tiles = np.array( [i for i in range(1,size++2)] + [0]) pass #draw the layout with tiles: #+++++ # | 1 | 2 | 3 | 41 #+-+-- # | 5 | 6 | 7 | 8 | #9 110 111 112 | #+-+ # 113 114 115 | #+-+- def draw(self): pass # return a string representation of the vector of tiles as a 2d array 1 2 3 4 # # 5 6 7 8 9 10 11 12 13 14 15 # def_str_(self): pass # exchange i-tile with j-tile, tiles are numbered 1-15, the last tile ise (empty space) # the exchange can be done (not required) using a dot product of the vector of tiles and the matrix of # the corresponding transformation (vector by matrix multiplication) # can (not required) return the dot product def transpose(self, i, j): pass # checks if the move is valid: one of the tiles is and another tile is its neighbor def is_valid_move(self, move): pass # update the vector of tiles # if the move is valid assign the vector to the return of transpose() or call transpose def update(self, move): pass # shuffle tiles. def shuffle(self, moves = 100): pass # verify if the puzzle is solved def is solved(self): pass # verify if the puzzle is solvable (optional) def is solvable(self): pass # solve the puzzle def solve(self): pass -+#