8 tile solver with repeated nodes - Python

Question

i'm trying to solve the 8tile puzzle using techniques like BFS search, DFS, Greedy and A* using Manhattan distance as my heuristic solution.

The problem is that while i can solve some good number of problems, the problem is with some of the puzzles, it can occur that the children i get on expanding the parent node can already be in the older nodes.

I don't know if i was able to explain myself well, but my main problem is everything i tried to see if the new nodes that i create aren't already on the old nodes.

With this problem i usually get to depth 9 and then my program doesn't advance or give solution.

One of my ideias was using the code:

if node in prev:
    continue
prev.append(node)

But i guess i'm going the wrong way.

I'm doing this on python and here's my code in case someone can help me.

#!/usr/bin/python

import sys
import copy


class Board:
    def __init__(self, matrix, whitepos=None):
        self.matrix = matrix
        self.whitepos = whitepos
        if not whitepos:
            for y in xrange(3):
                for x in xrange(3):
                    if board[y][x] == 0:
                        self.whitepos = (x, y)


def is_final_state(board):
    final = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
    for y in xrange(3):
        for x in xrange(3):
            if board.matrix[y][x] != final[y][x]:
                return False
    return True


def get_whitepos(board):
    return board.whitepos


def move(board, x, y, dx, dy):
    b = copy.deepcopy(board.matrix)
    b[y][x] = b[y + dy][x + dx]
    b[y + dy][x + dx] = 0
    return Board(b, (x + dx, y + dy))


def manhattan_heur(board):
    finalpos = [(1, 1), (0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2),
                (0, 1)]
    cost = 0
    for y in xrange(3):
        for x in xrange(3):
            t = board.matrix[y][x]
            xf, yf = finalpos[t]
            cost += abs(xf - x) + abs(yf - y)
    return cost


def wrongplace_heur(board):
    finalpos = [(1, 1), (0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2),
                (0, 1)]
    cost = 0
    for y in xrange(3):
        for x in xrange(3):
            t = board.matrix[y][x]
            if finalpos[t] != (x, y):
                cost += 1
    return cost


def heuristic(board):
    return manhattan_heur(board)


class Node:
    def __init__(self, board, parent):
        self.state = board
        self.parent = parent
        if not parent:
            self.g = 0
        else:
            self.g = parent.g + 1
        self.h = heuristic(board)

    def test_goal(self):
        return is_final_state(self.state)

    def expand(self):
        children = []
        b = self.state
        x, y = get_whitepos(b)
        if x > 0:
            children.append(Node(move(b, x, y, -1, 0), self))
        if x < 2:
            children.append(Node(move(b, x, y, +1, 0), self))
        if y > 0:
            children.append(Node(move(b, x, y, 0, -1), self))
        if y < 2:
            children.append(Node(move(b, x, y, 0, +1), self))
        return children


class Solution:
    def __init__(self, node, mem_needed, steps):
        self.node = node
        self.mem_needed = mem_needed
        self.iterations = steps

    def inc(self, other):
        self.node = other.node
        self.mem_needed = max(self.mem_needed, other.mem_needed)
        self.iterations += other.iterations


def search(board, queue_fn, queue_arg=None):
    max_nodes = 1
    steps = 0
    nodes = [Node(Board(board), None)]
    prev = []
    depth = 0
    while nodes:
        node = nodes.pop(0)

        if node.g > depth:
            depth = node.g
            print depth

        if node in prev:
            continue
        prev.append(node)

        if node.test_goal():
            return Solution(node, max_nodes, steps)
        new_nodes = node.expand()
        nodes = queue_fn(nodes, new_nodes, queue_arg)

        max_nodes = max(max_nodes, len(nodes))
        steps += 1
    return Solution(None, max_nodes, steps)


def fifo_queue(nodes, new_nodes, _):
    nodes.extend(new_nodes)
    return nodes


def bl_search(board):
    return search(board, fifo_queue)


def lifo_queue(nodes, new_nodes, _):
    new_nodes.extend(nodes)
    return new_nodes


def dfs_search(board):
    return search(board, lifo_queue)


def bpl_queue(nodes, new_nodes, max_depth):
    def f(n):
        return n.g <= max_depth

    new_nodes = filter(f, new_nodes)
    new_nodes.extend(nodes)
    return new_nodes


def bpi_search(board):
    solution = Solution(None, 0, 0)
    for max_depth in xrange(0, sys.maxint):
        sol = search(board, bpl_queue, max_depth)
        solution.inc(sol)
        if solution.node:
            return solution


def sort_queue(nodes, new_nodes, cmp):
    nodes.extend(new_nodes)
    nodes.sort(cmp)
    return nodes


def guloso2_search(board):
    def cmp(n1, n2):
        return n1.h - n2.h

    return search(board, sort_queue, cmp)


