def maze_successor(state):
    next_states = [(state[0] + 1, state[1]),
                   (state[0], state[1] + 1),
                   (state[0] - 1, state[1]),
                   (state[0], state[1] - 1)]
    next_states = [s for s in next_states if maze_allowed(s)]
    return next_states


def sudoku_successor(state):
    new_state = list(map(list, state))  # Convert state to a list of lists
    starting_point = [choose_best_subsquare(new_state), choose_best_rows(new_state), choose_best_column(new_state)]
    x, y, dummy = max(starting_point, key=lambda w: w[2])
    next_states = []
    for j in range(1, len(new_state) + 1):
        new_state[y][x] = j
        if sudoku_allowed((y, x, new_state)):
            next_states.append(tuple(map(tuple, new_state)))
    return next_states


def puzzle_successor(state):
    y, x = -1, -1
    for i in range(len(state)):
        for j in range(len(state[i])):
            if state[i][j] == 0:
                y, x = i, j
                break
    
    possible_moves = [(y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)]
    next_states = []

    for move in possible_moves:
        new_y, new_x = move
        if 0 <= new_y < len(state) and 0 <= new_x < len(state[0]):
            # make a copy of the state
            new_state = [list(row) for row in state]
            # swap tiles
            new_state[y][x], new_state[new_y][new_x] = new_state[new_y][new_x], new_state[y][x]
            # Convert state to a tuple of tuples
            new_state_tuple = tuple(tuple(row) for row in new_state)
            if puzzle_allowed(new_state_tuple):
                next_states.append(new_state_tuple)

    return next_states


def queens_successor(state):
    new_state = list(map(list, state))  # Convert state to a list of lists
    y = -1
    for i in range(len(new_state)):
        if sum(new_state[i]) == 0:
            y = i
            break
    next_states = []
    for j in range(len(new_state[0])):
        new_state[y] = [False] * len(new_state[y])
        new_state[y][j] = True
        if queens_allowed((y, j, new_state)):
            next_states.append(tuple(map(tuple, new_state)))
    return next_states


# Allowed moves Functions
def puzzle_allowed(state):
    return True



def maze_allowed(state):
    maze = [[' ', 'W', ' ', ' ', 'G'],
            [' ', 'W', ' ', 'W', ' '],
            [' ', 'W', ' ', ' ', ' '],
            [' ', ' ', 'W', 'W', ' '],
            [' ', ' ', ' ', ' ', ' ']]
    if state[0] >= len(maze[0]) or state[0] < 0:
        return False
    if state[1] >= len(maze) or state[1] < 0:
        return False
    return maze[state[0]][state[1]] == ' ' or maze[state[0]][state[1]] == 'G'


def sudoku_allowed(state):
    (y, x, grid) = state
    """I'm making the state a triple on this one"""
    # (y, x, z): x,y is the coordinate and z is the value in the square

    # check if still inside the box
    if y < 0 or y >= len(grid[0]):
        return False
    if x < 0 or x >= len(grid):
        return False

    # inspect columns and rows
    if ([row[x] for row in grid].count(grid[y][x]) > 1) or (grid[y].count(grid[y][x]) > 1):
        return False

    # inspect minor square in teh sudoku
    inner_x = ((x - (x % 3)), (x - (x % 3) + 3))
    inner_y = (y - (y % 3))
    inner_square = grid[inner_y][inner_x[0]:inner_x[1]] + grid[inner_y + 1][inner_x[0]:inner_x[1]] + \
                   grid[inner_y + 2][inner_x[0]:inner_x[1]]
    if inner_square.count(grid[y][x]) > 1:
        return False

    return True



def queens_allowed(state):
    """in this case the state is also y, x, grid"""
    y, x, grid = state

    # check if still inside the box
    if y < 0 or y >= len(grid):
        return False
    if x < 0 or x >= len(grid[0]):
        return False

    # inspect columns and rows for queens
    if (sum([row[x] for row in grid]) > 1) or (sum(grid[y]) > 1):
        return False

    # inspect diagonal
    for i in range(1, len(grid)):

        # positive diagonal
        if x - i >= 0 and y - i >= 0 and grid[y - i][x - i]:
            return False
        if x + i < len(grid[0]) and y + i < len(grid) and grid[y + i][x + i]:
            return False

        # negative diagonal
        if x - i >= 0 and y + i < len(grid) and grid[y + i][x - i]:
            return False
        if x + i < len(grid[0]) and y - i >= 0 and grid[y - i][x + i]:
            return False

    return True


# Helper Functions
def choose_best_rows(grid):
    best_row = -1
    x = -1
    min_empty = len(grid)
    for i in range(len(grid)):
        empty_cells = grid[i].count(0)
        if 0 < empty_cells < min_empty:
            best_row = i
            min_empty = empty_cells
            x = grid[i].index(0)
    return x, best_row, min_empty


def choose_best_column(grid):
    best_col = -1
    y = -1
    min_empty = len(grid)
    for i in range(len(grid)):
        col = [row[i] for row in grid]
        empty_cells = col.count(0)
        if 0 < empty_cells < min_empty:
            best_col = i
            min_empty = empty_cells
            y = col.index(0)
    return best_col, y, min_empty


def choose_best_subsquare(grid):
    x = -1
    y = -1
    best_val = len(grid)
    for down in range(0, 9, 3):
        for across in range(0, 9, 3):
            subsquare = [grid[i][across: across + 3] for i in range(down, down + 3)]
            zeros = sum([subsquare[i].count(0) for i in range(len(subsquare))])
            if 0 < zeros < best_val:
                best_val = zeros
                for j in range(len(subsquare)):
                    if 0 in subsquare[j]:
                        x = across + subsquare[j].index(0)
                        y = down + j
                        break
    return (x, y, best_val)