15 puzzle problem solution in python


Asked by wiki @ & viewed by 17 persons


Python 15 puzzle solver with A* algorithm can't find a solution for most cases

I've been trying to write a solver for 15 puzzle in python but now I reached a dead end where I can't figure out what's wrong with my code. It works for simple cases, where amount of moves required to solve the puzzle is low, this one for example:

5 1 2 3 9 7 11 4 13 6 15 8 14 10 0 12

where 0 represents blank tile.

When I use more complex cases (generated here), the program seems to go into an infinite loop, and even for simple cases I feel like it's not finding the optimal solution. I've been trying to figure out what's causing the problem, but after debugging it for multiple hours I didn't find anything, all of the methods seem to work properly. Can you tell me what is wrong with this code? Here's the solver class:

from copy import deepcopy


class Fifteen:

    heur = ''
    tiles = []
    undo_move = ''
    h_score = 0  # calculated using heuristic
    depth = 0
    previous_moves = []
    zero_x = 0
    zero_y = 0

    def __init__(self, heur, fin, parent=None):
        if parent is None:
            self.heur = heur
            fi = open(fin, 'r', encoding='utf-8')
            self.tiles = [list(map(int, line.split())) for line in fi]
            self.zero_x, self.zero_y = self.find()
            fi.close()
        elif parent is not None:
            self.heur = deepcopy(parent.heur)
            self.tiles = deepcopy(parent.tiles)
            self.undo_move = deepcopy(parent.undo_move)
            self.depth = deepcopy(parent.depth) + 1
            self.previous_moves = deepcopy(parent.previous_moves)
            self.zero_x = deepcopy(parent.zero_x)
            self.zero_y = deepcopy(parent.zero_y)

    def find(self, tile=0):
        for y in range(len(self.tiles)):
            for x in range(len(self.tiles[y])):
                if self.tiles[y][x] == tile:
                    return x, y
        raise NameError

    def move_tile(self, direction):
        x, y = self.zero_x, self.zero_y
        if direction == 'u':
            self.tiles[y][x], self.tiles[y - 1][x] = self.tiles[y - 1][x], self.tiles[y][x]
            self.zero_y = self.zero_y - 1
            self.previous_moves.append('u')
            self.undo_move = 'd'
        elif direction == 'd':
            self.tiles[y][x], self.tiles[y + 1][x] = self.tiles[y + 1][x], self.tiles[y][x]
            self.zero_y = self.zero_y + 1
            self.previous_moves.append('d')
            self.undo_move = 'u'
        elif direction == 'l':
            self.tiles[y][x], self.tiles[y][x - 1] = self.tiles[y][x - 1], self.tiles[y][x]
            self.zero_x = self.zero_x - 1
            self.previous_moves.append('l')
            self.undo_move = 'r'
        elif direction == 'r':
            self.tiles[y][x], self.tiles[y][x + 1] = self.tiles[y][x + 1], self.tiles[y][x]
            self.zero_x = self.zero_x + 1
            self.previous_moves.append('r')
            self.undo_move = 'l'
        else:
            raise NameError

    def generate_next_states(self):
        next_states = []
        x, y = self.zero_x, self.zero_y
        if y != 0 and self.undo_move != 'u':
            child = Fifteen(None, None, self)
            child.move_tile('u')
            next_states.append(child)
        if y != len(self.tiles) - 1 and self.undo_move != 'd':
            child = Fifteen(None, None, self)
            child.move_tile('d')
            next_states.append(child)
        if x != 0 and self.undo_move != 'l':
            child = Fifteen(None, None, self)
            child.move_tile('l')
            next_states.append(child)
        if x != len(self.tiles[y]) - 1 and self.undo_move != 'r':
            child = Fifteen(None, None, self)
            child.move_tile('r')
            next_states.append(child)
        return next_states

    def heuristic(self):
        if self.heur == 'hamm':
            return self.hamming()
        return self.manhattan()

    def hamming(self):
        diff = 0
        for y in range(len(self.tiles)):
            for x in range(len(self.tiles[y])):
                if y == len(self.tiles) - 1 and x == len(self.tiles[y]) - 1:
                    if self.tiles[y][x] != 0:
                        diff += 1
                elif self.tiles[y][x] != y * len(self.tiles) + x + 1:
                    diff += 1
        return diff

    def manhattan(self):
        score = 0
        value = 1
        for y in range(len(self.tiles)):
            for x in range(len(self.tiles[y])):
                if value == 16:
                    value = 0
                x_real, y_real = self.find(value)
                dx = abs(x - x_real)
                dy = abs(y - y_real)
                score += dx + dy
                value += 1
        return score

    def astar(self):

        queue = [self]
        closed_set = {}
        while len(queue) > 0:
            current_state = queue.pop(0)
            closed_set[repr(current_state.tiles)] = current_state
            if current_state.heuristic() == 0:
                print(current_state.tiles)
                print(current_state.previous_moves)
                print(len(current_state.previous_moves))
                return
            for state in current_state.generate_next_states():
                if repr(state.tiles) in closed_set:
                    continue
                state.h_score = state.heuristic()
                queue.append(state)
            queue.sort(key=lambda x: x.h_score, reverse=False)
        print(-1)
        return

And this is how I run it:

from fifteen import Fifteen

f = Fifteen('manh', "start.txt")
f.astar()

