class EightPuzzle:
    GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)  # 0 = blank

    def __init__(self, initial_state):
        self.initial_state = initial_state

    def actions(self, state):
        blank = state.index(0)
        row, col = divmod(blank, 3)
        moves = []
        if row > 0:
            moves.append("UP")
        if row < 2:
            moves.append("DOWN")
        if col > 0:
            moves.append("LEFT")
        if col < 2:
            moves.append("RIGHT")
        return moves

    def result(self, state, action):
        blank = state.index(0)
        row, col = divmod(blank, 3)
        delta = {
            "UP": -3, "DOWN": 3, "LEFT": -1, "RIGHT": 1,
        }[action]
        target = blank + delta
        state = list(state)
        state[blank], state[target] = state[target], state[blank]
        return tuple(state)

    def goal_test(self, state):
        return state == self.GOAL

    def cost(self, state, action, next_state):
        return 1


if __name__ == "__main__":
    start = (1, 2, 3, 4, 5, 6, 7, 0, 8)  # one move from solved
    puzzle = EightPuzzle(start)
    plan = iterative_deepening(puzzle, max_depth=10)
    print("Plan:", plan)
