## (15 puzzle) solution and time taken using:

• Depth 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.

### 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!

### Results log

``````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
``````

### Results 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):
``````