E11 Sudoku
O uso de tabelas de símbolos frequentemente simplifica a implementação de algoritmos. Entretanto, é importante observar que implementações genéricas de tais tabelas levam a objetos mais complexos. Assim, em situações específicas, vale a pena usar implementações específicas mais simples. Este exercício ilustra esse fato.
Resolução de instâncias de Sudoku com backtracking. O programa SudokuSET.java dado abaixo resolve instâncias do Sudoku usando backtracking. SudokuSET.java encontra todas as soluções para a instância dada. Para refrescar sua memória, veja
https://www.ime.usp.br/~yoshi/Sedgewick/Algs4th/Slides/67CombinatorialSearch.pdf
(páginas 22 a 29). Leia o programa SudokuSET.java e note que ele usa vários objetos do tipo SET<Integer> para que, em cada instante da busca, saibamos quais números ocorrem em cada linha, coluna e bloco do tabuleiro de Sudoku.
Você pode ler sobre SET em
https://algs4.cs.princeton.edu/35applications/
e páginas 489 e 490 de S&W.
Exemplos de execução
$ java-algs4 SudokuSET < in0.txt
7 2 8 9 4 6 3 1 5
9 3 4 2 5 1 6 7 8
5 1 6 7 3 8 2 4 9
1 4 7 5 9 3 8 2 6
3 6 9 4 8 2 1 5 7
8 5 2 1 6 7 4 9 3
2 9 3 6 1 5 7 8 4
4 8 1 3 7 9 5 6 2
6 7 5 8 2 4 9 3 1
1 solution(s)
$ java-algs4 SudokuSET . < in1.txt
1 solution(s)
$ java-algs4 SudokuSET . < in2.txt
10 solution(s)
$ java-algs4 SudokuSET . < in3.txt
Invalid instance
$
Com a entrada in5.txt, Sudoku.java é um tanto demorado:
$ time java-algs4 SudokuSET . < in5.txt
31834 solution(s)
real 15m22.735s
user 15m21.861s
sys 0m2.896s
$
Sua tarefa. Em SudokuSET.java, usamos objetos do tipo SET<Integer> para armazenar subconjuntos de \(\{1,\dots,9\}\). Embora conceitualmente isso não seja um problema, é fácil ver que o uso de SET.java é um /overkill/, pois SET.java é implementado para lidar com conjuntos de objetos genéricos (comparable) usando árvores rubro-negras.
Implemente um tipo de nome SET9 para lidar com subconjuntos de $\{1,\dots,9\}$. Sua implementação, feita em SET9.java, deve ser compatível com o programa Sudoku.java dado abaixo. Com uma boa implementação em SET9.java, Sudoku.java será bem mais rápido que SudokuSET.java:
$ time java-algs4 Sudoku . < in5.txt
31834 solution(s)
real 3m4.016s
user 3m3.434s
sys 0m0.473s
$
Observação. Você pode implementar SET9.java adequadamente em umas 20 linhas e com menos de 350 caracteres. Seu SET9.java deve ser mais ou menos desse tamanho.
Entrega. Basta entregar seu programa SET9.java.
- 20 giugno 2022, 19:15
- 20 giugno 2022, 19:15