Slow 8/15-puzzle IDA*

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)
self.zero_column = np.where(self.tiles == 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
• 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. – Gareth Rees Apr 29 '17 at 16:52
• 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 – superphunthyme Apr 29 '17 at 23:50