# Notes from Wednesday, November 8

# A program to solve the 8-puzzle problem using heuristic search.

from HeuristicSearch import search

class EightPuzzleState:

    def __init__(self, board):
        self.board = board[:]
        self.blank = board.index(' ')

    def __str__(self):
        (nw, n, ne, w, c, e, sw, s, se) = self.board
        return '\n%s %s %s\n%s %s %s\n%s %s %s\n' % (nw, n, ne, w, c, e, sw, s, se)

    # allows EightPuzzleState objects to be compared using the == operator
    def __eq__(self, other):
        return self.board == other.board

    # swaps the blank with the tile at position tilePos
    def swapBlank(self, tilePos):
        b = self.blank
        self.board[b], self.board[tilePos] = self.board[tilePos], self.board[b]
        self.blank = tilePos

    # operators: move blank up, down, left, or right
    def up(self):
        if self.blank in [0, 1, 2]:
            return None
        else:
            tilePos = self.blank - 3
            action = 'slide %d down' % self.board[tilePos]
            newState = EightPuzzleState(self.board)
            newState.swapBlank(tilePos)
            return (action, newState)

    def down(self):
        if self.blank in [6, 7, 8]:
            return None
        else:
            tilePos = self.blank + 3
            action = 'slide %d up' % self.board[tilePos]
            newState = EightPuzzleState(self.board)
            newState.swapBlank(tilePos)
            return (action, newState)

    def left(self):
        if self.blank in [0, 3, 6]:
            return None
        else:
            tilePos = self.blank - 1
            action = 'slide %d to the right' % self.board[tilePos]
            newState = EightPuzzleState(self.board)
            newState.swapBlank(tilePos)
            return (action, newState)

    def right(self):
        if self.blank in [2, 5, 8]:
            return None
        else:
            tilePos = self.blank + 1
            action = 'slide %d to the left' % self.board[tilePos]
            newState = EightPuzzleState(self.board)
            newState.swapBlank(tilePos)
            return (action, newState)

    def applyOperators(self):
        results = [self.up(), self.down(), self.left(), self.right()]
        return [r for r in results if r is not None]

#----------------------------------------------------------------------
# heuristic function - sums up the displacement of each tile from
# its desired goal position

def distance(state, goal):
    total = 0
    for tile in range(1, 9):
        total = total + abs(row(tile, state) - row(tile, goal))
        total = total + abs(col(tile, state) - col(tile, goal))
    return total

def row(tile, state):
    return state.board.index(tile) / 3
    
def col(tile, state):
    return state.board.index(tile) % 3

#----------------------------------------------------------------------

startA = EightPuzzleState([1, 3, ' ', 8, 2, 4, 7, 6, 5])  # 2 steps
startB = EightPuzzleState([1, 3, 4, 8, 6, 2, ' ', 7, 5])  # 6 steps
startC = EightPuzzleState([1, 3, ' ', 4, 2, 5, 8, 7, 6])  # 8 steps
startD = EightPuzzleState([7, 1, 2, 8, ' ', 3, 6, 5, 4])  # 10 steps
startE = EightPuzzleState([8, 1, 2, 7, ' ', 4, 6, 5, 3])  # 10 steps
startF = EightPuzzleState([2, 6, 3, 4, ' ', 5, 1, 8, 7])  # 12 steps
startG = EightPuzzleState([7, 3, 4, 6, 1, 5, 8, ' ', 2])  # 15 steps
startH = EightPuzzleState([7, 4, 5, 6, ' ', 3, 8, 1, 2])  # 20 steps

goal = EightPuzzleState([1, 2, 3, 8, ' ', 4, 7, 6, 5])

# this one is much harder (27 steps)
startJ = EightPuzzleState([7, 5, 6, 4, 8, ' ', 1, 2, 3])
goalJ  = EightPuzzleState([1, 2, 3, 4, 5, 6, 7, 8, ' '])

# this one is even harder (29 steps)
startK = EightPuzzleState([3, 1, 7, 6, 4, ' ', 8, 2, 5])
goalK  = EightPuzzleState([1, 2, 3, 4, 5, 6, 7, 8, ' '])

def main():
    search(startH, goal, distance)