EightPuzzleSolver

hw2.py

from random import shuffle
import heapq

def main():
    # puzzles = []
    # while len(puzzles) < 100:
    #     puzzles.append(generate_solvable_puzzle())

    node = Node(generate_solvable_puzzle(), None)
    print(node)

    n1 = node.move_up()
    print('Moving up')
    print(Node(n1, None))

    # n = Node([2, 1, 4, 5, 0, 6, 7, 8, 3])
    # print(n)
    n2 = node.move_down()
    print('Moving down')
    print(Node(n2, None))

    n3 = node.move_right()
    print('Moving right')
    print(Node(n3, None))

    n4 = node.move_left()
    print('Moving left')
    print(Node(n4, None))


class Node:
    goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]

    def __init__(self, state, parent=None):
        self.state = state # state is None if illegal state
        self.parent = parent

    def __str__(self):
        pattern = '[%s %s %s]\n[%s %s %s]\n[%s %s %s]'
        values = [str(x) if x != 0 else ' ' for x in self.state]
        return pattern % tuple(values)

    def __repr__(self):
        return str(self)

    def __eq__(self, other): # for comparing the nodes and detecting repeated states
        return self.state == other.state

    def children(self):
        children = [Node(self.move_up(), self), Node(self.move_down(), self), Node(self.move_left(), self),
                    Node(self.move_right(), self)] # GENERATE ALL POSSIBLE STATES
        children = [node if node.state is not None for node in children] # eliminate illegal states
        return children

    def search(self):
        # http://aima.cs.berkeley.edu/python/search.html
        '''
        Best-First-Search( Maze m )
            Insert( m.StartNode )
            Until PriorityQueue is empty
                c <- PriorityQueue.DeleteMin
                If c is the goal
                    Exit
                Else
                    Foreach neighbor n of c
                        If n "Unvisited"
                            Mark n "Visited"
                            Insert( n )
                    Mark c "Examined"
        End procedure
        '''

        closed = {}
        fringe.append(Node(problem.initial))
        while fringe:
            node = fringe.pop()
            if problem.goal_test(node.state):
                return node
            if node.state not in closed:
                closed[node.state] = True
                fringe.extend(node.expand(problem))
        return None


    def num_of_misplaced_tiles(self):
        misplaced = 0
        for index, tile in enumerate(self.state):
            if tile != 0 and index + 1 != tile:
                misplaced += 1
        return misplaced


    def move_up(self):
        blank_position = self.state.index(0)
        if blank_position < 6: # means that blank is not on the last row
            puzzle = self.state.copy()
            puzzle[blank_position], puzzle[blank_position + 3] = puzzle[blank_position + 3], puzzle[blank_position]
            return puzzle
        else: # if illegal state
            return None

    def move_down(self):
        blank_position = self.state.index(0)
        if blank_position > 2: # means that blank is not on the first row
            puzzle = self.state.copy()
            puzzle[blank_position], puzzle[blank_position - 3] = puzzle[blank_position - 3], puzzle[blank_position]
            return puzzle
        else: # if illegal state
            return None

    def move_right(self):
        blank_position = self.state.index(0)
        if blank_position not in [0, 3, 6]: # means that blank is not on the first column
            puzzle = self.state.copy()
            puzzle[blank_position], puzzle[blank_position - 1] = puzzle[blank_position - 1], puzzle[blank_position]
            return puzzle
        else: # if illegal state
            return None

    def move_left(self):
        blank_position = self.state.index(0)
        if blank_position not in [2, 5, 8]: # means that blank is not on the last row
            puzzle = self.state.copy()
            puzzle[blank_position], puzzle[blank_position + 1] = puzzle[blank_position + 1], puzzle[blank_position]
            return puzzle
        else: # if illegal state
            return None

class PriorityQueue:
    # Initialize the instance
    def __init__(self):
        # Create a list to use as the queue
        self._queue = []
        # Create an index to use as ordering
        self._index = 0

    # Create a function to add a task to the queue
    def append(self, item, priority):
        # Push the arguments to the _queue using a heap
        heapq.heappush(self._queue, (-priority, self._index, item))
        # Add one to the index
        self._index += 1

    # Create a function to get the next item from the queue
    def pop(self):
        # Return the next item in the queue
        return heapq.heappop(self._queue)[-1]

    def __str__(self):
        return str(self._queue)


def generate_solvable_puzzle():
    while True:
        puzzle = [1, 2, 3, 4, 5, 6, 7, 8, 0]

        shuffle(puzzle)
        # print(puzzle)

        inversions = 0
        for i in range(len(puzzle)):
            for j in range(i+1, len(puzzle)):
                if puzzle[j] > puzzle[i]:
                    inversions += 1

        if inversions % 2 == 0:
            return puzzle
        else:
            print('Generated an unsolvable puzzle, trying again')

if __name__ == '__main__':
    main()