8-puzzle pattern database in Python

Question

I was originally trying to create a disjoint (6-6-3) pattern database for the 15-puzzle, but I've been struggling so much that I resorted to first trying to create a full pattern database for the 8-puzzle, which means that I want to save all possible permutations of the 8-puzzle to a file in order to create a heuristic to use when trying to solve the puzzle with the A* algorithm.

The goal state of the 8-puzzle is [1, 2, 3, 4, 5, 6, 7, 8, 0] where 0 is the blank tile. In order to create the permutations I'm using breadth-first search from the goal state and save each permutation as a tuple of the puzzle state and the cost (number of moves) to reach it from the goal state.

My code is as follows:

import math
import json
from collections import deque
from copy import deepcopy
from timeit import default_timer

# Goal state of the puzzle
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]


# Calculates the possible moves of the blank tile.
def get_moves(puzzle):
    # Lists potential moves in order: up, right, down, left.
    potential_moves = [-3, 1, 3, -1]

    # Checks which moves are possible.
    possible_moves = []
    for pm in potential_moves:
        pos = puzzle.index(0)
        pos += pm
        if pos in range(8):
            possible_moves += [pm]

    return possible_moves


# Moves the blank tile in the puzzle.
def move(puzzle, direction):
    # Creates a copy of the new_puzzle to change it.
    new_puzzle = deepcopy(puzzle)
    pos = puzzle.index(0)

    # Swaps blank tile with tile in direction.
    if direction == -3:
        new_puzzle[pos], new_puzzle[pos-3] = new_puzzle[pos-3], new_puzzle[pos]
    elif direction == 1:
        new_puzzle[pos], new_puzzle[pos+1] = new_puzzle[pos+1], new_puzzle[pos]
    elif direction == 3:
        new_puzzle[pos], new_puzzle[pos+3] = new_puzzle[pos+3], new_puzzle[pos]
    elif direction == -1:
        new_puzzle[pos], new_puzzle[pos-1] = new_puzzle[pos-1], new_puzzle[pos]

    return new_puzzle


# Transforms a puzzle to a string.
def puzzle_to_string(puzzle):
    string = ""
    for t in puzzle:
        string += str(t)

    return string


# Creates the database.
def create_database():
    # Initializes a timer, starting state, queue and visited set.
    begin = default_timer()
    start = goal
    queue = deque([[start, 0]])
    visited = set()
    visited.add((puzzle_to_string(start), 0))

    print("Generating database...")
    print("Collecting entries...")
    # BFS taking into account a state and the cost to reach it from the starting state.
    while queue:
        states = queue.popleft()
        state = states[0]
        cost = states[1]

        for m in get_moves(state):
            next_state = move(state, m)
            cost += 1

            if not any(s for s in visited if s[0] == puzzle_to_string(next_state)):
                queue.append([next_state, cost])
                visited.add((puzzle_to_string(next_state), cost))

        # Print a progress for every x entries in visited.
        if len(visited) % 10000 == 0:
            print("Entries collected: " + str(len(visited)))

        # Exit loop when all permutations for the puzzle have been found.
        if len(visited) >= math.factorial(9)/2:
            break

    print("Writing entries to database...")
    # Writes entries to the text file, sorted by cost in ascending order .
    with open("database.txt", "w") as f:
        for entry in sorted(visited, key=lambda c: c[1]):
            json.dump(entry, f)
            f.write("\n")

    end = default_timer()
    minutes = math.floor((end-begin)/60)
    seconds = math.floor((end-begin) % 60)
    return "Generated database in " + str(minutes) + " minute(s) and " + str(seconds) + " second(s)."


print(create_database())

Now, the issue is that it (still) takes unbearably long for the entries to fill up which it probably shouldn't as the 8-puzzle only has 9!/2 = 181440 possible permutations, so it should be possible to create a full database fairly quickly.

I would appreciate any kind of input into this issue and if possible also some hints in the direction of creating disjoint pattern databases for the 15-puzzle.

Thanks in advance!

