<jupyter_start><jupyter_text>The taskThe goal of this assignment is to solve the 8 Puzzle. There is a 3x3 board with 8 blocks with numbers and one empty space. Blocks can be moved in any direction if there is a space. The goal is to get from a starting layout of blocks to an ending layout of blocks.My name is *<NAME>* and I have the *assignment D*.<jupyter_code>import math<jupyter_output><empty_output><jupyter_text>StatesA state of the board will be represented as a tuple of numbers, where 0 represents the space. A state looks like this:<jupyter_code>some_state = (1, 2, 3, 4, 0, 5, 6, 7, 8)<jupyter_output><empty_output><jupyter_text>Generating new statesNew states are generated using operators - up, right, down, left. These operators take in a state and return a new state.Let's define a generic function for an operator. This function takes in a state and a tuple indicating a movement in some direction, such as (1, 0).<jupyter_code>def operator(state, direction):
    new_state = list(state)
    
    # find the space
    i = state.index(0)
    x = i % 3
    y = math.floor(i / 3)
    
    # get the block that will be moved
    x2 = x - direction[0]
    y2 = y - direction[1]
    i2 = y2 * 3 + x2
    
    # check if it is a valid move, if not, return None
    if x2 < 0 or x2 > 2 or y2 < 0 or y2 > 2:
        return None
    
    # swap the space and the block and return the new state
    new_state[i], new_state[i2] = new_state[i2], new_state[i]
    return tuple(new_state)<jupyter_output><empty_output><jupyter_text>For convenience, let's also define a helper function for printing a state.<jupyter_code>def print_state(state):
    for y in range(3):
        for x in range(3):
            i = y * 3 + x
            if state[i] > 0:
                print(state[i], '', end='')
            else:
                print('  ', end='')
        print()<jupyter_output><empty_output><jupyter_text>Now we have the generic operator function, let's make the specific functions for the 4 operators we will be using.<jupyter_code>def up(state):
    return operator(state, (0, -1))
def right(state):
    return operator(state, (1, 0))
def down(state):
    return operator(state, (0, 1))
def left(state):
    return operator(state, (-1, 0))<jupyter_output><empty_output><jupyter_text>Test it to make sure the implementation is right.<jupyter_code>print_state(some_state)
print_state(up(some_state))
print_state(right(some_state))
print_state(down(some_state))
print_state(left(some_state))<jupyter_output>1 2 3 
4 5   
6 7 8<jupyter_text>It works. It should also return None if the move is invalid.<jupyter_code>print(right((0, 1, 2, 3, 4, 5, 6, 7, 8)))<jupyter_output>None<jupyter_text>Heuristic functionsWe will use 2 heuristic functions and compare their results. The first one determines how many blocks are not in their final place. The other counts the sum of difference between the current position and the final positions of each block.<jupyter_code>def heuristic_count(state, final_state, count_space=False):
    count = 0
    
    for i in range(9):
        if state[i] == 0 and not count_space:
            # don't count the space if count_space == False
            continue
        
        if state[i] != final_state[i]:
            count += 1
    
    return count
def heuristic_sum(state, final_state, count_space=False):
    sum = 0
    
    for i in range(9):
        block = state[i]
        if block == 0 and not count_space:
            # don't count the space if count_space == False
            continue
        
        x = i % 3
        y = math.floor(i / 3)
        
        # find the block in the final state
        i2 = final_state.index(block)
        x2 = i2 % 3
        y2 = math.floor(i2 / 3)
        
        # count the difference in the positions and
        # add it to the sum
        sum += abs(x - x2)
        sum += abs(y - y2)
        
    return sum<jupyter_output><empty_output><jupyter_text>Now let's test these functions.<jupyter_code>some_state = (1, 2, 3, 6, 4, 5, 0, 8, 7)
