solve a 3*3 puzzle using AI.The assignment is to add the A star function to the given example

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

You are given the code necessary for solving simple slide puzzles, except for the general A* function.

(a) Your job is to fill in the body of the a_star function in the given a_star_slide_puzzle.py file.

The a_star function needs to know the problem's start state, the desired goal state, and an expand function that expands a given node. The expand function receives as its input the current state, the goal state and returns a list of pairs of the form: (new_state, h-score).

There is exactly one such pair for each of the possible moves in the current state, with new_state being the state resulting from that move, paired with its h-score. Note that this is not the f-score but the h-score, i.e., an (optimistic) estimate of the number of moves needed to reach the goal from the current state.

The expand function does not know g and therefore cannot compute f; this has to be done by the a_star function. Also, note that slide_expand does not (and cannot) check whether it is creating a search cycle, i.e., whether it generates a state that is identical to one of its ancestors; this has to be done by a_star as well. The given slide_expand function counts the number of mismatched tiles (excluding the empty tile) as a scoring function.

As you can see, the slide_puzzle_solver function simply calls a_star and then prints out the solution or tells you that there is no solution. There are two examples given. For now, please only try solving Example #1 as shown in the last line of the code. Puzzle states are represented by numpy arrays, with a 0 indicating the empty tile. The other tiles always have to be enumerated starting at 1.

Please add code to the a_star function so that slide_puzzle_solver can find an optimal solution for Example #1 and, in principle, for any slide puzzle. You are not allowed to modify any code outside of the a_star function.

Hints: It is best to not use recursion in a_star but rather a single loop that expands the next node, prevents any cycles in the search tree, sorts the list of open nodes by their scores, etc., until it finds a solution or determines that there is no solution. It is also a good idea to keep a list of ancestors for every node on the list, i.e., the list of states from the start that the algorithm went through in order to reach this node. When a goal state is reached, the list of ancestors for this goal node can be returned as the solution.

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of