Edit: I found the issue, I managed to mess up the move function when converting from the 15-puzzle which uses 4 rows instead of having a 1-dimensional string. In addition, I also messed up incrementing the cost of the states somewhere along the line.

Here is the updated working code, that generates the full database for 8-puzzle in ~15 seconds on my machine.

import json
import math
from collections import deque
from copy import deepcopy
from timeit import default_timer

# Goal state of the puzzle
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]


# Calculates the possible moves of the blank tile.
def get_moves(puzzle):
    pos = puzzle.index(0)

    if pos == 0:
        possible_moves = [1, 3]
    elif pos == 1:
        possible_moves = [1, 3, -1]
    elif pos == 2:
        possible_moves = [3, -1]
    elif pos == 3:
        possible_moves = [-3, 1, 3]
    elif pos == 4:
        possible_moves = [-3, 1, 3, -1]
    elif pos == 5:
        possible_moves = [-3, 3, -1]
    elif pos == 6:
        possible_moves = [-3, 1]
    elif pos == 7:
        possible_moves = [-3, 1, -1]
    else:
        possible_moves = [-3, -1]

    return possible_moves


# Moves the blank tile in the puzzle.
def move(puzzle, direction):
    # Creates a copy of the new_puzzle to change it.
    new_puzzle = deepcopy(puzzle)
    pos = puzzle.index(0)
    # Position blank tile will move to.
    new_pos = pos + direction
    # Swap tiles.
    new_puzzle[pos], new_puzzle[new_pos] = new_puzzle[new_pos], new_puzzle[pos]

    return new_puzzle


# Creates the database.
def create_database():
    # Initializes a timer, starting state, queue and visited set.
    begin = default_timer()
    start = goal
    queue = deque([[start, 0]])
    entries = set()
    visited = set()

    print("Generating database...")
    print("Collecting entries...")
    # BFS taking into account a state and the cost (number of moves) to reach it from the starting state.
    while queue:
        state_cost = queue.popleft()
        state = state_cost[0]
        cost = state_cost[1]

        for m in get_moves(state):
            next_state = move(state, m)

            # Increases cost if blank tile swapped with number tile.
            pos = state.index(0)
            if next_state[pos] > 0:
                next_state_cost = [next_state, cost+1]
            else:
                next_state_cost = [next_state, cost]

            if not "".join(str(t) for t in next_state) in visited:
                queue.append(next_state_cost)

            entries.add(("".join(str(t) for t in state), cost))
            visited.add("".join(str(t) for t in state))

        # Print a progress for every x entries in visited.
        if len(entries) % 10000 == 0:
            print("Entries collected: " + str(len(entries)))

        # Exit loop when all permutations for the puzzle have been found.
        if len(entries) >= 181440:
            break

    print("Writing entries to database...")
    # Writes entries to the text file, sorted by cost in ascending order .
    with open("database.txt", "w") as f:
        for entry in sorted(entries, key=lambda c: c[1]):
            json.dump(entry, f)
            f.write("\n")

    end = default_timer()
    minutes = math.floor((end-begin)/60)
    seconds = math.floor((end-begin) % 60)
    return "Generated database in " + str(minutes) + " minute(s) and " + str(seconds) + " second(s)."


print(create_database())

Answer 1

Seems like in move function direction only provides potential_moves and pattern is same. It could help to replace all if else with just,

tmp = pos + direction 
new_puzzle[pos], new_puzzle[tmp] = new_puzzle[tmp], new_puzzle[pos]

Use precalculated value of, math.factorial(9)/2 outside loop with bitwise shift. You could move function contents into the loop itself and remove function calls. https://nyu-cds.github.io/python-performance-tips/04-functions/

Remove puzzle_to_string function and Convert int list to string inline.

Use in get moves,

pos = puzzle.index(0) + pm

This could make it worse. You could also try to remove all puzzle_to_string function calls and replace goal = (1, 2, 3, 4, 5, 6, 7, 8, 0) as tuple. Then handle it in move function by converting to list before assignment and convert back to tuple before returning.