# Scaled up puzzles

Our implmentation of the 8-puzzle game is made to accept any 2D puzzle shape so let's see how it performs when we scale up the puzzles. Let's generate 3x3 puzzle, a 4x4 puzzle, a 5x5 puzzle, a 6x6 puzzle and try searching for a solution. We will not bother trying to perform uniform cost search on 5x5 as it could take more RAM than available on our local machines.



```python
import numpy as np
from tqdm import tqdm
import time
import matplotlib.pyplot as plt
import copy
import math

from board import Board
from node import Node
import search
import heuristics
```

### Let's create a function to run any puzzle on any algorithm with a specified timeout

we will choose manhattan distance as the heuristic because our previous [analysis](https://github.com/ribal-aladeeb/state-space-search/blob/main/analysis.ipynb) has demonstrated that it is on average our fasted heuristic.


```python
def search_solution(puzzle, algo, timeout=60, heuristic_func=heuristics.manhattan_distance):
    print(f'Puzzle {puzzle.shape[0]}x{puzzle.shape[1]}:')
    print(puzzle)
    print('Searching...')
    
    b = Board(puzzle)
    result: dict

    if algo == 'A*':
        result = search.a_star(b ,H=heuristic_func, timeout=timeout)
    
    elif algo == 'GBF':
        result = search.greedy_best_first(b ,H=heuristic_func, timeout=timeout)
    
    elif algo == 'UCS':
        result = search.uniform_cost(b, timeout=timeout)
    
    else:
        result = {'success': False, 'message': f'{algo} is not a valid argument position'}
        print(result['message'])
    
    
    if result['success']:        
        print(f'Solution found in {round(result["runtime"],2)} seconds')
    else:
        print(result['message'])

    solution_path_length = 1
    node = result['current_node']

    while node.parent != None:
        solution_path_length += 1
        node = node.parent
    
    final_msg = f'Length of solution path: {solution_path_length}\n'
    final_msg += f'Cost: {result["current_node"].total_cost}\n'

    print(final_msg)

    return result
    
```

### Let's generate some random puzzles


```python
np.random.seed(4)
puzzle3 = np.random.permutation(3*3).reshape(3,3)
puzzle4 = np.random.permutation(4*4).reshape(4,4)
puzzle5 = np.random.permutation(5*5).reshape(5,5)
puzzle6 = np.random.permutation(6*6).reshape(6,6)

puzzles = [puzzle3, puzzle4, puzzle5, puzzle6]
print('Here are the random puzzles we generated:\n')
for p in puzzles:
    print(p)
    print()
```

    Here are the random puzzles we generated:
    
    [[3 4 6]
     [2 8 0]
     [1 5 7]]
    
    [[ 5  1  0  3]
     [ 6 11 10  2]
     [ 4  8  9 15]
     [14 13  7 12]]
    
    [[12 22 18 16 11]
     [ 4  5 20 13  1]
     [15  3 17  0  7]
     [10 19  8 14  2]
     [23  6  9 24 21]]
    
    [[30 21 15  8 14 26]
     [ 1 24 29  4 19  0]
     [33  5 34  2 32 20]
     [10 13  7  6 31 28]
     [11  3 22 18 23 12]
     [16 27  9 25 35 17]]
    


#### We expect GBF to converge relatively quickly even for very large search spaces (like 6x6 puzzle)

Therefore we will run GBF on all of these puzzles first to make sure that at the very least we can get to 6x6 using GBF. If all puzzles converge within a minute, we will try A*.

## Greedy Best First Search



```python
for p in puzzles:
    result = search_solution(p, 'GBF', timeout=60)
    
    if 'timeout' in result['message']:
        print('No point of searching through larger puzzles given the current timeout\n')
        break
    
    print()
```

    Puzzle 3x3:
    [[3 4 6]
     [2 8 0]
     [1 5 7]]
    Searching...
    Solution found in 0.02 seconds
    Length of solution path: 10
    Cost: 14
    
    
    Puzzle 4x4:
    [[ 5  1  0  3]
     [ 6 11 10  2]
     [ 4  8  9 15]
     [14 13  7 12]]
    Searching...
    Solution found in 2.26 seconds
    Length of solution path: 97
    Cost: 126
    
    
    Puzzle 5x5:
    [[12 22 18 16 11]
     [ 4  5 20 13  1]
     [15  3 17  0  7]
     [10 19  8 14  2]
     [23  6  9 24 21]]
    Searching...
    Solution found in 9.87 seconds
    Length of solution path: 250
    Cost: 297
    
    
    Puzzle 6x6:
    [[30 21 15  8 14 26]
     [ 1 24 29  4 19  0]
     [33  5 34  2 32 20]
     [10 13  7  6 31 28]
     [11  3 22 18 23 12]
     [16 27  9 25 35 17]]
    Searching...
    timeout after 60 seconds
    Length of solution path: 450
    Cost: 502
    
    No point of searching through larger puzzles given the current timeout
    


### Assumption proven wrong
#### It seems like GBF times out on this 6x6 puzzle after 1 minute, we can try setting the timeout to 5 min and see if we can find a solution


```python
_ = search_solution(puzzle6, 'GBF', timeout=5*60)
```

    Puzzle 6x6:
    [[30 21 15  8 14 26]
     [ 1 24 29  4 19  0]
     [33  5 34  2 32 20]
     [10 13  7  6 31 28]
     [11  3 22 18 23 12]
     [16 27  9 25 35 17]]
    Searching...
    Solution found in 200.24 seconds
    Length of solution path: 443
    Cost: 495
    


## Given what we know about GBF and its runtimes, Let's try A*
We will first try 1 minute timeouts to see what we can achieve. Our intuition is that A* will not be able to beat the runtimes of Greedy Best First and might possibly timeout on the 5x5 puzzle.


```python
for p in puzzles:
    result = search_solution(p, 'A*', timeout=60)
    
    if 'timeout' in result['message']:
        print('No point of searching through larger puzzles given the current timeout\n')
        break

    print()
```

    Puzzle 3x3:
    [[3 4 6]
     [2 8 0]
     [1 5 7]]
    Searching...
    Solution found in 0.05 seconds
    Length of solution path: 12
    Cost: 13
    
    
    Puzzle 4x4:
    [[ 5  1  0  3]
     [ 6 11 10  2]
     [ 4  8  9 15]
     [14 13  7 12]]
    Searching...
    timeout after 60 seconds
    Length of solution path: 12
    Cost: 15
    
    No point of searching through larger puzzles given the current timeout
    


#### A* timed-out on the 4x4 puzzle, which is sort of disappointing but kind of expected. let's see if we can do better with a 5 minute timeout



```python
_ = search_solution(puzzle4, 'A*', timeout=5*60)
```

    Puzzle 4x4:
    [[ 5  1  0  3]
     [ 6 11 10  2]
     [ 4  8  9 15]
     [14 13  7 12]]
    Searching...
    timeout after 300 seconds
    Length of solution path: 19
    Cost: 25
    


### Well that was disappointing but understandable:
We are using manhattan distance as our heuristic, which is admissible. This means the range of values that H(n) can take for any n is always between 0 and H*(n). With such a small domain, the function has a theoretical limit for how informative it can be. There's no free lunch, if you want to shave through the search space you need a more informative heuristic and that most probably means sacrificing admissibility (i.e you can no longer garantee that the search would yield the smallest cost path).

#### Let's try running A with an unadmissible heuristic (the algorithm is no longer A*)
We will use [permutation inversions](https://mathworld.wolfram.com/PermutationInversion.html). In our [heuristic analysis](https://github.com/ribal-aladeeb/state-space-search/blob/main/analysis.ipynb), we found that permutation inversions are the second best heuristic in terms of average runtime (after manhattan distance of course). Maybe it is the case that with scaled up puzzles, inversions will be able to find a solution fast enough.


```python
_ = search_solution(puzzle3, 'A*', timeout=5*60)
_ = search_solution(puzzle4, 'A*', timeout=5*60)
```

    Puzzle 3x3:
    [[3 4 6]
     [2 8 0]
     [1 5 7]]
    Searching...
    Solution found in 0.05 seconds
    Length of solution path: 12
    Cost: 13
    
    Puzzle 4x4:
    [[ 5  1  0  3]
     [ 6 11 10  2]
     [ 4  8  9 15]
     [14 13  7 12]]
    Searching...
    timeout after 300 seconds
    Length of solution path: 19
    Cost: 22
    


## Now Uniform Cost Search
We have low expectation for UCS, its runtimes are orders of magnitude larger than heuristic search so we expect it will timeout on the 4x4 puzzle.


```python
for p in puzzles:
    result = search_solution(p, 'UCS', timeout=60)
    
    if 'timeout' in result['message']:
        print('No point of searching through larger puzzles given the current timeout\n')
        break

    print()
```

    Puzzle 3x3:
    [[3 4 6]
     [2 8 0]
     [1 5 7]]
    Searching...
    Solution found in 12.09 seconds
    Length of solution path: 12
    Cost: 13
    
    
    Puzzle 4x4:
    [[ 5  1  0  3]
     [ 6 11 10  2]
     [ 4  8  9 15]
     [14 13  7 12]]
    Searching...
    timeout after 60 seconds
    Length of solution path: 12
    Cost: 14
    
    No point of searching through larger puzzles given the current timeout
    


### No surprise here
Well, as expected, UCS timed-out on the 4x4 puzzle (uninformed search sucks).

# Why is it so slow
You might be wondering why adding 1 row and 1 column increases the runtime by so much. Given a puzzle with R rows and C columns, the number of possible states configurations is:

 \begin{align}(R*C)!\end{align}

That is because there are RxC tiles and the first one can assume RxC possible values, the second can take RxC-1, and so on. So the number of of possible states is the number of permutations of a vector containing RxC unique values. This is what factorial growth looks like:


```python
def states(R,C): return math.factorial(R*C)
shapes = [ 
    (2,4),
    (3,3),
    (4,4),
    (5,5),
    (6,6),
    (7,7)
]

for s in shapes:
    print(f'For a {s[0]}x{s[1]} puzzle, the number of states is: {states(*s)}')
```

    For a 2x4 puzzle, the number of states is: 40320
    For a 3x3 puzzle, the number of states is: 362880
    For a 4x4 puzzle, the number of states is: 20922789888000
    For a 5x5 puzzle, the number of states is: 15511210043330985984000000
    For a 6x6 puzzle, the number of states is: 371993326789901217467999448150835200000000
    For a 7x7 puzzle, the number of states is: 608281864034267560872252163321295376887552831379210240000000000


86f3957b167be2dd62e913b114d798bae02d083c
ipynb
Jupyter Notebook
scaling_up.ipynb
ribal-aladeeb/state-space-search
64393ab88b2693e14038359debfd021eae56677a
MIT
2020-11-18T14:48:20.000Z
2020-11-18T14:48:20.000Z
scaling_up.ipynb
ribal-aladeeb/state-space-search
64393ab88b2693e14038359debfd021eae56677a
MIT
scaling_up.ipynb
ribal-aladeeb/state-space-search
64393ab88b2693e14038359debfd021eae56677a
MIT
2020-11-18T14:20:29.000Z
2020-11-18T14:20:29.000Z
Qwen/Qwen-72B
1. YES
2. YES