final_state = (1, 2, 3, 4, 5, 6, 7, 8, 0)
heuristic_count(some_state, final_state)
heuristic_sum(some_state, final_state)<jupyter_output><empty_output><jupyter_text>AlgorithmIt's time to get to the algorithm. Here's how it will all work:1. Get as inputs the starting and the final state, as well as the used heuristic2. Put the starting state into a priority queue - priority is given by the heuristic3. Take the state with the lowest priority from the queue4. If this is the final state, we are done - return the moves (operators) that got us here5. Otherwise, generate all possible states we can get from this one, point them to this one, and insert the ones which weren't visited yet into the priority queue6. Jump to point 3We will use a priority queue for storing the states that are generated but have not been yet visited. We will also use a dictionary for storing the visited states.<jupyter_code>from queue import PriorityQueue<jupyter_output><empty_output><jupyter_text>Before we actually create the method that implements the algorithm mentioned above, let's do it interactively step by step. Start by defining the starting and the final states.<jupyter_code>start_state = (1, 2, 3, 4, 5, 6, 7, 8, 0)
final_state = (1, 2, 3, 4, 6, 8, 7, 5, 0)<jupyter_output><empty_output><jupyter_text>The correct solution we should get to is right, down, left, up.<jupyter_code>print_state(start_state)
print_state(up(left(down(right(start_state)))))<jupyter_output>1 2 3 
4 6 8 
7 5<jupyter_text>As mentioned, we will need a priority queue and a dictionary. The queue will store a tuple with the following attributes:- priority - determined by the heuristic function- state- list of moves how we got hereThe dictionary will just store the states that have been already generated.<jupyter_code>generated = PriorityQueue()
visited = {}<jupyter_output><empty_output><jupyter_text>First, put the starting state into the dictionary. Then, generate all possible states from the starting one.<jupyter_code>visited[start_state] = True
for op in [up, right, down, left]:
    new_state = op(start_state)
    
    # check if the state is valid and it has not been visited
    if new_state == None or new_state in visited:
        continue
        
    # store states as visited and add them to the queue
    visited[new_state] = True
    priority = heuristic_count(new_state, final_state)
    generated.put((priority, new_state, [op]))<jupyter_output><empty_output><jupyter_text>Now the queue contains the generated states.<jupyter_code>generated.qsize()<jupyter_output><empty_output><jupyter_text>There are exactly 2 states, because only 2 operators are valid from the starting position - down and right.<jupyter_code>len(visited)<jupyter_output><empty_output><jupyter_text>The dictionary also stores 3 states that have been generated, including the starting state. It's name `visited` is actually not correct, the states have just been generated and not visited yet.Let's take a look into the states we get from the queue.<jupyter_code>generated.get()
state = generated.get()
state
print_state(state[1])<jupyter_output>1 2 3 
4 5 6 
7   8<jupyter_text>Both states have priority 3. Let's process the second one, just to see if everything works as expected.<jupyter_code>for op in [up, right, down, left]:
    new_state = op(state[1])
    
    # check if the state is valid and it has not been visited
    if new_state == None or new_state in visited:
        continue
        
    # store states as visited and add them to the queue
    visited[new_state] = True
    priority = heuristic_count(new_state, final_state)
    generated.put((priority, new_state, state[2] + [op]))<jupyter_output><empty_output><jupyter_text>Now let's see what states we get from the queue.<jupyter_code>generated.qsize()
generated.get()
generated.get()<jupyter_output><empty_output><jupyter_text>The algorithm so far generated the correct states and is moving towards the final state based on the heuristic. We can also check the dictionary.<jupyter_code>visited<jupyter_output><empty_output><jupyter_text>It contains all states that have been generated so far. We are ready. SolutionIt's time to write a method that implements the algorithm.<jupyter_code>def solve(start_state, final_state, heuristic):
    # create a queue and a dictionary
    queue = PriorityQueue()
    generated = {}
    
    # place the starting state into both
    queue.put((0, start_state, []))
    generated[start_state] = True
    
    # loop through the states until we either find the solution or run out of states
    while queue.qsize() > 0:
        state = queue.get()
        
        # if this is the final state, return the moves that got us here
        if state[1] == final_state:
            return state[2]
        
        # apply all operators
        for op in [up, right, down, left]:
            new_state = op(state[1])
    
            # check if the state is valid and it has not been visited
            if new_state == None or new_state in generated:
                continue

            # store the state as generated and add it to the queue
            generated[new_state] = True
            priority = heuristic(new_state, final_state)
            queue.put((priority, new_state, state[2] + [op]))
        
    # no solution found :(
    return None<jupyter_output><empty_output><jupyter_text>The method uses the algorithm we described and tried out above. It first puts the starting state into the queue and the dictionary. Then it loops while there are more states in the queue, applying the operators and the heuristic function. If it finds the final state, it returns the moves, otherwise it returns `None`.For printing the moves, let's create another method that takes in the list of moves and prints a string of them.<jupyter_code>def print_moves(moves) :
    for move in moves:
        if move == up:
            print('up ', end='')
        elif move == right:
            print('right ', end='')
        elif move == down:
            print('down ', end='')
        elif move == left:
            print('left ', end='')
        
    print()
