🧠 CSP Solver para Palavras Cruzadas

Este projeto implementa um resolvedor de palavras cruzadas modelado como um Problema de Satisfação de Restrições (CSP). O objetivo é preencher automaticamente grids com palavras de uma lista fornecida, utilizando técnicas e heurísticas aprendidas na disciplina de Inteligência Artificial (PUCRS, 2025).

📋 Descrição do Problema

O sistema deve preencher espaços vazios (?) em um grid, utilizando palavras de um dicionário externo, sem modificar o grid original ou a lista de palavras. O preenchimento precisa respeitar regras de cruzamento (como em palavras cruzadas) e evitar conflitos entre palavras.

⚙️ Técnicas Utilizadas

A solução foi construída a partir de um CSP personalizado, utilizando:

• Backtracking como estratégia principal de busca.
• Forward Checking para restringir domínios após cada escolha.
• Heurística MRV (Minimum Remaining Values) para priorizar variáveis com menos opções.
• Heurística Degree para desempate entre variáveis com mesmo domínio, priorizando as mais restritas.
• Restrições binárias para garantir que as palavras se cruzem corretamente e não sejam repetidas.

📁 Estrutura do Projeto

📦csp_solver/
├── CspSolver.py   # Script principal: leitura, resolução e escrita de saída
├── csp.py         # Implementação completa do CSP customizado
├── FileHandler.py # Módulo auxiliar para leitura e escrita de arquivos
├── Test-Grids/    # Grids fornecidos para testes
├── Test-Words/    # Lista de palavras
├── Output-Grids/  # Geração dos grids preenchidos
├── Logs-Grids/    # Arquivos de log detalhado das execuções

🧪 Execução

Ao rodar o script cspSolver.py, o sistema solicitará a escolha de um dos grids de teste. Após a seleção:

1. O grid e a lista de palavras são lidos.
2. Os espaços a serem preenchidos ("slots") são detectados.
3. Os domínios são criados a partir das palavras, agrupadas por tamanho.
4. As variáveis e restrições são adicionadas ao CSP.
5. O algoritmo é executado com Forward Checking + MRV + Degree.
6. A solução encontrada é aplicada ao grid e salva em Output-Grids/.
7. Um log detalhado da execução é gerado em Logs-Grids/.

📝 Formato de Entrada

• Grids: arquivos .txt com caracteres . (bloqueado), ? (preenchível).
• Palavras: uma por linha, no arquivo lista_palavras.txt.

📄 Resultados

Todos os grids de teste foram resolvidos com sucesso dentro de um tempo de execução satisfatório. Destaque para o maior grid (35x48), que foi concluído em apenas 3,5 minutos. Os grids preenchidos e os logs detalhados da execução estão disponíveis nas pastas Output-Grids/ e Logs-Grids/.