Assignment 1_ 8-puzzle problem

1. Description
The 8-puzzle problem is a puzzle played on a 3-by-3 grid with 8 square blocks labeled 1 through 8 and a blank square. Your goal is to rearrange the blocks so that they are in order, using as few moves as possible. The legal actions include sliding blocks horizontally or vertically into the blank square. The initial state can be any arrangement of the blocks. In this assignment, the final state is always: ----------- | | 1 | 2 | ----------- | 3 | 4 | 5 | ----------- | 6 | 7 | 8 | -----------
The following shows a sequence of legal moves from an easy start board (left) to the goal board (right).

The Solution is: 'left'.
The solution must be a sequence of moves/actions. You must display it both visually and textually as a set of states and actions respectively (see above). Note also that your point of reference must be the blank node, which is why the solution above indicates “left” rather than “right”.
------------- | 1 | | 2 | ------------- | 3 | 4 | 5 | ------------- | 6 | 7 | 8 |
----------- | | 1 | 2 | ----------- | 3 | 4 | 5 | ----------- | 6 | 7 | 8 |
Prof. Amal Zouaq, CSI4106, F2017
2
Your program must also display the following information: the solution depth, the path cost, the number of visited nodes to reach the solution, and the time taken to obtain it. The method printResults is provided in util.py. Example: The Solution is at depth 1 The path cost is 1 Number of visited nodes: 3 The execution time is 0.0004117325215004907 seconds.
Note that not all puzzles are solvable, which means that not all initial configurations can lead to the goal by a sequence of legal moves. You will be provided with: 1- Some python code that you must complete 2- Examples of solvable and unsolvable configurations Your code will be tested with any random configuration so you must make sure that it is generic and that it can handle all possible cases.
2. Python code
You must use Python 3.6.2: https://www.python.org/downloads/
You will be provided with the following classes and packages:
Class State: to solve a problem, you must define a sub-class of the class State that redefines the methods in the state class. (COMPLETE)
Class Node: This class represents a node in a search tree. (COMPLETE)
Class EightPuzzleState: you will implement the class EightPuzzleState as a subclass of State. The skeleton is available in problems.eightpuzzle. This class must contain the successor function, the heuristics and all the methods that are dependent on the problem you are trying to solve(TO BE COMPLETED BY YOUR CODE).
Class Util: The class contains an implementation of the data structures Queue, Stack and PriorityQueue and utility methods. (TO BE COMPLETED BY YOUR CODE)
Search algorithms - Folder searchdir: this folder contains sub-folders with the following files (TO BE COMPLETED BY YOUR CODE):  breadthfirst_search.py: You must use the queue implemented in util.py  depthfirst_search.py: You must use the stack implemented in util.py  astar_search.py: You must use the priority queue implemented in util.py
Note that your search algorithms must remain independent of the particular problem to solve. Each search algorithm must take as input an initial state and return a solution node and the number of explored nodes. The class EightPuzzleState contains examples of calls to the search algorithms. This must not be modified.
Prof. Amal Zouaq, CSI4106, F2017
3
Several configurations/puzzles are available in EIGHT_PUZZLE_DATA. Some are solvable and others are not. The code that tests the solvability of a puzzle is provided.
After testing the available EIGHT_PUZZLE_DATA configurations, make sure to un-comment the randomization of the puzzles. Test your algorithms extensively.
Your code must handle exceptions such as for example an out of memory exception
Note that you do not need any additional python file to solve the problem and you must not add any other file.
3. To Do List You must submit on Brighspace a zip file named yourname1_yourname2_A1.zip containing your complete code and a report. Code You must write programs in Python that solve the problem described above using the following search methods: a. Depth-first search b. Breadth-first search c. A* search with two admissible heuristics H1 and H2
Report The report must have a front page with your names, the course and the assignment number. It must contain the following sections: 1. A description of the environment properties. Justify your answers. 2. A table that summarizes the performance of each algorithm (depth of solution, solution path cost, time, number of visited nodes, and whether it is complete and optimal) on the three same puzzles. These puzzles are: EIGHT_PUZZLE_DATA [1](trivial), EIGHT_PUZZLE_DATA [6] (medium) and EIGHT_PUZZLE_DATA [3] (harder). EIGHT_PUZZLE_DATA is defined in EightPuzzleState.py Note that A* must have a separate column for H1 and H2 and that you must obtain the details of an execution with each heuristic. 3. Heuristics a. A description of the two admissible heuristics used with A* b. A clear explanation of their admissibility c. Does one of the heuristics dominate the other? Why? 4. What is your conclusion regarding the performance of the algorithms?
Marking guidelines
1- Working and correct implementation following the guidelines 2- Good programming practices (appropriate use of classes, methods, parameters, comments, etc.) 3- Correct answers to questions and correct expected solutions
Prof. Amal Zouaq, CSI4106, F2017
4
Mark Distribution Code Problem representation (successor function, legal moves, cost, etc.)
20
DFS 15 BFS 15 A* 10 Heuristic1 5 Heuristic 2 5 Data structures in util.py 15 Report Q1 2.5 Q2 5 Q3 5 Q4 2.5 total 100