Searching and the 8-tile puzzle
The 8- tile puzzle consists of an area divided into a 3×3 grid. On each grid square is a tile, expect for one square which remains empty (blank). Thus, there are eight tiles in the 8-puzzle. A tile that is next to the blank square can be moved into the empty space, leaving its previous position empty in turn. Tiles are numbered, 1 thru 8 for the 8-puzzle, so that each tile can be uniquely identified. The aim of the puzzle is to achieve a given configuration of tiles from a given (different) configuration by sliding the individual tiles around the grid as described above.
For all searches – you will query the user for the initial state and the goal state. You should make sure that the states that you are given are valid (only tiles 1-8 and a blank).
What to do:
Develop a way to store the state of the 8-tile puzzle. This will be your state description.
Develop a node data structure. In the node you will store the current state of the 8-tile puzzle, a reference to the parent node, the move that led to the current state (did the blank move Up, Right, Down, Left), and the depth. For one of the searches you will need to store the evaluation of the heuristic and the cost.
Develop a set of rules for generating children (successor states). When developing your children, create them in clockwise order (blank moves U, R, D, L) when those moves are allowed from the parent state.
Implement the breadth-first algorithm to solve the 8-tile puzzle. Your program will print-out the sequence of moves needed to solve the puzzle (go from start to finish). To avoid problems of tractability, set the maximum number of levels that can be opened by your search to 10.
Implement the breadth-first algorithm to solve the 8-tile puzzle avoiding repeated states. Your program will print-out the sequence of moves needed to solve the puzzle (go from start to finish). To avoid problems of tractability, set the maximum number of levels that can be opened by your search to 10.
Implement depth-limited search algorithm (maximum depth 10) by making a small modification to your breadth-first algorithm; have it allow repeated states. Your program will print-out the sequence of moves needed to solve the puzzle (go from start to finish).
Implement a depth-limited search algorithm (maximum depth 10) that avoids repeated states. Your program will print-out the sequence of moves needed to solve the puzzle (go from start to finish).
Implement a simple A* search. You will use the tiles out of position as your heuristic, and the depth of the node as the cost. Note that there is no maximum depth limit! Your algorithm will simply pick the best node to expand, will expand it. Your program will print-out the sequence of moves needed to solve the puzzle (go from start to finish).
Your code must have two modes: normal and verbose. In normal mode, the program will output only the final solution steps. In verbose mode, the program will output all the states it is generating in the order in which they were searched, in addition to the final solution steps. These modes are to be implemented through command line arguments (–v for verbose mode and nothing for normal)
Your analysis (This takes time!):
For all the algorithms you will perform at least 20 experiments (Example: 4 experiments where the solution can be found in 1 move, 4 experiments where the solution can be found in 2 moves, 4 experiments where the solution can be found in 4, etc.). For each algorithm you will report the average number of states expanded and average of maximum states stored, and you will compare these values to the expected theoretical performance of the algorithms (assume a branching factor of 3 for the 8-tile puzzle!)
You will prepare a report. The sections you will need:
Introduction
The introduction is one of the most important sections of a report, or, for that matter, any document because it introduces readers to the report and/or subject matter.
Topic: Early in the introduction, you need to indicate the specific topic of the report. A good way to check if you are doing this is if you can highlight the topic words in the first 3-4 lines of the introduction.
Purpose/Statement of Problem: Indicate what the purpose of the report is. What are the report’s objectives? Succinctly define the problem you are covering. You need to indicate the scope of the report—what it is intending to accomplish as well as what it is not intending to accomplish.
Overview of the contents: Indicate the main contents of the report.
Approach
Explain the design of your code. Elaborate on data structures and algorithms you used. This is also where you provide full and precise identification of all equipment and instrumentation used. You need to state the nature of the tests you ran, with reasons. For your tests, special precautions for obtaining accuracy and means for controlling conditions should be described. Remember, people need to be able to reproduce your set up. Having test cases to refer to can help. You can refer to an Appendix if you have a lot of data or code to explain.
Results
This section includes all necessary calculations and presentations of the data in graphical and/or tabular form. The uncertainty/error analysis must be performed on the basis of known or estimated instruments’ and measurement uncertainties and statistical analysis. Gross plotting may be advantageous. Remember a picture is worth 1,000 words, so sometimes figures and tables can convey information better. Label figures and tables and give them captions. Then, refer to them by the labels in the text of your report. In this section, your findings are to be summarized according to the significance to the stated objectives. Bulky details and repetitive tasks should be presented in Appendices.
Conclusion
This is where you restate the main points of your paper (please have this be fresh text, not cut-and-paste from prior sections). Mention the conclusions you drew and why. Your conclusions should be supported by specific data and results, and wherever possible compared with theory and data obtained by others. We always know how to do better after we finish a project, i.e. after we obtain an appropriate experience, please put these recommendations in your report. Recommendations should be given for any further changes or work that would better accomplish the project objectives.
References
You need to cite all your references. You need to use the IEEE format. Keep in mind that if bibliographic items are cited in text, tables, figures, or notes, the citation should be placed at the point where reference is made to them. This is referred to as in-text citation. If you do not use them, you are plagiarizing and will fail the paper.
Appendices (only if needed)
These sections are for supplemental information and for information that is either too detailed or too voluminous to fit into the body of your report. For example, if your project involves any programming, you can/should include a nicely documented and formatted listing of all the source code you wrote. The output of your code could also be included in this section. Basically – all the other things that complement your report go here.
Extra Credit (5 pts):
Your code will identify when a goal state is not possible from an initial state (of course, without running the search algorithm), and will notify the user.
What to turn in:
A zip file with your code, a readme file, your report that is neatly formatted and grammatically correct.
Your report is of equal importance to your code!