Problemas de Satisfação de Restrições (PSR)

Formulação e Resolução com Backtracking e Propagação de Restrições

Autor

Márcio Nicolau

Data de Publicação

16 de outubro de 2025

Introdução

Até agora, exploramos como os agentes inteligentes podem encontrar caminhos em espaços de estados usando estratégias de busca cega e informada. No entanto, muitos problemas em Inteligência Artificial não se encaixam naturalmente no paradigma de encontrar uma “sequência de ações” para um estado objetivo. Em vez disso, eles envolvem a busca por um estado (uma configuração de variáveis) que satisfaça um conjunto de restrições específicas. Estes são os Problemas de Satisfação de Restrições (PSRs).

Nesta aula, definiremos o que são PSRs, como formalizá-los e, mais importante, como utilizar técnicas poderosas como a busca com backtracking e a propagação de restrições para resolvê-los de forma eficiente. PSRs são onipresentes em áreas como planejamento, agendamento, visão computacional e projeto de circuitos.

Objetivo de Aprendizagem

Ao final desta aula, você será capaz de:

Definir e identificar os componentes de um Problema de Satisfação de Restrições (PSR).
Formular problemas do mundo real como PSRs.
Compreender e aplicar o algoritmo de busca com Backtracking para resolver PSRs.
Entender a importância e aplicar técnicas de aprimoramento do Backtracking, como ordenação de variáveis, ordenação de valores e propagação de restrições (Forward Checking).
Implementar soluções para PSRs simples em Python utilizando essas técnicas.

O que são Problemas de Satisfação de Restrições (PSR)?

Um Problema de Satisfação de Restrições (PSR) é um modelo para problemas nos quais o objetivo é encontrar uma atribuição de valores para um conjunto de variáveis, de forma que todas as restrições sobre essas variáveis sejam satisfeitas (Russell; Norvig, 2004, p. 136).

Componentes de um PSR

Formalmente, um PSR é definido por três componentes principais:

Variáveis (V): Um conjunto de variáveis \(V = \{V_1, V_2, \dots, V_n\}\).
Domínios (D): Para cada variável \(V_i\), há um domínio \(D_i\), que é um conjunto de valores possíveis que \(V_i\) pode assumir.
Restrições (C): Um conjunto de restrições \(C = \{C_1, C_2, \dots, C_m\}\). Cada restrição \(C_j\) especifica uma combinação permitida de valores para um subconjunto das variáveis.

Uma solução para um PSR é uma atribuição consistente (sem violação de restrições) de um valor de seu domínio para cada variável.

Exemplos Clássicos de PSRs

Coloração de Mapas: Atribuir cores a regiões de um mapa de forma que regiões adjacentes tenham cores diferentes.
Problema das N-Rainhas: Posicionar N rainhas em um tabuleiro N x N de xadrez de forma que nenhuma rainha ataque outra.
Sudoku: Preencher uma grade 9x9 com dígitos de 1 a 9, de forma que cada linha, coluna e subgrade 3x3 contenha todos os dígitos sem repetição.
Agendamento: Agendar tarefas em horários e recursos limitados.

Grafo de Restrições

Um PSR pode ser visualizado como um grafo de restrições, onde:

Os nós do grafo são as variáveis.
As arestas conectam variáveis que compartilham uma restrição.

graph TD
    A["Problema de Satisfação de Restrições (PSR)"] --> V["Variáveis (V)"];
    V --> D["Domínios (D)"];
    V --> C["Restrições (C)"];

    D -- "Valores possíveis para V" --> V;
    C -- "Restringe valores de V" --> V;

    style A fill:#f9f,stroke:#333,stroke-width:2px;
    style V fill:#add8e6,stroke:#333,stroke-width:2px;
    style D fill:#f0e68c,stroke:#333,stroke-width:2px;
    style C fill:#ffa07a,stroke:#333,stroke-width:2px;

Figura 1: Componentes de um Problema de Satisfação de Restrições (PSR)

Formalizando um PSR: Exemplo de Coloração de Mapas

Vamos usar o problema de colorir o mapa da Austrália para ilustrar a formalização de um PSR.

