SUDOKU_SOLVER é um programa que tem como objetivo encontrar uma solução para um quebra-cabeça de Sudoku representado por uma matriz 9x9, caso uma solução exista. Esse programa é o produto de um trabalho prático da disciplina de Introdução à Inteligência Artificial do Departamento de Ciência da Computação da UFMG.
O script run é responsável por gerenciar a compilação com o CMake e a execução do programa. Ele oferece várias opções para facilitar diferentes operações relacionadas ao projeto. A tabela abaixo apresenta essas opções:
Parâmetro do script run | Descrição |
|---|---|
-h, --help | Exibe uma mensagem de ajuda |
-b, --build | Executa a compilação |
-d, --debug | Compila o projeto em modo de depuração (debug mode) |
-e, --exec | Executa o programa |
-c, --clean | Limpa os artefatos gerados pelo CMake, como os diretórios de compilação e os binários |
-t, --test | Executa os testes unitários |
-v, --valgrind | Executa testes com Valgrind para verificar vazamentos e o uso de memória |
-x <args>, --exec_args <args> | Permite passar argumentos adicionais para o programa. Pode ser utilizado com as flags -e e -v |
Assim, SUDOKU_SOLVER pode ser compilado com o seguinte comando:
$ ./run --build
# ou
$ ./run -bA execução do programa pode ser feita com o comando:
$ ./run -e -x <program params> # Executa o programa com a passagem de parâmetrosTambém é possível executar o binário do programa diretamente, por exemplo:
$ bin/Release/sudoku_solver <program params>SUDOKU_SOLVER espera a passagem dos seguintes parâmetros:
- uma letra maiúscula que define qual algoritmo de busca em espaços de estado será empregado para encontrar a solução
- a matriz inicial do Sudoku.
A tabela abaixo apresenta todos os algoritmos de busca implementados.
| Parâmetro | Descrição |
|---|---|
B <matrix> | Busca uma solução com o algoritmo Breadth-First Search |
I <matrix> | Busca uma solução com o algoritmo Iterative Deepening Depth-First Search |
U <matrix> | Busca uma solução com o algoritmo Uniform-Cost Search |
A <matrix> | Busca uma solução com o algoritmo A* Search |
G <matrix> | Busca uma solução com o algoritmo Greedy Best-First Search |
A matriz é dada por 9 conjuntos de 9 números, onde o primeiro conjunto é a primeira linha da matriz, o segundo é a segunda linha etc.
Exemplo de execução:
# linha 1 linha 2 linha 3 linha 4 linha 5 linha 6 linha 7 linha 8 linha 9
$ ./run -e -x U 800000000 003600000 070090200 050007000 000045700 000100030 001000068 008500010 090000400Zero representa as posições que precisam ser preenchidas.
O comando acima passa a seguinte matriz para o programa:
8 0 0 | 0 0 0 | 0 0 0
0 0 3 | 6 0 0 | 0 0 0
0 7 0 | 0 9 0 | 2 0 0
------+-------+------
0 5 0 | 0 0 7 | 0 0 0
0 0 0 | 0 4 5 | 7 0 0
0 0 0 | 1 0 0 | 0 3 0
------+-------+------
0 0 1 | 0 0 0 | 0 6 8
0 0 8 | 5 0 0 | 0 1 0
0 9 0 | 0 0 0 | 4 0 0Saída esperada do programa para a matriz de entrada:
Solution found :')
8 1 2 | 7 5 3 | 6 4 9
9 4 3 | 6 8 2 | 1 7 5
6 7 5 | 4 9 1 | 2 8 3
------+-------+------
1 5 4 | 2 3 7 | 8 9 6
3 6 9 | 8 4 5 | 7 2 1
2 8 7 | 1 6 9 | 5 3 4
------+-------+------
5 2 1 | 9 7 4 | 3 6 8
4 3 8 | 5 2 6 | 9 1 7
7 9 6 | 3 1 8 | 4 5 2
Algorithm: UCS
Total time: 16071 ms
Total expanded states: 1813316Total expanded states é a quantidade de estados explorados.
A discussão dos resultados obtidos durante os testes podem ser lidos na seção 4 da documentação.
A primeira versão da documentação, bem como o enunciado deste trabalho pode ser lida aqui