print_moves([left, right])<jupyter_output>left right<jupyter_text>Let's test the solution method if it finds a correct solution to this problem.<jupyter_code>start_state = (1, 2, 3, 4, 5, 6, 7, 8, 0)
final_state = (1, 2, 3, 4, 6, 8, 7, 5, 0)
moves = solve(start_state, final_state, heuristic_count)<jupyter_output><empty_output><jupyter_text>Now print the moves.<jupyter_code>if moves:
    print_moves(moves)
else:
    print('No solution found!')<jupyter_output>right down left up<jupyter_text>And that's correct! ExamplesHere are more sample inputs and outputs for the algorithm. To make it easier to see the solutions, we will add one more method that combines `solve` and `print_moves`.<jupyter_code>def solve_print(start_state, final_state, heuristic):
    moves = solve(start_state, final_state, heuristic)
    if moves:
        print_moves(moves)
        print(len(moves), 'moves')
    else:
        print('No solution found!')<jupyter_output><empty_output><jupyter_text>Example 1<jupyter_code>start1 = (0, 1, 3, 4, 2, 5, 7, 8, 6)
end1 = (1, 2, 3, 4, 5, 6, 7, 8, 0)

print_state(start1)
print('  ↓  ')
print_state(end1)<jupyter_output>1 3 
4 2 5 
7 8 6 
  ↓  
1 2 3 
4 5 6 
7 8<jupyter_text>We will use both heuristics and both of them counting and not counting space.<jupyter_code>from functools import partial
%%time
solve_print(start1, end1, heuristic_count)
solve_print(start1, end1, partial(heuristic_count, count_space=True))
solve_print(start1, end1, heuristic_sum)
solve_print(start1, end1, partial(heuristic_sum, count_space=True))<jupyter_output>left up left up 
4 moves
left up left up 
4 moves
left up left up 
4 moves
left up left up 
4 moves
CPU times: user 2.76 ms, sys: 1.93 ms, total: 4.7 ms
Wall time: 3.29 ms<jupyter_text>This was a very easy example so all heuristics came up with the same solution. Also, no difference in performace can be seen because algorithms ran very fast. Example 2<jupyter_code>start2 = (3, 6, 4, 0, 1, 2, 8, 7, 5)
end2 = (1, 2, 3, 8, 0, 4, 7, 6, 5)

print_state(start2)
print('  ↓  ')
print_state(end2)
%%time
solve_print(start2, end2, heuristic_count)
%%time
solve_print(start2, end2, partial(heuristic_count, count_space=True))
%%time
solve_print(start2, end2, heuristic_sum)
%%time
solve_print(start2, end2, partial(heuristic_sum, count_space=True))<jupyter_output>left down right up left left down right up right up left down 
13 moves
CPU times: user 2.31 ms, sys: 1.7 ms, total: 4.01 ms
Wall time: 2.83 ms<jupyter_text>This example shows that the second heuristic performs better. Solutions using the first heuristic took way longer to finish and they found an unnecesserily long solution.We can also see that counting space made the solution worse and slower. Example 3<jupyter_code>start3 = (0, 1, 2, 3, 4, 5, 6, 7, 8)
end3 = (1, 2, 3, 4, 5, 6, 7, 8, 0)

print_state(start3)
print('  ↓  ')
print_state(end3)
%%time
solve_print(start3, end3, heuristic_count)
%%time
solve_print(start3, end3, partial(heuristic_count, count_space=True))
%%time
solve_print(start3, end3, heuristic_sum)
%%time
solve_print(start3, end3, partial(heuristic_sum, count_space=True))<jupyter_output>left left up right right up left left down right right up left left down right up right down left down left up right down left up up right down down left up right up left 
36 moves
CPU times: user 4.48 ms, sys: 1.71 ms, total: 6.19 ms
Wall time: 5.03 ms
{'fraction_non_alphanumeric': 0.08712037242296608, 'fraction_numerical': 0.024163156727998226, 'mean_word_length': 3.7554462403373154, 'pattern_counts': {'":': 0, '<': 110, '<?xml version=': 0, '>': 112, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '29', 'dir': 'jupyter-structured-clean-dedup', 'id': '627936', 'license': 'MIT', 'n_tokens_mistral': 4492, 'n_tokens_neox': 4206, 'n_words': 1656, 'path': 'Solving the puzzle.ipynb', 'repo_name': 'chuckeles/8puzzle-solution', 'size': '13541'}