Homework #1 Submit the zip files on Canvas by the deadlines Solve a 17 tile 6x3 puzzle with an A* search algorithm. The characteristics of your program must include the following: a. The program takes...

Python 6x3 puzzle solve with A* search. Much of the assignment already provided.


Homework #1 Submit the zip files on Canvas by the deadlines Solve a 17 tile 6x3 puzzle with an A* search algorithm. The characteristics of your program must include the following: a. The program takes as inputs two vectors, the first one describing a start state and the second one describing a goal state. For example, the input to the program may look like: [5 15 7 8 9 11 10 3 12 0 2 13 4 14 1 6 16 17] [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 17 16] b. The output of the program must include the following items: i. TASK-3: A* algorithm using h2 heuristic (described in (e) below): 1. A sequence of State descriptions in which the first state is the start (or the goal) state and the last state is the goal (or the start) state as obtained by the A* algorithm using the h2 heuristic (described below). Show the details of each state description including the ID’s, g(n), h(n) and f(n) values. 2. Length of the path between the start and the goal state in terms of the number of moves; the count of nodes added to the Open List during the search process; and the count of nodes added to the Closed List during the search process (A* Search using heuristic h2). c. The heuristic function h2 for the A* search is as follows: The estimated cost of taking a board B to the goal state G is the sum of the smallest number of moves for each tile, that is not at its final location, to reach its final location as required by G. d. Make sure that your program has the provision to suspend the search process if a solution has not been found after significant resources (time or memory) have been exhausted. The following items, bundled in a single zip file, must be submitted on Blackboard in response to this assignment: a. Source code file for your program, named ’SourceCodeFile’.___ Your program must be written in one of these three languages: JAVA, PYTHON, or C++. b. A README.pdf file listing the command line instructions needed for (i) compiling your program, and (ii) executing your program with two 1X20 vectors as inputs. c. Output of your program obtained for the following two cases, included in a file named:

.OutPutFile.pdf: i. [1 13 3 5 6 9 11 0 8 12 14 10 7 16 15 4 17 2] [1 13 3 5 6 9 11 14 8 12 16 10 7 17 15 0 4 2] ii. [1 13 3 5 17 9 11 0 8 12 14 10 7 16 15 4 6 2] [5 1 3 13 17 9 11 0 8 12 14 10 7 16 15 4 6 2] The following code is an A* search for 6x3 puzzle. Modify the search heuristic based on the previous requirements. from copy import deepcopy import numpy as np import time # takes the input of current states and evaluates the best path to goal state def bestsolution(state): bs = np.array([], int).reshape(-1, 18) c = len(state) - 1 while c != -1: bs = np.insert(bs, 0, state[c]['puzzle'], 0) c = (state[c]['parent']) return bs.reshape(-1, 6, 3) # Checks iteration, whether it has been previously traversed or not. def all(checkarray): set = [] for it in set: for checkarray in it: return 1 else: return 0 # Calculates the number of misplaced tiles in the current state as compared to the goal state def misplaced_tiles(puzzle, goal): mscost = np.sum(puzzle != goal) - 1 return mscost if mscost > 0 else 0 # Finds coordinates of each of goal or initial state values def coordinates(puzzle): pos = np.array(range(18)) for p, q in enumerate(puzzle): pos[q] = p return pos # start of 17 puzzle evaluation, using h1 heuristic def evaluate_misplaced(puzzle, goal): steps = np.array([('up', [0, 1, 2], -3), ('down', [15, 16, 17], 3), ('left', [0, 3, 6, 9, 12, 15], -1), ('right', [2, 5, 8, 11, 14, 17], 1)], dtype=[('move', str, 1), ('position', list), ('head', int)]) # 0 1 2 # 3 4 5 # 6 7 8 # 9 10 11 # 12 13 14 # 15 16 17 dtstate = [('puzzle', list), ('parent', int), ('gn', int), ('hn', int)] totalCost = coordinates(goal) p = -1 gn = 0 hn = misplaced_tiles(coordinates(puzzle), totalCost) state = np.array([(puzzle, p, gn, hn)], dtstate) dtprio = [('position', int), ('fn', int)] prio = np.array([(0, hn)], dtprio) while 1: prio = np.sort(prio, kind='mergesort', order=['fn', 'position']) position, fn = prio[0] prio = np.delete(prio, 0, 0) puzzle, p, gn, hn = state[position] puzzle = np.array(puzzle) blank = int(np.where(puzzle == 0)[0]) gn = gn + 1 c = 1 start_time = time.time() for s in steps: c = c + 1 if blank not in s['position']: open_state = deepcopy(puzzle) open_state[blank], open_state[blank + s['head']] = open_state[blank + s['head']], open_state[blank] if ~(np.all(list(state['puzzle']) == open_state, 1)).any(): end_time = time.time() if ((end_time - start_time) > 2): print(" The 17 puzzle is unsolvable \n") break hn = misplaced_tiles(coordinates(open_state), totalCost) q = np.array([(open_state, position, gn, hn)], dtstate) state = np.append(state, q, 0) fn = gn + hn q = np.array([(len(state) - 1, fn)], dtprio) prio = np.append(prio, q, 0) if np.array_equal(open_state, goal): print(' The 17 puzzle is solvable \n') return state, len(prio) return state, len(prio) puzzle = [] print(" Input values from 0-17 for start state ") for i in range(0, 18): x = int(input("Enter values :")) puzzle.append(x) goal = [] print(" Input values from 0-17 for goal state ") for i in range(0, 18): x = int(input("Enter values :")) goal.append(x) state, visited = evaluate_misplaced(puzzle, goal) bestpath = bestsolution(state) print(str(bestpath).replace('[', ' ').replace(']', '')) totalmoves = len(bestpath) - 1 print('Steps to reach goal:', totalmoves) visit = len(state) - visited print('Total nodes visited: ', visit, "\n") print('Total generated:', len(state))