SUDOKU_SOLVER

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.

Sumário

• Compilação
• Execução
• Benchmarks
• Documentação

Compilação

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 -b

Execução

A execução do programa pode ser feita com o comando:

$ ./run -e -x <program params> # Executa o programa com a passagem de parâmetros

Também é possível executar o binário do programa diretamente, por exemplo:

$ bin/Release/program <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 090000400

Zero 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 0

Saída esperada do programa para a matriz de entrada:

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

Total expanded states: 1813316

Total expanded states é a quantidade de estados explorados.

Benchmarks

• TODO

Documentação

A primeira versão da documentação, bem como o enunciado deste trabalho pode ser lida aqui.