from collections import deque

def bfs_8puzzle(start, goal):
    # state as tuple: (1,2,3,4,5,6,7,8,0) where 0 is blank
    start = tuple(start)
    goal = tuple(goal)

    queue = deque([(start, 0, None)])  # state, cost, parent
    visited = {start}
    parent = {start: None}
    moves = {start: 0}

    while queue:
        state, cost, _ = queue.popleft()

        if state == goal:
            # reconstruct path
            path = []
            while state != start:
                path.append(state)
                state = parent[state]
            path.append(start)
            path.reverse()
            return path, cost

        # find blank position
        pos = state.index(0)
        row, col = pos // 3, pos % 3
        directions = [(-1,0), (1,0), (0,-1), (0,1)]  # up, down, left, right

        for dr, dc in directions:
            nr, nc = row + dr, col + dc
            if 0 <= nr < 3 and 0 <= nc < 3:
                new_pos = nr * 3 + nc
                new_state = list(state)
                new_state[pos], new_state[new_pos] = new_state[new_pos], new_state[pos]
                new_state = tuple(new_state)

                if new_state not in visited:
                    visited.add(new_state)
                    parent[new_state] = state
                    queue.append((new_state, cost + 1, state))

    return None, -1

# Example
start = [1, 2, 3, 0, 4, 6, 7, 5, 8]
goal  = [1, 2, 3, 7, 8, 4, 0, 6, 5]
path, steps = bfs_8puzzle(start, goal)
print(f"Solved in {steps} moves!")

import random
import math

def conflicts(board):
    n = len(board)
    conflicts = 0
    for i in range(n):
        for j in range(i+1, n):
            if board[i] == board[j] or abs(board[i] - board[j]) == j - i:
                conflicts += 1
    return conflicts

def simulated_annealing_8queens():
    board = list(range(8))
    random.shuffle(board)
    temp = 10000
    cooling_rate = 0.995

    while temp > 0.1:
        if conflicts(board) == 0:
            return board

        i = random.randint(0, 7)
        j = random.randint(0, 7)
        board[i], board[j] = board[j], board[i]

        delta_E = conflicts(board) - conflicts(list(reversed(board)))  # wait, better way:
        current_E = conflicts(board)
        board[i], board[j] = board[j], board[i]  # revert
        new_E = conflicts(board)
        delta_E = new_E - current_E

        if delta_E < 0 or random.random() < math.exp(-delta_E / temp):
            board[i], board[j] = board[j], board[i]  # accept move
        # else reject → board stays same

        temp *= cooling_rate

    return board if conflicts(board)==0 else None

solution = simulated_annealing_8queens()
print("Solution:", solution)

def is_valid(board, row, col, num):
    # Check row, col, 3x3 box
    for x in range(9):
        if board[row][x] == num or board[x][col] == num:
            return False
    start_row, start_col = row // 3 * 3, col // 3 * 3
    for i in range(3):
        for j in range(3):
            if board[i + start_row][j + start_col] == num:
                return False
    return True

def solve_sudoku(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1, 10):
                    if is_valid(board, row, col, num):
                        board[row][col] = num
                        if solve_sudoku(board):
                            return True
                        board[row][col] = 0  # backtrack
                return False
    return True  # solved

# Example puzzle
puzzle = [
    [5,3,0,0,7,0,0,0,0],
    [6,0,0,1,9,5,0,0,0],
    [0,9,8,0,0,0,0,6,0],
    [8,0,0,0,6,0,0,0,3],
    [4,0,0,8,0,3,0,0,1],
    [7,0,0,0,2,0,0,0,6],
    [0,6,0,0,0,0,2,8,0],
    [0,0,0,4,1,9,0,0,5],
    [0,0,0,0,8,0,0,7,9]
]

solve_sudoku(puzzle)
for row in puzzle:
    print(row)

def evaluate(board):
    # Check rows, cols, diagonals for win
    win_states = [
        [board[0][0], board[0][1], board[0][2]],
        [board[1][0], board[1][1], board[1][2]],
        [board[2][0], board[2][1], board[2][2]],
        [board[0][0], board[1][0], board[2][0]],
        [board[0][1], board[1][1], board[2][1]],
        [board[0][2], board[1][2], board[2][2]],
        [board[0][0], board[1][1], board[2][2]],
        [board[0][2], board[1][1], board[2][0]],
    ]
    if [1,1,1] in win_states: return 10
    if [-1,-1,-1] in win_states: return -10
    return 0

def game_over(board):
    return evaluate(board) != 0 or all(cell != 0 for row in board for cell in row)

def minimax(board, depth, alpha, beta, maximizing_player):
    if game_over(board) or depth == 0:
        return evaluate(board)

    if maximizing_player:
        max_eval = -float('inf')
        for i in range(3):
            for j in range(3):
                if board[i][j] == 0:
                    board[i][j] = 1
                    eval = minimax(board, depth-1, alpha, beta, False)
                    board[i][j] = 0
                    max_eval = max(max_eval, eval)
                    alpha = max(alpha, eval)
                    if beta <= alpha:
                        return max_eval
        return max_eval
    else:
        min_eval = float('inf')
        for i in range(3):
            for j in range(3):
                if board[i][j] == 0:
                    board[i][j] = -1
                    eval = minimax(board, depth-1, alpha, beta, True)
                    board[i][j] = 0
                    min_eval = min(min_eval, eval)
                    beta = min(beta, eval)
                    if beta <= alpha:
                        return min_eval
        return min_eval