## Fifteen-puzzle, solution and time taken using the following algorithms:

• Depth First Search
• Breadth First Search
• Limited Depth First
• Iterative Limited Depth First

I modified the `eight_puzzle.py` presented by simpleai-team repo in github. And here is the modified fifteen_puzzle.py to solve our class problem.

Note, to run the code, you may:

• download the `simpleai` zip folder, or:
• `git clone https://github.com/iamaziz/simpleai.git`
• unzip it and navigate to the folder where the 15-puzzle code is:
• `cd simpleai/samples/search/`
• run the command:
• `python fifteen_puzzle.py`

### Initial cases

• ``````easy =
1-e-2-4
5-7-3-8
9-6-11-12
13-10-14-15``````
• ``````case1 =
11-5-12-14
15-2-e-9
13-7-6-1
3-10-4-8``````
• ``````case 2 =
13-5-8-3
7-1-9-4
14-10-6-15
2-12-11-e``````

### Solution analysis

• easy
• DFS: doesn't work! (it gets lost down in the search depth and never gets to try the easy neighboring moves.)
• BFS: time 0.40 sec in 8 steps.
• limited_depth_first: depth(8) 0.089 sec in 8 steps | depth(9) 0.030 sec in 10
• iterative_limited_depth_first: time: graph search 0.028 sec | tree search 0.084 sec in 8 steps.
• case 1
• DFS: doesn't work!
• BFS: doesn't work!
• limited_depth_first: doesn't work!
• iterative_limited_depth_first: doesn't work!
• case 2
• DFS: doens't work!
• BFS: doesn't work!
• limited_depth_first: doens't work!
• iterative_limited_depth_first: doesn't work!

### Solution graphed:

``breadth_first(FifteenPuzzleProblem(INITIAL), 1):``
``limited_depth_first(FifteenPuzzleProblem(INITIAL), depth_limit=8):``
``limited_depth_first(FifteenPuzzleProblem(INITIAL), depth_limit=9):``
``iterative_limited_depth_first(FifteenPuzzleProblem(INITIAL),1):``

### Solution log (samples)

``breadth_first(FifteenPuzzleProblem(INITIAL), 1):``
• ``````**** STEP NUMBER: 1 ****
Move number None
1-e-2-4
5-7-3-8
9-6-11-12
13-10-14-15
**** STEP NUMBER: 2 ****
Move number 2
1-2-e-4
5-7-3-8
9-6-11-12
13-10-14-15
**** STEP NUMBER: 3 ****
Move number 3
1-2-3-4
5-7-e-8
9-6-11-12
13-10-14-15
**** STEP NUMBER: 4 ****
Move number 7
1-2-3-4
5-e-7-8
9-6-11-12
13-10-14-15
**** STEP NUMBER: 5 ****
Move number 6
1-2-3-4
5-6-7-8
9-e-11-12
13-10-14-15
**** STEP NUMBER: 6 ****
Move number 10
1-2-3-4
5-6-7-8
9-10-11-12
13-e-14-15
**** STEP NUMBER: 7 ****
Move number 14
1-2-3-4
5-6-7-8
9-10-11-12
13-14-e-15
**** STEP NUMBER: 8 ****
Move number 15
1-2-3-4
5-6-7-8
9-10-11-12
13-14-15-e

time taken:  0.124543905258``````
``limited_depth_first(FifteenPuzzleProblem(INITIAL), depth_limit=8):``
• ``````**** STEP NUMBER: 1 ****
Move number None
1-e-2-4
5-7-3-8
9-6-11-12
13-10-14-15
**** STEP NUMBER: 2 ****
Move number 2
1-2-e-4
5-7-3-8
9-6-11-12
13-10-14-15
**** STEP NUMBER: 3 ****
Move number 3
1-2-3-4
5-7-e-8
9-6-11-12
13-10-14-15
**** STEP NUMBER: 4 ****
Move number 7
1-2-3-4
5-e-7-8
9-6-11-12
13-10-14-15
**** STEP NUMBER: 5 ****
Move number 6
1-2-3-4
5-6-7-8
9-e-11-12
13-10-14-15
**** STEP NUMBER: 6 ****
Move number 10
1-2-3-4
5-6-7-8
9-10-11-12
13-e-14-15
**** STEP NUMBER: 7 ****
Move number 14
1-2-3-4
5-6-7-8
9-10-11-12
13-14-e-15
**** STEP NUMBER: 8 ****
Move number 15
1-2-3-4
5-6-7-8
9-10-11-12
13-14-15-e

time taken:  0.0886759757996``````
``iterative_limited_depth_first(FifteenPuzzleProblem(INITIAL),1):``
• ``````**** STEP NUMBER: 1 ****
Move number None
1-e-2-4
5-7-3-8
9-6-11-12
13-10-14-15
**** STEP NUMBER: 2 ****
Move number 2
1-2-e-4
5-7-3-8
9-6-11-12
13-10-14-15
**** STEP NUMBER: 3 ****
Move number 3
1-2-3-4
5-7-e-8
9-6-11-12
13-10-14-15
**** STEP NUMBER: 4 ****
Move number 7
1-2-3-4
5-e-7-8
9-6-11-12
13-10-14-15
**** STEP NUMBER: 5 ****
Move number 6
1-2-3-4
5-6-7-8
9-e-11-12
13-10-14-15
**** STEP NUMBER: 6 ****
Move number 10
1-2-3-4
5-6-7-8
9-10-11-12
13-e-14-15
**** STEP NUMBER: 7 ****
Move number 14
1-2-3-4
5-6-7-8
9-10-11-12
13-14-e-15
**** STEP NUMBER: 8 ****
Move number 15
1-2-3-4
5-6-7-8
9-10-11-12
13-14-15-e

time taken:  0.0282061100006``````