Problema: Colorir cada estado do mapa da Austrália com uma de três cores (vermelho, verde, azul) de forma que estados adjacentes não tenham a mesma cor.

graph TD
    WA("Western Australia") --- NT("Northern Territory");
    WA --- SA("South Australia");
    NT --- SA;
    NT --- Q("Queensland");
    SA --- Q;
    SA --- NSW("New South Wales");
    SA --- V("Victoria");
    Q --- NSW;
    NSW --- V;

    subgraph "Legenda"
        style WA fill:#add8e6,stroke:#333,stroke-width:2px;
        style NT fill:#add8e6,stroke:#333,stroke-width:2px;
        style SA fill:#add8e6,stroke:#333,stroke-width:2px;
        style Q fill:#add8e6,stroke:#333,stroke-width:2px;
        style NSW fill:#add8e6,stroke:#333,stroke-width:2px;
        style V fill:#add8e6,stroke:#333,stroke-width:2px;
    end

Figura 2: Mapa da Austrália com Grafo de Restrições para Coloração

Componentes do PSR:

Variáveis (V):
- \(\{WA, NT, SA, Q, NSW, V, T\}\) (os estados australianos, onde T é Tasmânia, mas não é adjacente a nenhum outro e pode ser ignorado por enquanto para simplificar o grafo conectado).
- Vamos usar apenas as variáveis do grafo acima: \(\{WA, NT, SA, Q, NSW, V\}\).
Domínios (D): Para cada variável \(V_i\), o domínio é \(D_i = \{\text{vermelho, verde, azul}\}\).
Restrições (C): Para cada par de estados adjacentes, eles devem ter cores diferentes.
- \(C(WA, NT): WA \ne NT\)
- \(C(WA, SA): WA \ne SA\)
- \(C(NT, SA): NT \ne SA\)
- \(C(NT, Q): NT \ne Q\)
- \(C(SA, Q): SA \ne Q\)
- \(C(SA, NSW): SA \ne NSW\)
- \(C(SA, V): SA \ne V\)
- \(C(Q, NSW): Q \ne NSW\)
- \(C(NSW, V): NSW \ne V\)

Técnicas de Resolução de PSRs

A resolução de PSRs pode ser vista como um problema de busca. Um estado na busca é uma atribuição parcial de valores às variáveis, e uma ação é atribuir um valor a uma variável não atribuída.

Busca com Backtracking (Backtracking Search)

A Busca com Backtracking é o algoritmo básico para resolver PSRs. É uma forma de Busca em Profundidade (DFS) que, em cada nó da árvore de busca, tenta atribuir um valor a uma variável. Se a atribuição viola alguma restrição, ela retrocede (backtracks) e tenta outro valor.

Funcionamento

Atribuição Incremento: O algoritmo atribui um valor a uma variável por vez.
Verificação de Restrições: Após cada atribuição, verifica se alguma restrição é violada.
Backtracking: Se uma atribuição viola uma restrição, o algoritmo “desfaz” a atribuição e tenta outro valor para a mesma variável. Se não houver mais valores para tentar, ele retrocede para a variável anterior e muda sua atribuição.

Pseudocódigo Básico (Russell; Norvig, 2004, p. 139)

function BACKTRACKING-SEARCH(csp) returns solution or failure
    return BACKTRACK( {}, csp )

function BACKTRACK(assignment, csp) returns solution or failure
    if assignment is complete then return assignment
    var <- SELECT-UNASSIGNED-VARIABLE(csp)
    for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
        if value is consistent with assignment and csp's constraints then
            add {var = value} to assignment
            result <- BACKTRACK(assignment, csp)
            if result is not failure then return result
            remove {var = value} from assignment
    return failure

SELECT-UNASSIGNED-VARIABLE: Escolhe a próxima variável a ser atribuída.
ORDER-DOMAIN-VALUES: Decide a ordem em que os valores serão testados para a variável selecionada.

Limitações do Backtracking Simples

O backtracking simples pode ser muito ineficiente. Ele pode perder muito tempo explorando caminhos de busca que são obviamente inválidos, o que é conhecido como “thrashing” (perder tempo repetindo os mesmos erros, pois não “lembra” de onde veio o problema).

