CS3243 Project 1- An Evaluation of Uninformed and Informed Solution

Search Algorithms on the k-puzzle Problem
Objectives
The aims of this project are to:
1. Become familiar with the implementation of uninformed and informed search algorithms through their application on a simple problem.
2. Analyse the correctness and complexity of the aforementioned search algorithms.
3. Design experiments to further empirically evaluate the aforementioned search algorithms.
4. Discuss the effectiveness of the implemented algorithms on the k-puzzle problem.

Introduction: The k-puzzle Problem
The k-puzzle problem is a generic version of the 8-puzzle problem, which is described in detail in the AIMA text.
2 3 6
1 5 8
4 7
Figure 1: An example of an initial state for the 8-puzzle problem.
In the 8-puzzle version, you are given a 3×3 grid, where all but one grid cell contains a unique number between 1 and 8 (inclusive), and the last cell is left empty. An example of this is depicted in Figure 1.
The goal is to move the cells such that all the cells are ordered. More specifically, for the 8-puzzle to be solved, all the cells must be identical to the positions depicted in Figure 2.
1 2 3
4 5 6
7 8
Figure 2: An example of an initial state for the 8-puzzle problem.
8 ↓ 6 ↓ 3 → 2 → 1 ↑ 4 ↑ 7 ← 8 ←
For the generic k-puzzle, you are to assume that the grid has dimensions n×n, where k = n2 −1, n≥ 2 and n∈Z.

General Project Requirements
The general project requirements are as follows:
• Group size: 3-4 students
• Submission Platform: LumiNUS > CS3243 Module > Project Submission Folder
• Submission Format: One standard (non-encrypted) zip file containing all necessary project files
As to the specific project requirements, you must complete and submit the following:
1. An implementation of ONE uninformed search algorithm described in Chapter 3.4 of the AIMA Text.
2. An implementation of ONE informed search algorithm described in Chapter 3.5 of the AIMA Text.
3. Design of THREE admissible heuristics for the chosen informed search algorithm in Point
2.
4. Design of experiments to empirically evaluate the 1 uninformed search algorithm and chosen informed search algorithm with each of the three heuristics.
5. A 2-page report that describes the following:
a Problem specification
b Technical analysis of the selected algorithms and heuristics
c Experimental setup to evaluate the selected algorithms and heuristics
d Results and Discussion

Submission Specifications
Your submissions should contain the following:
• FIVE Python code files (one for uninformed search, three for informed search with 1 heuristic each, and one for the experiment), and
• ONE report in PDF format.
The files mentioned above should be named:
• CS3243P1XX1.py - for your uninformed search implementation
• CS3243P1XX2.py - for your informed search implementation using the 1st heuristic
• CS3243P1XX3.py - for your informed search implementation using the 2nd heuristic
• CS3243P1XX4.py - for your informed search implementation using the 3rd heuristic
• CS3243P1XX5.py - for your empirical experiments
• CS3243P1XX.pdf - for your report
Input
The input is provided in a text file, which will contain n lines, with n integers on each line. Each such integer included will correspond to one integer from the sequence 0 to (n2 − 1), with 0 representing the empty cell. This will correspond to the initial state of the k-puzzle. For example, the initial state given in Figure 1 would be encoded in the text file as follows:
2 3 6
1 5 8
4 7 0
Output
The output of your code should correspond to a List containing the strings: ’LEFT’, ’RIGHT’, ’UP’, ’DOWN’, and ’UNSOLVABLE’. For example, the output specified as the solution to the initial state given in Figure 1, would be: [’DOWN’, ’DOWN’, ’RIGHT’, ’RIGHT’, ’UP’, ’UP’, ’LEFT’, ’LEFT’].
If the given puzzle (input) is not solvable, your output should be [’UNSOLVABLE’]. Else, you should output the actions of each step required to solve the puzzle, where each step here corresponds to the movement of the non-empty cell (i.e., the non-zero cell).
Code
• You are required to implement ONE informed and ONE uninformed search algorithm, with THREE admissible heuristics chosen for the latter.
• You must also design and implement experiments to empirically evaluate your search implementations.
• Your code must be executable; if your program cannot be executed, you will get 0 for the code components.
• Your code should be correct. It must follow the given input and output specifications and pass all test cases. It must run in reasonable time.
Report
Your report should at least be 2 pages long, and no longer than 4 pages.
It must include the following sections:
1. Problem specification
2. Technical analysis
3. Experimental setup
4. Results and Discussion
You must submit the report in PDF format.

Marking Rubrics
The following rubrics will be applied to your submission.
Evaluated
1 Uninformed search implementation (1 algorithm)
• Correct implementation based on algorithm specified
• Runs in reasonable time and passes all test cases
• Implementation must correspond to the description given in the report Code
1 Informed search implementation (1 algorithm including the 3 heuristics)
• Correct implementation based on algorithm specified with the 3 heuristics implemented as specified
• Runs in reasonable time and passes all test cases
• Implementation must correspond to the description given in the report Code

1 Implementation of experimental setup
• Experimental setup implemented as specified
• Generates performance results for all implemented algorithms and heuristics
• Experiments should correspond to the description given in the report Code
1 Problem specification
• A suitable representation should be specified to define the problem
• It should facilitate the formulation of search-based solutions Report
1 Technical Analysis (1)
• Each algorithm implemented should be analysed for correctness and complexity Report
3 Technical Analysis (2)
• Your heuristic must be provably admissible, or (preferably) consistent. In either case you must formally prove this property. Note that consistency implies admissibility but not the other way around. Thus, if you show admissibility, you should provide a (preferably simple) counterexample where your heuristic violates consistency.
• The 3 heuristics should be distinct and non-trivial; for example, your heuristic should not be a constant, a simple linear transformation of other heuristics, or any simple function of another heuristic like a square root of another
• 1 mark per heuristic Report
1 Experimental Setup
• The goal of the experiments should be defined (including a rationale for the chosen algorithms and heuristics), and in particular the metrics designed/used should be justified
1 Results and Discussion
• A concise discussion comparing the theoretical analysis and empirical results should be given to elucidate the effectiveness and efficiency of your implementations Report
This project is worth 10% of your module grade.