Resolvendo um clássico com código: O problema das 8 rainhas

				
					# Instalar imagemagick (uma vez no notebook)
!apt-get install imagemagick

# Importações
import matplotlib.pyplot as plt
from matplotlib import animation
from IPython.display import HTML, display
from google.colab import files

# Variáveis globais
states = []
actions = []

def save_state(board, action_type):
    states.append([row.copy() for row in board])
    actions.append(action_type)

def draw_board(state, action, ax, frame_idx, total_frames):
    ax.clear()

    # Desenhar o tabuleiro
    for i in range(8):
        for j in range(8):
            color = 'white' if (i + j) % 2 == 0 else 'gray'
            ax.add_patch(plt.Rectangle((j, 7-i), 1, 1, color=color))

    # Desenhar rainhas
    for i in range(8):
        for j in range(8):
            if state[i][j] == 1:
                if action == "inicial" and states[0][i][j] == 1:
                    queen_color = 'blue'
                elif action == "remover":
                    queen_color = 'gold'
                else:
                    queen_color = 'red'
                ax.text(j + 0.5, 7-i + 0.5, '♛', fontsize=24,
                        ha='center', va='center', color=queen_color)

    # Barra de progresso SUAVE
    progress = frame_idx / total_frames
    ax.add_patch(plt.Rectangle((0, -0.5), 8 * progress, 0.3, color='green'))

    # Texto do progresso
    percent = int(progress * 100)
    ax.text(4, -0.9, f"Progresso: {percent}%", fontsize=12,
            ha='center', va='center', color='black')

    ax.set_xlim(0, 8)
    ax.set_ylim(-1.5, 8)
    ax.axis('off')

def solve(board, row, colunas_ocupadas, diag1_ocupadas, diag2_ocupadas):
    if row >= 8:
        return True

    if any(board[row]):
        return solve(board, row + 1, colunas_ocupadas, diag1_ocupadas, diag2_ocupadas)

    for col in range(8):
        if not colunas_ocupadas[col] and not diag1_ocupadas[row + col] and not diag2_ocupadas[row - col + 7]:
            board[row][col] = 1
            colunas_ocupadas[col] = diag1_ocupadas[row + col] = diag2_ocupadas[row - col + 7] = True
            save_state(board, "colocar")

            if solve(board, row + 1, colunas_ocupadas, diag1_ocupadas, diag2_ocupadas):
                return True

            # backtrack
            board[row][col] = 0
            colunas_ocupadas[col] = diag1_ocupadas[row + col] = diag2_ocupadas[row - col + 7] = False
            save_state(board, "remover")

    return False

def main():
    global states, actions
    board = [[0 for _ in range(8)] for _ in range(8)]

    print("Digite a posição inicial da primeira rainha:")
    initial_row = int(input("Linha (1 a 8): "))-1
    initial_col = int(input("Coluna (1 a 8): "))-1

    if not (0 <= initial_row <= 7 and 0 <= initial_col <= 7):
        print("Posição inválida!")
        return

    colunas_ocupadas = [False] * 8
    diag1_ocupadas = [False] * 15
    diag2_ocupadas = [False] * 15

    board[initial_row][initial_col] = 1
    colunas_ocupadas[initial_col] = True
    diag1_ocupadas[initial_row + initial_col] = True
    diag2_ocupadas[initial_row - initial_col + 7] = True
    save_state(board, "inicial")

    if solve(board, 0, colunas_ocupadas, diag1_ocupadas, diag2_ocupadas):
        print("Solução encontrada!")
    else:
        print("Não foi possível encontrar uma solução a partir dessa posição.")

    # DUPLICAR o último estado para "pausar" a solução final
    num_copies = 6  # 4 cópias de 500ms = 2000ms
    for _ in range(num_copies):
        states.append(states[-1])
        actions.append("final")

    # INTERPOLAR frames para suavidade
    frames_per_move = 5  # 5 frames suaves por ação
    new_states = []
    new_actions = []

    for i in range(len(states) - 1):
        for interp in range(frames_per_move):
            new_states.append(states[i])
            new_actions.append(actions[i])

    # Adiciona o último frame
    new_states.append(states[-1])
    new_actions.append(actions[-1])

    states[:] = new_states
    actions[:] = new_actions

    # Criar animação
    fig, ax = plt.subplots()

    def update(frame_idx):
        draw_board(states[frame_idx], actions[frame_idx], ax, frame_idx, len(states)-1)

    ani = animation.FuncAnimation(fig, update, frames=len(states), interval=100)  # 100ms entre frames suaves

    # Salvar como GIF
    gif_path = "/content/solucao_8rainhas.gif"
    ani.save(gif_path, writer='imagemagick', fps=10)  # fps ajustado conforme suavidade

    print(f"GIF salvo em: {gif_path}")

    plt.close(fig)

    # Mostrar o GIF
    display(HTML(f'<img decoding="async" src="{gif_path}">'))

    # Oferecer download
    files.download(gif_path)

# Executar
animation_html = main()