Melhorando o Backtracking

Podemos melhorar significativamente a eficiência do backtracking adicionando heurísticas e técnicas de propagação de restrições.

1. Ordem de Seleção de Variáveis (Variable Ordering)

Qual variável devemos atribuir primeiro?

MRV (Minimum Remaining Values - Variável Mais Restrita): Escolha a variável com o menor número de valores legais restantes em seu domínio. Isso tende a identificar falhas mais cedo.
Heurística do Grau (Degree Heuristic): Se houver um empate no MRV, escolha a variável que está envolvida no maior número de restrições com variáveis ainda não atribuídas. Isso tenta “desprender” as variáveis mais conectadas primeiro.

2. Ordem de Seleção de Valores (Value Ordering)

Uma vez que uma variável foi selecionada, qual valor devemos tentar primeiro?

LCV (Least Constraining Value - Valor Menos Restritivo): Escolha o valor que descarta o menor número de valores nos domínios das variáveis adjacentes (que ainda não foram atribuídas). Isso maximiza as chances de encontrar uma solução sem precisar de backtracking.

3. Propagação de Restrições (Constraint Propagation)

A propagação de restrições remove valores dos domínios das variáveis que são inconsistentes com as atribuições atuais ou com outras restrições. Isso ajuda a detectar falhas mais cedo e a reduzir o espaço de busca.

Forward Checking (FC): Após atribuir um valor a uma variável X, o Forward Checking verifica cada variável Y não atribuída que é adjacente a X (ou seja, tem uma restrição com X). Para cada Y, ele remove do seu domínio quaisquer valores que sejam inconsistentes com a atribuição de X. Se o domínio de Y se tornar vazio, a atribuição de X é inconsistente, e o algoritmo retrocede.

    %%| label: fig-forward-checking
    %%| fig-cap: |
    %%|     Propagação de Restrições: Forward Checking
    %%| fig-width: 8
    %%| fig-height: 5

    graph TD
        A["Variável X Atribuída"] --> B{"Verifica Restrições com Vizinhos Não Atribuídos (Y)"};
        B --> C["Remove Valores Inconsistentes do Domínio de Y"];
        C --> D{"Domínio de Y Vazio?"};
        D -- "Sim" --> E["Inconsistência Detectada: Backtrack"];
        D -- "Não" --> F["Continua Busca"];

        style A fill:#add8e6,stroke:#333,stroke-width:2px;
        style B fill:#f0e68c,stroke:#333,stroke-width:2px;
        style C fill:#ffa07a,stroke:#333,stroke-width:2px;
        style D fill:#ffd700,stroke:#333,stroke-width:2px;
        style E fill:#ff6347,stroke:#333,stroke-width:2px;
        style F fill:#98fb98,stroke:#333,stroke-width:2px;

Arc Consistency (AC-3): Uma forma mais poderosa de propagação de restrições. Ela garante que cada arco (Xi, Xj) em um grafo de restrições seja consistente. Um arco (Xi, Xj) é consistente se, para cada valor x no domínio de Xi, existe pelo menos um valor y no domínio de Xj tal que a atribuição (Xi=x, Xj=y) satisfaz a restrição entre Xi e Xj. O AC-3 itera sobre os arcos, removendo valores inconsistentes até que nenhuma remoção possa ser feita (ou um domínio se torne vazio).

Exemplo: Problema das N-Rainhas com Backtracking e Forward Checking

O problema das N-Rainhas é um PSR clássico: posicionar N rainhas em um tabuleiro N x N de modo que nenhuma rainha ataque outra (nenhuma na mesma linha, coluna ou diagonal).

Variáveis: \(Q_1, \dots, Q_N\), onde \(Q_i\) é a linha da rainha na coluna \(i\).
Domínios: Para cada \(Q_i\), \(D_i = \{1, \dots, N\}\) (as linhas possíveis).
Restrições: Para qualquer par de rainhas \((Q_i, Q_j)\) (com \(i \ne j\)):
- \(Q_i \ne Q_j\) (não na mesma linha)
- \(|Q_i - Q_j| \ne |i - j|\) (não na mesma diagonal)

