import math

AI = "X"       # MAX player (AI goes first)
HUMAN = "O"    # MIN player
EMPTY = " "

# ------------------ Board Utilities ------------------

def print_board(board):
    print()
    for i in range(3):
        print(" | ".join(board[i]))
        if i < 2:
            print("--+---+--")
    print()


def ACTIONS(board):
    return [(i, j) for i in range(3) for j in range(3) if board[i][j] == EMPTY]


def RESULT(board, action, player):
    new_board = [row[:] for row in board]
    i, j = action
    new_board[i][j] = player
    return new_board


def winner(board):
    lines = []

    # rows and columns
    for i in range(3):
        lines.append(board[i])
        lines.append([board[0][i], board[1][i], board[2][i]])

    # diagonals
    lines.append([board[0][0], board[1][1], board[2][2]])
    lines.append([board[0][2], board[1][1], board[2][0]])

    for line in lines:
        if line[0] != EMPTY and line[0] == line[1] == line[2]:
            return line[0]

    return None


def TERMINAL_TEST(board):
    return winner(board) is not None or not ACTIONS(board)


def UTILITY(board):
    w = winner(board)
    if w == AI:
        return 1
    elif w == HUMAN:
        return -1
    else:
        return 0


# ------------------ Minimax ------------------

def MAX_VALUE(board):
    if TERMINAL_TEST(board):
        return UTILITY(board)

    v = -math.inf
    for action in ACTIONS(board):
        v = max(v, MIN_VALUE(RESULT(board, action, AI)))
    return v


def MIN_VALUE(board):
    if TERMINAL_TEST(board):
        return UTILITY(board)

    v = math.inf
    for action in ACTIONS(board):
        v = min(v, MAX_VALUE(RESULT(board, action, HUMAN)))
    return v


def MINIMAX_DECISION(board):
    best_value = -math.inf
    best_action = None

    for action in ACTIONS(board):
        value = MIN_VALUE(RESULT(board, action, AI))
        if value > best_value:
            best_value = value
            best_action = action

    return best_action


# ------------------ Game Loop ------------------

def play_game():
    board = [[EMPTY for _ in range(3)] for _ in range(3)]
    print("AI is X and plays first.")
    print("You are O.")
    print_board(board)

    # AI first move
    print("AI is thinking...")
    move = MINIMAX_DECISION(board)
    board = RESULT(board, move, AI)
    print_board(board)

    while True:
        # Human move
        row = int(input("Enter row (0-2): "))
        col = int(input("Enter col (0-2): "))

        if board[row][col] != EMPTY:
            print("Invalid move!")
            continue

        board[row][col] = HUMAN
        print_board(board)

        if TERMINAL_TEST(board):
            break

        # AI move
        print("AI is thinking...")
        move = MINIMAX_DECISION(board)
        board = RESULT(board, move, AI)
        print_board(board)

        if TERMINAL_TEST(board):
            break

    # Result
    w = winner(board)
    if w == AI:
        print("AI wins!")
    elif w == HUMAN:
        print("You win!")
    else:
        print("It's a draw!")


# ------------------ Run ------------------

if __name__ == "__main__":
    play_game()
import math

AI = "X"       # MAX player
HUMAN = "O"    # MIN player
EMPTY = " "

# ------------------ Utility Functions ------------------

def print_board(board):
    print()
    for i in range(3):
        print(" | ".join(board[i]))
        if i < 2:
            print("--+---+--")
    print()


def ACTIONS(board):
    actions = []
    for i in range(3):
        for j in range(3):
            if board[i][j] == EMPTY:
                actions.append((i, j))
    return actions


def RESULT(board, action, player):
    new_board = [row[:] for row in board]
    i, j = action
    new_board[i][j] = player
    return new_board


def winner(board):
    lines = []

    # rows & columns
    for i in range(3):
        lines.append(board[i])
        lines.append([board[0][i], board[1][i], board[2][i]])

    # diagonals
    lines.append([board[0][0], board[1][1], board[2][2]])
    lines.append([board[0][2], board[1][1], board[2][0]])

    for line in lines:
        if line[0] != EMPTY and line[0] == line[1] == line[2]:
            return line[0]

    return None


def TERMINAL_TEST(board):
    return winner(board) is not None or not ACTIONS(board)


def UTILITY(board):
    w = winner(board)
    if w == AI:
        return 1
    elif w == HUMAN:
        return -1
    else:
        return 0