The first argument can be either manh or hamm, depending on the heuristic used, second one is name of file containing initial puzzle setup.

Do you know the better answer?

Similar questions

8 puzzle problem using breadth first search in python

Asked by wiki @ & viewed by 5 persons

Python implementation of BFS to solve 8-puzzle takes too long to find a solution My implementation of BFS in Python …

8 puzzle problem using best first search in python

Asked by wiki @ & viewed by 8 persons

Python implementation of BFS to solve 8-puzzle takes too long to find a solution My implementation of BFS in Python …

15 puzzle solver python

Asked by wiki @ & viewed by 20 persons

Python 15 puzzle solver with A* algorithm can't find a solution for most cases I've been trying to write a …

15 puzzle python code

Asked by wiki @ & viewed by 11 persons

Python 15 puzzle solver with A* algorithm can't find a solution for most cases I've been trying to write a …

Project euler problem 15 python

Asked by wiki @ & viewed by 9 persons

Project Euler #15 in Python I am newbie in Python. I'm stuck on doing Problem 15 in Project-Euler in reasonable …

Diffusion equation solution 1d python

Asked by wiki @ & viewed by 6 persons

Solving heat equation with python (NumPy) I solve the heat equation for a metal rod as one end is kept …

Crossword puzzle python code

Asked by wiki @ & viewed by 7 persons

Placing a crossword puzzle into a tkiner in python 3.2 I managed to write code (through a tutorial) that runs …

Coderbyte solutions python

Asked by wiki @ & viewed by 5 persons

CoderByte Python import statements [closed] Closed. This question needs debugging details. It is not currently accepting answers. Want to improve …

Nim game python solution

Asked by wiki @ & viewed by 6 persons

Python help - Game of Nim Python novice here trying to trouble shoot my game of nim code. Basically the …

Cryptarithmetic problem python code

Asked by wiki @ & viewed by 4 persons

Cryptarithmetic puzzle generic solution in Python 3 I am stuck with this problem statement, My code does work but I …

Sum of subset problem using backtracking python

Asked by wiki @ & viewed by 5 persons

Subset Sum with Backtracking on Python So I want to print out all the subsets of the initial set that …

Python round problem

Asked by wiki @ & viewed by 6 persons

round() doesn't seem to be rounding properly The documentation for the round() function states that you pass it a number, …

Staircase hackerrank solution python

Asked by wiki @ & viewed by 7 persons

HackerRank Staircase Python I am trying to solve a problem in HackerRank and I am having an issue with my …

Python encoding problem

Asked by wiki @ & viewed by 6 persons

Python Encoding Issue I am really lost in all the encoding/decoding issues with Python. Having read quite few docs about …

Bin packing problem python

Asked by wiki @ & viewed by 6 persons

Python Implementations of Packing Algorithm For an application I'm working on I need something like a packing algorithm implemented in …

Most viewed questions


Python strftime milliseconds

Asked by wiki @ & viewed by 201 persons

Format a datetime into a string with milliseconds I want to have a datetime string from the date with milliseconds. …

What does the percent sign mean in python

Asked by wiki @ & viewed by 136 persons

What does the percentage sign mean in Python In the tutorial there is an example for finding prime numbers: >>> …

Self keyword in python

Asked by wiki @ & viewed by 135 persons

What is the purpose of the word 'self'? What is the purpose of the self word in Python? I understand …

Check object type python

Asked by wiki @ & viewed by 133 persons

Determine the type of an object? Is there a simple way to determine if a variable is a list, dictionary, …

Correlation matrix python

Asked by wiki @ & viewed by 132 persons

Plot correlation matrix using pandas I have a data set with huge number of features, so analysing the correlation matrix …

Alphabetical sort python

Asked by wiki @ & viewed by 131 persons

Python data structure sort list alphabetically I am a bit confused regarding data structure in python; (),[], and {}. I …

Python random

Asked by wiki @ & viewed by 127 persons

Generate random integers between 0 and 9 How can I generate random integers between 0 and 9 (inclusive) in Python? …

Python one line for loop

Asked by wiki @ & viewed by 124 persons

Python one-line “for” expression I'm not sure if I need a lambda, or something else. But still, I need the …

Python create dataframe from list

Asked by wiki @ & viewed by 124 persons

Python: create a pandas data frame from a list I am using the following code to create a data frame …

How to add a column to dataframe python

Asked by wiki @ & viewed by 123 persons

Adding new column to existing DataFrame in Python pandas I have the following indexed DataFrame with named columns and rows …

Why we use self in python

Asked by wiki @ & viewed by 116 persons

What is the purpose of the word 'self'? What is the purpose of the self word in Python? I understand …

Shape 0 python

Asked by wiki @ & viewed by 115 persons

x.shape[0] vs x[0].shape in NumPy Let say, I have an array with x.shape = (10,1024) when I try to print …

Python print working directory

Asked by wiki @ & viewed by 113 persons

Find current directory and file's directory [duplicate] This question already has answers here: How do you properly determine the current …

Image shape python

Asked by wiki @ & viewed by 110 persons

Python OpenCV2 (cv2) wrapper to get image size? How to get the size of an image in cv2 wrapper in …

Interface grafica python

Asked by wiki @ & viewed by 108 persons

Como criar interface gráfica em Python? [duplicada] Essa pergunta já tem uma resposta aqui: É possível criar interfaces gráficas para …