Vamos implementar uma solução para o problema das N-Rainhas usando backtracking e Forward Checking.

N-Rainhas com Backtracking e Forward Checking em Python

def solve_n_queens(n):
    # Inicializa domínios para cada rainha (coluna)
    # domains[coluna] = set de linhas possíveis para aquela rainha
    domains = {col: set(range(n)) for col in range(n)}
    
    # current_assignment = {coluna: linha}
    current_assignment = {}
    
    # backtrack(col) tenta posicionar a rainha na coluna 'col'
    solutions = []

    def is_consistent(col, row, assignment):
        # Verifica se a nova rainha (col, row) é consistente com as rainhas já posicionadas
        for assigned_col, assigned_row in assignment.items():
            if assigned_row == row:  # Mesma linha
                return False
            if abs(assigned_col - col) == abs(assigned_row - row): # Mesma diagonal
                return False
        return True

    def forward_check(col, row, current_domains):
        # Cria uma cópia dos domínios para não modificar o original no caso de backtracking
        new_domains = {c: d.copy() for c, d in current_domains.items()}
        
        # O valor 'row' é atribuído à 'col'. Removemos 'row' do domínio de outras colunas se for inconsistente.
        for next_col in range(col + 1, n):
            # Remove a linha 'row' (mesma linha)
            if row in new_domains[next_col]:
                new_domains[next_col].discard(row)
            
            # Remove diagonais
            diag1 = row + (next_col - col) # Diagonal principal
            diag2 = row - (next_col - col) # Diagonal secundária

            if diag1 in new_domains[next_col]:
                new_domains[next_col].discard(diag1)
            if diag2 in new_domains[next_col]:
                new_domains[next_col].discard(diag2)
            
            # Se algum domínio ficar vazio, significa que essa atribuição levou a uma inconsistência
            if not new_domains[next_col]:
                return None # Indicia falha
        return new_domains

    def backtrack(col, current_assignment, current_domains):
        if col == n: # Todas as rainhas foram posicionadas
            solutions.append(dict(current_assignment)) # Adiciona uma cópia da solução
            return True # Encontrou uma solução (ou queremos todas, então continuamos)

        # Heurística MRV (Minimum Remaining Values) para selecionar a próxima variável
        # Para N-Rainhas, as colunas são fixas, então é mais simples selecionar a próxima coluna não atribuída.
        # No entanto, se o problema fosse mais genérico (e.g. posicionar N items em M slots), MRV seria útil.
        # Aqui, apenas selecionamos a próxima coluna 'col'.

        found_solution_in_this_branch = False
        
        # Ordem de valores: LCV (Least Constraining Value) não é trivial aqui.
        # Apenas iteramos sobre os valores possíveis para a linha na coluna 'col'.
        
        # Consideramos apenas os valores que ainda estão no domínio atual
        # após a propagação de restrições das rainhas anteriores.
        
        # Para DFS, podemos percorrer os valores em uma ordem qualquer.
        # Se usarmos `sorted(current_domains[col])`, a ordem é fixa.
        for row in sorted(list(current_domains[col])):
            if is_consistent(col, row, current_assignment):
                current_assignment[col] = row
                
                # Aplica Forward Checking
                updated_domains = forward_check(col, row, current_domains)

                if updated_domains is not None: # Se não houve falha no forward check
                    # print(f"Tentando ({col},{row}). Domínios após FC: {updated_domains}")
                    # Recursivamente chama backtrack para a próxima coluna
                    result = backtrack(col + 1, current_assignment, updated_domains)
                    if result:
                        found_solution_in_this_branch = True
                
                # Remove a atribuição para tentar o próximo valor (backtracking)
                del current_assignment[col]
        
        return found_solution_in_this_branch # Retorna True se pelo menos uma solução foi encontrada neste ramo

    # Inicia a busca
    backtrack(0, current_assignment, domains)
    return solutions

def print_board(solution, n):
    board = [['.' for _ in range(n)] for _ in range(n)]
    for col, row in solution.items():
        board[row][col] = 'Q'
    for r in board:
        print(" ".join(r))
    print("-" * (2 * n - 1))