# ------------------ Minimax ------------------

def MAX_VALUE(board):
    if TERMINAL_TEST(board):
        return UTILITY(board)

    v = -math.inf
    for action in ACTIONS(board):
        v = max(v, MIN_VALUE(RESULT(board, action, AI)))
    return v


def MIN_VALUE(board):
    if TERMINAL_TEST(board):
        return UTILITY(board)

    v = math.inf
    for action in ACTIONS(board):
        v = min(v, MAX_VALUE(RESULT(board, action, HUMAN)))
    return v


def MINIMAX_DECISION(board):
    best_value = -math.inf
    best_action = None

    for action in ACTIONS(board):
        value = MIN_VALUE(RESULT(board, action, AI))
        if value > best_value:
            best_value = value
            best_action = action

    return best_action


# ------------------ Game Loop ------------------

def play_game():
    board = [[EMPTY for _ in range(3)] for _ in range(3)]
    print("You are O. AI is X.")
    print_board(board)

    while True:
        # Human move
        row = int(input("Enter row (0-2): "))
        col = int(input("Enter col (0-2): "))

        if board[row][col] != EMPTY:
            print("Invalid move!")
            continue

        board[row][col] = HUMAN
        print_board(board)

        if TERMINAL_TEST(board):
            break

        # AI move
        print("AI is thinking...")
        move = MINIMAX_DECISION(board)
        board = RESULT(board, move, AI)
        print_board(board)

        if TERMINAL_TEST(board):
            break

    # Game result
    w = winner(board)
    if w == AI:
        print("AI wins!")
    elif w == HUMAN:
        print("You win!")
    else:
        print("It's a draw!")


# ------------------ Run ------------------

if __name__ == "__main__":
    play_game()
import heapq

# -----------------------------------------
# Grid (0 = free, 1 = blocked)
# -----------------------------------------
grid = [
    [0, 0, 0, 0],
    [1, 1, 0, 1],
    [0, 0, 0, 0],
    [0, 1, 1, 0]
]

rows, cols = 4, 4
start = (0, 0)
goal = (3, 3)


# -----------------------------------------
# Heuristic: Manhattan distance
# -----------------------------------------
def heuristic(cell):
    x1, y1 = cell
    x2, y2 = goal
    return abs(x1 - x2) + abs(y1 - y2)


# -----------------------------------------
# Reconstruct path
# -----------------------------------------
def get_path(parent, current):
    path = []
    while current is not None:
        path.append(current)
        current = parent[current]
    return path[::-1]


# -----------------------------------------
# Greedy Best-First Search
# f(n) = h(n)
# -----------------------------------------
def greedy_best_first():
    pq = []
    heapq.heappush(pq, (heuristic(start), start))

    visited = set()
    parent = {start: None}

    while pq:
        _, current = heapq.heappop(pq)

        if current == goal:
            return get_path(parent, current)

        visited.add(current)

        x, y = current
        for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            nx, ny = x + dx, y + dy
            neighbor = (nx, ny)

            if (0 <= nx < rows and 0 <= ny < cols and
                grid[nx][ny] == 0 and neighbor not in visited
                and neighbor not in parent):

                parent[neighbor] = current
                heapq.heappush(pq, (heuristic(neighbor), neighbor))

    return None


# -----------------------------------------
# A* Search
# f(n) = g(n) + h(n)
# -----------------------------------------
def a_star():
    pq = []
    heapq.heappush(pq, (heuristic(start), start))

    parent = {start: None}
    g_cost = {start: 0}
    visited = set()

    while pq:
        _, current = heapq.heappop(pq)

        if current == goal:
            return get_path(parent, current)

        visited.add(current)

        x, y = current
        for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            nx, ny = x + dx, y + dy
            neighbor = (nx, ny)

            if (0 <= nx < rows and 0 <= ny < cols and
                grid[nx][ny] == 0 and
                neighbor not in visited and
                neighbor not in parent):

                g_cost[neighbor] = g_cost[current] + 1
                f = g_cost[neighbor] + heuristic(neighbor)

                parent[neighbor] = current
                heapq.heappush(pq, (f, neighbor))

    return None


# -----------------------------------------
# Run
# -----------------------------------------
print("Greedy Best-First Path:")
print(greedy_best_first())

print("\nA* Path:")
print(a_star())