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.

• Compilação
• Execução
• Benchmarks
• Documentaçã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:

Assim, SUDOKU_SOLVER pode ser compilado com o seguinte comando:

$ ./run --build
# ou
$ ./run -b

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/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.

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:

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: 1813316

Total 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