def astar_search(board):
    def cmp(n1, n2):
        return (n1.g + n1.h) - (n2.g + n2.h)

    return search(board, sort_queue, cmp)


def print_solution(search, sol):
    print
    print "*", search
    node = sol.node
    if node:
        print "moves:", node.g
        while node:
            print "\t", node.state.matrix
            node = node.parent
    else:
        print "no solution found"
    print "nodes needed:", sol.mem_needed
    print "iterations:  ", sol.iterations


board = [[6, 5, 7], [2, 0, 1], [8, 4, 3]]

print_solution("bl", bl_search(board))
print_solution("dfs", dfs_search(board))
print_solution("bpi", bpi_search(board))
print_solution("guloso2", guloso2_search(board))
print_solution("astar", astar_search(board))

Answer 1

Looks like you're going about it the right way, but you need to define the __eq__ and __ne__ methods in the Node class; otherwise node in prev will always return False because Python doesn't know how to compare node to the items in the list. Check out the Python data model documentation for more on how comparisons work on user-defined types.

I grabbed your code and added a couple of (very naive) methods to do the equality checking, and it no longer appears to be hanging. It's also worth noting that your classes ought to be inheriting from the base object (see below). These are the changes I made (in context):

class Board(object):
    def __init__(self, matrix, whitepos=None):
        self.matrix = matrix
        self.whitepos = whitepos
        if not whitepos:
            for y in xrange(3):
                for x in xrange(3):
                    if board[y][x] == 0:
                        self.whitepos = (x, y)
    def __eq__(self, o):
        # Note that comparing whitepos is not strictly necessary; but I left 
        # it in as a safety measure in case the board state gets corrupted.
        # If speed becomes an issue, take it out.
        return (self.matrix, self.whitepos) == (o.matrix, o.whitepos)

class Node(object):
    def __init__(self, board, parent):
        self.state = board
        self.parent = parent
        if not parent:
            self.g = 0
        else:
            self.g = parent.g + 1
        self.h = heuristic(board)

    def test_goal(self):
        return is_final_state(self.state)

    def expand(self):
        children = []
        b = self.state
        x, y = get_whitepos(b)
        if x > 0:
            children.append(Node(move(b, x, y, -1, 0), self))
        if x < 2:
            children.append(Node(move(b, x, y, +1, 0), self))
        if y > 0:
            children.append(Node(move(b, x, y, 0, -1), self))
        if y < 2:
            children.append(Node(move(b, x, y, 0, +1), self))
        return children

    def __eq__(self, o):
        # Note that you don't have to compare parents, since your goal
        # is to eliminate ANY nodes with the same position.
        return self.state == o.state

class Solution(object):
    def __init__(self, node, mem_needed, steps):
        self.node = node
        self.mem_needed = mem_needed
        self.iterations = steps

    def inc(self, other):
        self.node = other.node
        self.mem_needed = max(self.mem_needed, other.mem_needed)
        self.iterations += other.iterations

#...

print_solution("bl", bl_search(board))
# I commented out all but the first search to avoid cluttering up the output.

With these changes, the code does produce a solution (I'll leave it up to you to verify that it's correct, but here's my output).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

* bl
moves: 20
    [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
    [[1, 2, 3], [8, 6, 4], [7, 0, 5]]
    [[1, 2, 3], [8, 6, 4], [0, 7, 5]]
    [[1, 2, 3], [0, 6, 4], [8, 7, 5]]
    [[1, 2, 3], [6, 0, 4], [8, 7, 5]]
    [[1, 0, 3], [6, 2, 4], [8, 7, 5]]
    [[0, 1, 3], [6, 2, 4], [8, 7, 5]]
    [[6, 1, 3], [0, 2, 4], [8, 7, 5]]
    [[6, 1, 3], [2, 0, 4], [8, 7, 5]]
    [[6, 1, 3], [2, 7, 4], [8, 0, 5]]
    [[6, 1, 3], [2, 7, 4], [8, 5, 0]]
    [[6, 1, 3], [2, 7, 0], [8, 5, 4]]
    [[6, 1, 0], [2, 7, 3], [8, 5, 4]]
    [[6, 0, 1], [2, 7, 3], [8, 5, 4]]
    [[6, 7, 1], [2, 0, 3], [8, 5, 4]]
    [[6, 7, 1], [2, 5, 3], [8, 0, 4]]
    [[6, 7, 1], [2, 5, 3], [8, 4, 0]]
    [[6, 7, 1], [2, 5, 0], [8, 4, 3]]
    [[6, 7, 0], [2, 5, 1], [8, 4, 3]]
    [[6, 0, 7], [2, 5, 1], [8, 4, 3]]
    [[6, 5, 7], [2, 0, 1], [8, 4, 3]]
nodes needed: 44282
iterations:   59930

Hope this helps!