4
\$\begingroup\$

I am trying to find the optimal solution for a given 15-puzzle. So far as I can tell, the algorithm works (on simple instances of 8-puzzle), but is extremely slow for complex starting states (order of 100 seconds), and practically unsolvable with 15 tiles. I know finding the optimal solution is hard but I think I may be using the language in an efficient way here.

IDAStarSolver.solve() contains the starting point for computing the solution, although most of the operations are done in the Board class.

This is the class containing the solver:

import sys
from heapq import heappop, heappush
from src.State import State

class IDAStarSolver:
    def __init__(self, board, heuristic='manhattan'):
        self.solution = []
        self.initial = board
        self.heuristic = heuristic

    def solve(self):
        bound = getattr(self.initial, self.heuristic)

        while True:
            t = self.search(self.initial, 0, bound)
            if t == 'FOUND':
                return bound
            if t == sys.maxsize:
                return 'NOT_FOUND'
            bound = t

    def search(self, node, g, bound):
        f = g + getattr(node, self.heuristic)
        if f > bound:
            return f
        if getattr(node, self.heuristic) == 0:
            return 'FOUND'
        minimum = sys.maxsize
        for neighbour in node.neighbours():
            t = self.search(neighbour, g + 1, bound)
            if t == 'FOUND':
                self.solution.append(node)
                return 'FOUND'
            if t < minimum:
                minimum = t
        return minimum

    def moves(self):
        return len(self.solution)

And the Board is represented as follows:

from copy import copy
import numpy as np

class Board:
    """ A nxn board for with n^2 - 1 tiles """

    def __init__(self, tiles=None, size=3):
        if tiles is None:
            self.dim = size
            self.tiles = self.generate_board(size)
            while not self.is_solvable():
                self.tiles = self.generate_board(size)
        else:
            self.dim = len(tiles)
            self.tiles = tiles

        self.zero_row = np.where(self.tiles == 0)[0][0]
        self.zero_column = np.where(self.tiles == 0)[1][0]
        self.manhattan = self._manhattan()

    def __copy__(self):
        cls = self.__class__
        new_copy = cls.__new__(cls)
        new_copy.tiles = np.copy(self.tiles)
        new_copy.manhattan = self.manhattan
        new_copy.dim = self.dim
        new_copy.zero_row = self.zero_row
        new_copy.zero_column = self.zero_column
        return new_copy

    def _manhattan(self):
        manhattan = 0
        for i in range(self.dim):
            for j in range(self.dim):
                if self.tiles[i][j] != 0:
                    row = (self.tiles[i][j] - 1) // self.dim
                    column = (self.tiles[i][j] - 1) % self.dim
                    manhattan += abs(i - row) + abs(j - column)
        return manhattan

    def equals(self, board):
        """
        :param Board board: Test board
        """
        return np.array_equal(board.tiles, self.tiles)

    def swap_zero(self, i0, j0):
        """
        Swaps tile at i0, j0 with the zero tile
        """
        # Recalculate manhattan distance
        row = (self.tiles[i0][j0] - 1) // self.dim
        column = (self.tiles[i0][j0] - 1) % self.dim
        self.manhattan -= abs(i0 - row) + abs(j0 - column)
        self.manhattan += abs(self.zero_row - row) + abs(self.zero_column - column)

        # Swap tiles
        self.tiles[i0][j0], self.tiles[self.zero_row, self.zero_column] = \
                self.tiles[self.zero_row, self.zero_column], self.tiles[i0, j0]
        # Update zero row and column
        self.zero_row = i0
        self.zero_column = j0

    def neighbours(self):
        neighbours = []

        # The zero tile can be swapped with tile above
        if self.zero_row > 0:
            neighbour = copy(self)
            neighbour.swap_zero(self.zero_row - 1, self.zero_column)
            neighbours.append(neighbour)

        # The zero tile can be swapped with tile below
        if self.zero_row < self.dim - 1:
            neighbour = copy(self)
            neighbour.swap_zero(self.zero_row + 1, self.zero_column)
            neighbours.append(neighbour)

        # The zero tile can be swapped with the tile to its left
        if self.zero_column > 0:
            neighbour = copy(self)
            neighbour.swap_zero(self.zero_row, self.zero_column - 1)
            neighbours.append(neighbour)

        # The zero tile can be swapped with the tile to its right
        if self.zero_column < self.dim - 1:
            neighbour = copy(self)
            neighbour.swap_zero(self.zero_row, self.zero_column + 1)
            neighbours.append(neighbour)
        return neighbours

    def is_solved(self):
        """
        Checks if the board is the goal position
        """
        return self.manhattan() == 0

    def is_solvable(self):
        """
        Checks if the board is solvable
        """
        tiles = np.ndarray.flatten(self.tiles)
        dim = self.dim * self.dim

        inversions = 0
        for i in range(dim):
            for j in range(i, dim):
                if tiles[i] != 0 and tiles[j] != 0 and tiles[i] > tiles[j]:
                    inversions += 1

        return inversions % 2 == 0

    @staticmethod
    def generate_board(size):
        arr = np.arange(size ** 2)
        np.random.shuffle(arr)
        arr = arr.reshape(size, size)
        return arr


    def __str__(self):
        return np.array_str(self.tiles)

And the State:

import functools

@functools.total_ordering
class State:
    def __init__(self, current, previous, moves):
        """
        :param current: The current board position
        :param previous: The previous board position
        :param moves: The number of moves made to get to the current board position
        """
        self.current = current
        self.moves = moves
        self.previous = previous
        self.score = self._score()

    def _score(self):
        return self.current.manhattan + self.moves

    def __lt__(self, other):
        return self.score < other.score

    def __eq__(self, other):
        return self.score == other.score
\$\endgroup\$
  • 1
    \$\begingroup\$ The A* algorithm finds the best solution — and in order to do so it has to examine a lot of alternatives in order to prove that the solution it finds really is the best. See here for details. If you are prepared to accept any solution (even if you can't prove it is the best) then other algorithms can be much faster on this problem. \$\endgroup\$ – Gareth Rees Apr 29 '17 at 16:52
  • \$\begingroup\$ The goal was to find the optimal solution, but I'm still curious about alternate approaches for non-optimal solutions so thanks for the link. The main problem here is that there is still issues with puzzles >35 moves, and according to what I've seen, these should be practically solvable \$\endgroup\$ – superphunthyme Apr 29 '17 at 23:50
0
\$\begingroup\$

You can use a better heuristic than Manhattan distance. Take a look at the pattern database heuristic. The speedup here would be massive.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.