if __name__ == "__main__":
    N = 4
    print(f"Resolvendo o problema das {N}-Rainhas com Backtracking e Forward Checking:\n")
    solutions = solve_n_queens(N)

    if solutions:
        print(f"Encontradas {len(solutions)} soluções para {N}-Rainhas:")
        for i, sol in enumerate(solutions):
            print(f"Solução {i+1}: {sol}")
            print_board(sol, N)
    else:
        print(f"Nenhuma solução encontrada para {N}-Rainhas.")

    N_large = 8
    print(f"\nResolvendo o problema das {N_large}-Rainhas (apenas a primeira solução):\n")
    solutions_large = solve_n_queens(N_large)
    if solutions_large:
        print(f"Encontrada 1 solução para {N_large}-Rainhas:")
        print_board(solutions_large, N_large)
    else:
        print(f"Nenhuma solução encontrada para {N_large}-Rainhas.")

A implementação demonstra como o forward_check atua para podar o espaço de busca. Quando um valor row é atribuído a uma rainha na col, o forward_check percorre as colunas futuras e remove as linhas que seriam atacadas. Se um domínio de alguma coluna futura se tornar vazio, sabemos que a atribuição atual é inviável, e o backtracking ocorre mais cedo, sem explorar caminhos que levariam a um beco sem saída.

Considerações Finais

Problemas de Satisfação de Restrições são uma forma poderosa e flexível de modelar uma vasta gama de desafios em IA. Enquanto o backtracking puro é uma estratégia de força bruta, a combinação com heurísticas de ordenação (MRV, Grau, LCV) e, crucialmente, com técnicas de propagação de restrições como o Forward Checking e Arc Consistency, transforma-o em um algoritmo prático e eficiente para resolver muitos PSRs complexos. A chave é a detecção precoce de inconsistências para evitar a exploração de ramos inúteis na árvore de busca.

Verificação de Aprendizagem

Responda às seguintes questões e implemente as tarefas propostas para solidificar seu entendimento.

Fundamentos de PSR:
1. Defina um Problema de Satisfação de Restrições (PSR) e liste seus três componentes principais.
2. Dê um exemplo de um problema do mundo real (diferente dos citados na aula) que pode ser formulado como um PSR. Identifique as variáveis, seus domínios e as restrições para seu exemplo.
Backtracking:
1. Explique o funcionamento básico do algoritmo de busca com Backtracking para resolver PSRs. Qual é a principal desvantagem do backtracking simples?
2. Por que as heurísticas de ordenação de variáveis (MRV e Grau) e de valores (LCV) são importantes para melhorar o desempenho do backtracking?
Propagação de Restrições:
1. Descreva o mecanismo do Forward Checking. Como ele ajuda a reduzir o espaço de busca em comparação com o backtracking simples?
2. Qual é a diferença conceitual entre Forward Checking e Arc Consistency (AC-3)? Quando você usaria um em vez do outro, considerando a complexidade?
Implementação e Análise: Considere o seguinte problema de criptoaritmética: TWO + TWO = FOUR. Cada letra deve ser um dígito único de 0 a 9. T e F não podem ser 0.
1. Formule este problema como um PSR:
  - Liste as variáveis.
  - Defina os domínios para cada variável.
  - Liste as restrições (iguais, diferentes, e a restrição aritmética).
2. Simulação de Backtracking com Forward Checking (Manual): Imagine que o algoritmo de backtracking está resolvendo este PSR. Se a primeira atribuição é T = 2:
  - Quais variáveis seriam afetadas pelo Forward Checking (ou seja, quais domínios seriam podados)?
  - Quais valores seriam removidos dos domínios dessas variáveis devido à restrição de dígitos únicos e à restrição \(T \ne 0\)?
  - Existe alguma inconsistência detectada imediatamente por esta primeira atribuição? (Ou seja, algum domínio fica vazio?)

Referências Bibliográficas

RUSSELL, Stuart J.; NORVIG, Peter. Inteligência Artificial: Um Enfoque Moderno. 2. ed. Rio de Janeiro: Prentice Hall, 2004.