Answer to Question #167927 in Python for M ABu sufyan

Question

Consider the 2021 puzzle, which is a lot like the 15-puzzle we talked about in class, but: (1) it’s played on a 4x5 board, (2) it has 20 tiles, so that there are no empty spaces on the board, (3) instead of moving a single tile into an open space, a move in this puzzle consists of either (a) sliding an entire row of tiles left or right, with the left- or right-most tile “wrapping around” to the other side of the board, or (b) sliding an entire column of the puzzle up or down, with the top- or bottom-most tile “wrapping around.” However, each given row or column can only be slid in a certain way: the first and third rows can only be slid left; the second and fourth rows can only be slid right; the first, third, and fifth columns can only be slid up; and the second and fourth columns can only be slid down. For example, here is a sequence of two moves on such a puzzle: 2 1 2 3 4 5 1 2 3 4 5 1 17 3 4 5 6 7 8 9 10 → 10 6 7 8 9 → 10 2 7 8 9 11 12 13 14 15 11 12 13 14 15 11 6 13 14 15 16 17 18 19 20 16 17 18 19 20 16 12 18 19 20 The goal of the puzzle is to find a short sequence of moves that restores the canonical configuration (on the left above) given an initial board configuration. We’ve provided skeleton code to get you started. You can run the skeleton code on the command line: python3 solver2021.py [input-board-filename] where input-board-filename is a text file containing a board configuration (we have provided an example). You’ll need to complete the function called solve(), which should return a list of valid moves, each of which is encoded as a letter L, R, U, or D for left, right, up, or down, respectively, and a row or column number (indexed beginning at 1). (For instance, the moves in the picture above would be R2 D2.) The initial code does not work correctly. Using this code as a starting point, implement a fast version, using A* search with a suitable heuristic function that guarantees finding a solution in as few moves as possible. Try to make your code as fast as possible even for difficult boards, although it is not necessarily possible to write code that will be able to quickly solve all puzzles. In addition to doing your own testing, it is important that you test your program on the SICE Linux servers to ensure that we will be able to run it and grade it accurately

Answer 1

class State:

def _init_(self, state, parent, move, depth, cost, key):

self.state = state

self.parent = parent

self.move = move

self.depth = depth

self.cost = cost

self.key = key

if self.state:

chr= [str(e) for e in self.state]
self.map = ''.join(chr)

def _eq_(self, other):
return self.map == other.map

def _lt_(self, other):
return self.map < other.map

target_state = [0, 1, 2, 3, 4, 5, 6, 7, 8]
target = State
initial_state = list()
board_len = 0
board_side = 0

nodes_expanded = 0
maxdepth = 0
fs = 0

moves = list()
costs = set()

def bfs(puzzle):
  

   global fs, target, maxdepth
  

   search, queue = set(), deque([State(puzzle, None, None, 0, 0, 0)])
  

   while queue:
  

   node = queue.popleft()
  

   search.add(node.map)
  

   if node.state == goal_state:
   target = node
   return queue
  

   near = expand(node)
  

   for near in neighbors:
   if near.map not in search:
   queue.append(near)
   explored.add(near.map)
  

   if near.depth > maxdepth:
maxdepth += 1
  

   if len(queue) > fs:
   fs = len(queue)
  

  

   def dfs(puzzle):
  

   global fs, target, depth
  

   search, stack = set(), list([State(puzzle, None, None, 0, 0, 0)])
  

   while stack:
  

   node = stack.pop()
  

   search.add(node.map)
  

   if node.state == goal_state:
   target= node
   return stack
  

   neighbors = reversed(expand(node))
  

   for near in neighbors:
   if near.map not in search:
   stack.append(near)
   search.add(near.map)
  

   if near.depth > maxdepth:
   depth += 1
  

   if len(stack) > fs:
   fs = len(stack)