Main.py

"""
    An implementation of A* Search Algorithm to solve the 8-Puzzle Problem
"""
from queue import PriorityQueue
import curses
import time

class Board(object):
    """
    - This class defines a board for the 8-Puzzle.
    - Tiles are denoted using 1-8, 0 denotes a blank tile.
    """
    def __init__(self, board=None, moves=0, previous=None):
        """
            board: array representing the current board,
            moves: number of moves to get to this board,
            previous: previous state of the board
        """
        if board is None:
            self.board = [1, 2, 3, 4, 5, 6, 7, 8, 0]
        else:
            self.board = board
        self.previous = previous
        self.moves = moves

    def is_goal(self):
        """
            returns True if current board is goal state
        """
        for i in range(0, 9):
            if i != 8:
                if self.board[i] != i + 1:
                    return False

        return True

    def move_blank(self, where):
        """
            where: Move blank 'left', 'right',
                    'up', or 'down',
                   Does nothing if the move is out-of-bounds.
        """
        blank = self.find_blank()

        if where == 'left':
            if blank % 3 != 0:
                t_col = (blank % 3) - 1
                t_row = int(blank / 3)
                self.exchange(blank, t_row * 3 + t_col)

        if where == 'right':
            if blank % 3 != 2:
                t_col = (blank % 3) + 1
                t_row = int(blank / 3)
                self.exchange(blank, t_row * 3 + t_col)

        if where == 'up':
            if int(blank / 3) != 0:
                t_col = (blank % 3)
                t_row = int(blank / 3) - 1
                self.exchange(blank, t_row * 3 + t_col)

        if where == 'down':
            if int(blank / 3) != 2:
                t_col = (blank % 3)
                t_row = int(blank / 3) + 1
                self.exchange(blank, t_row * 3 + t_col)

    def find_blank(self):
        """
            returns index of blank tile
        """
        blank = None
        for i in range(0, 9):
            if self.board[i] == 0:
                blank = i
                break
        return blank

    def clone(self):
        """
            returns copy of the current board with
                moves = current moves + 1 and
                previous = current board
        """
        return Board(self.board.copy(), self.moves + 1, self)


    def exchange(self, source, target):
        """
            exchange the 'source' tile with 'target'
        """
        # print('Exchanging: {} <-> {}'.format(source, target))
        self.board[source], self.board[target] = self.board[target], self.board[source]


    def neighbours(self):
        """
            returns a list of all valid neighbours generated by moving
                the blank tile once in all possible directions
        """
        blank_index = self.find_blank()

        neighbours = []

        # print('Blank found: {}, := {}, {}'.format(blank_index, int(blank_index / 3), blank_index % 3))
        # Can we move blank tile left?
        if blank_index % 3 != 0:
            new_board = self.clone()
            new_board.move_blank('left')
            neighbours.append(new_board)

        # right?
        if blank_index % 3 != 2:
            new_board = self.clone()
            new_board.move_blank('right')
            neighbours.append(new_board)

        # up?
        if int(blank_index / 3) != 0:
            new_board = self.clone()
            new_board.move_blank('up')
            neighbours.append(new_board)

        # down?
        if int(blank_index / 3) != 2:
            new_board = self.clone()
            new_board.move_blank('down')
            neighbours.append(new_board)

        return neighbours


    def manhattan(self):
        """
            returns manhattan distance for the board
        """
        manhattan = 0
        for i in range(0, 9):
            if self.board[i] != i + 1 and self.board[i] != 0:
                correct_pos = 8 if self.board[i] == 0 else self.board[i] - 1
                s_row = int(i / 3)
                s_col = i % 3
                t_row = int(correct_pos / 3)
                t_col = correct_pos % 3
                manhattan += abs(s_row - t_row) + abs(s_col - t_col)

        return manhattan

    def to_pq_entry(self, count):
        """
            returns the tuple (priority, count, board)
        """
        return (self.moves + self.manhattan(), count, self)

    def __str__(self):
        """
            Same as print(self) except this returns a string
        """
        string = ''
        string = string + '+---+---+---+\n'
        for i in range(3):
            for j in range(3):
                tile = self.board[i * 3 + j]
                string = string + '| {} '.format(' ' if tile == 0 else tile)
            string = string + '|\n'
            string = string + '+---+---+---+\n'
        return string

    def __eq__(self, other):
        """
            check if self == other
        """
        if other is None:
            return False
        else:
            return self.board == other.board

    def get_previous_states(self):
        """
            return a list of previous states by going up the state space tree
        """
        states = [self]
        prev = self.previous
        while prev is not None:
            states.append(prev)
            prev = prev.previous

        states.reverse()
        return states

def diff_boards_str(board1, board2):
    """
        returns a string describing move made from board1 to board2
    """
    if board1 is None:
        return 'Intial State'

    if board2 is None:
        return ''

    blank1 = board1.find_blank()
    blank2 = board2.find_blank()

    s_row = int(blank1 / 3)
    s_col = blank1 % 3
    t_row = int(blank2 / 3)
    t_col = blank2 % 3

    dx = s_col - t_col
    dy = s_row - t_row

    if dx == 1:
        return 'Move Left'
    if dx == -1:
        return 'Move Right'
    if dy == 1:
        return 'Move Up'
    if dy == -1:
        return 'Move Down'

def solve(initial_board):
    """
        returns a list of moves from 'initial_board' to goal state
            calculated using A* algorithm
    """
    queue = PriorityQueue()
    queue.put(initial_board.to_pq_entry(0))

    i = 1
    while not queue.empty():
        board = queue.get()[2]
        if not board.is_goal():
            for neighbour in board.neighbours():
                if neighbour != board.previous:
                    queue.put(neighbour.to_pq_entry(i))
                    i += 1
        else:
            return board.get_previous_states()

    return None


def main2(window):
    """
        Driver function to handle UI using curses.
    """
    initial = Board()
    window.insstr(0, 0, 'Enter starting state of the board: ')
    window.insstr(1, 0, str(initial))
    window.insstr(8, 0, 'Controls: Up, Down, Left, Right to move, Enter to solve')
    ch = window.getch()
    while str(ch) != '10':
        if ch == curses.KEY_UP:
            # Move blank up
            initial.move_blank('up')
        if ch == curses.KEY_DOWN:
            # Move blank down
            initial.move_blank('down')
        if ch == curses.KEY_LEFT:
            # Move blank left
            initial.move_blank('left')
        if ch == curses.KEY_RIGHT:
            # Move blank right
            initial.move_blank('right')
        window.insstr(1, 0, str(initial))
        ch = window.getch()
        window.refresh()

    moves = solve(initial)
    prev = None
    window.clear()
    for move in moves:
        window.clear()
        window.insstr(0, 0, 'Solving puzzle: ')
        window.insstr(1, 0, str(move))
        window.insstr(8, 0, diff_boards_str(prev, move))
        window.refresh()
        time.sleep(1)
        prev = move

    window.insstr(9, 0, 'Puzzle solved.')
    window.getch()

if __name__ == '__main__':
    curses.wrapper(main2)