Description

Purpose:           The purpose of this project is to make you practice and experiment with heuristic search.

 

Heuristic Search

 

Assume a variation of the 8-puzzle called 11d-puzzle.  The 11d-puzzle is identical to the 8-puzzle, except for 2 differences:

1. the board is a 3×4
2. diagonal moves into the empty tile are legal (assume it can be done on a physical board). So we have

at most 8 possible moves: UP, UP –RIGHT, RIGHT, DOWN–RIGHT, DOWN, DOWN–LEFT, LEFT, UP–LEFT.

 

The goal configuration of the 11d-puzzle is:

 

1	2	3	4
5	6	7	8
9	10	11	0

 

To represent the positions on the board, let us use the letters a to l as indicated by the superscripts below:

 

1a	2b	6c	4d
5e	9f	7g	3h
0i	10j	11k	8l

For example, in the figure on the left:

tile #1 is at position a, …

tile #6 is at position c, …

                                                                               the empty tile (denoted by the 0) is at position i…

 

Since a tile can only move into the empty position, all that is required to represent a move is to record the tile that moved.  For example, given the configuration above, the sequence of moves: [f g k] should be interpreted as:

1. move tile f DOWN–LEFT to position i (where the empty tile is)
2. (now the empty tile is at position f) move tile g LEFT to position f
3. (now the empty tile is at position g) move tile k UP to position g

 

Your task:

Implement a solution for the 11d-puzzle using the following 3 search algorithms:

1. Depth-first search (DFS)
2. Best-first search (BFS)
3. Algorithm A* (A*)

 

Ties between equivalent nodes should be broken in a clockwise direction starting with UP.  This means that equivalent moves are ordered this way:

UP >  UP –RIGHT  >  RIGHT  >  DOWN- RIGHT  >  DOWN  >  DOWN –LEFT  >  LEFT > UP–LEFT

(most preferred moves)                                                                        (least preferred moves)

 

For BFS and A*, you must experiment with 2 different heuristics h1 and h2 of your choice.  h1 and h2 should both be used with BFS and with A*.

Input:

Your program will read from the console an initial puzzle, where each tile will be represented by a unique integer (0 to 11), where the zero will denote the empty tile. The order of the tiles will follow the alphabetic order of the tile names (a b c d e f g h i j k l). For example, the puzzle:

 

1	0	3	7
5	2	6	4
9	10	11	8

 

will be represented as:  1 0 3 7 5 2 6 4 9 10 11 8

 

Output:

Given an initial puzzle (from the console), your program must output its results in the 5 text files below:

 

1. txt:

A trace of the puzzle configuration after each move on the final solution found by depth-first search.   First, you display the initial configuration preceded by a 0 (zero), then for each move in the solution path, you should display the move followed by the new configuration in list format, one puzzle per line.  For example, if your final solution path is:

[c d h l k g c d b f k l] 

Then puzzleDFS.txt should contain:

 

0 [1, 0, 3, 7, 5, 2, 6, 4, 9, 10, 11, 8] // 0 then the initial configuration c [1, 3, 0, 7, 5, 2, 6, 4, 9, 10, 11, 8] // move c, then configuration after move c d [1, 3, 7, 0, 5, 2, 6, 4, 9, 10, 11, 8] // move d, then configuration after move d h [1, 3, 7, 4, 5, 2, 6, 0, 9, 10, 11, 8] // … l [1, 3, 7, 4, 5, 2, 6, 8, 9, 10, 11, 0] k [1, 3, 7, 4, 5, 2, 6, 8, 9, 10, 0, 11] g [1, 3, 7, 4, 5, 2, 0, 8, 9, 10, 6, 11] c [1, 3, 0, 4, 5, 2, 7, 8, 9, 10, 6, 11] d [1, 3, 4, 0, 5, 2, 7, 8, 9, 10, 6, 11] b [1, 0, 3, 4, 5, 2, 7, 8, 9, 10, 6, 11] f [1, 2, 3, 4, 5, 0, 7, 8, 9, 10, 6, 11] k [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 11] l [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0] 

 

Please follow the format indicated above.

 

2. puzzleBFS-h1.txt: same as above but for BFS with heuristic h1.
3. puzzleBFS-h2.txt: same as above but for BFS with heuristic h2.
4. puzzleAs-h1.txt: same as above but for A* with heuristic h1. puzzleAs-h2.txt: same as above but for A* with heuristic h2.

 

Programming Environment:

You can use Java, C, C++, Python or Prolog.  If you wish to use another language, please check with me first.

 

Experimentations:

Note that this is a mini-project, not an assignment.  The difference is that it is open-ended and in addition to the required work stated above, you are expected to be creative, perform additional experimentations and analyse the results of your experimentations.  Examples of experimentations include trying different heuristics, modifying the size or rules of the puzzle,…

 

The Code:

Submit all files necessary to run your code in addition to a README.txt which will contain specific and complete instructions how to run your program on the desktops in the computer labs.  If the instructions in your readme file do not work or are incomplete, you will not be given the benefit of the doubt.