E02 Passeio do cavalo
Este exercício é sobre passeios de cavalos em tabuleiros de xadrez:
https://en.wikipedia.org/wiki/Knight%27s_tour
Um exercício padrão de recursão/backtracking é escrever um programa que conta tais passeios. Você pode achar interessante estudar essa apresentação de S&W:
https://www.ime.usp.br/~yoshi/Sedgewick/Algs4th/Slides/67CombinatorialSearch.pdf
Você encontra alguns programas relacionados, relevantes para esse exercício, em
https://www.ime.usp.br/~yoshi/2019ii/ccm118/sandbox/2019.10.16/
Note que os programas na URL acima devem ser compilados e executados com javac-introcs e java-introcs. O texto abaixo supõe que você já deu uma olhada nos programas acima. Como o número total de passeios do cavalo em um tabuleiro por $N$ cresce muito rapidamente com $N$, em tempo razoável, nosso programa KnightTotal.java apenas determina a resposta para valores de $N$ pequenos, como $N = 5$. Para $N = 6$, o número total de passeios é 6637920 e assim listar todos esses passeios é um pouco demorado (quanto tempo você estima que KnightTotal.java demoraria para $N = 6$?).
Neste exercício, ficaremos satisfeitos em encontrar um caminho. O programa KnightOnePlain.java abaixo resolve esse problema:
$ java-algs4 KnightOnePlain 4
Found no tours
$ java-algs4 KnightOnePlain 5
1 6 15 10 21
14 9 20 5 16
19 2 7 22 11
8 13 24 17 4
25 18 3 12 23
$ java-algs4 KnightOnePlain 8
1 60 39 34 31 18 9 64
38 35 32 61 10 63 30 17
59 2 37 40 33 28 19 8
36 49 42 27 62 11 16 29
43 58 3 50 41 24 7 20
48 51 46 55 26 21 12 15
57 44 53 4 23 14 25 6
52 47 56 45 54 5 22 13
$
Ao tentar executar KnightOnePlain.java para $N = 9$, você verá que ele é demorado. O objetivo desse exercício é escrever um programa mais rápido que KnightOnePlain.java, explorando a ordem em que as chamadas recursivas são feitas.
Seu programa deve chamar-se KnightOneDeluxe.java. Para definir a ordem das chamadas recursivas, será necessário introduzirmos algumas definições. Considere o seguinte passeio parcial:
1 . 3 18 . . 13 16
4 19 . . 14 17 . .
. 2 . . . . 15 12
20 5 . . . . . .
. . . . . . 11 .
6 21 . . . . . .
. . . 8 . . . 10
. 7 . . . 9 . .
Considere agora a seguinte matriz:
- 3 - - 4 3 - -
- - 4 5 - - 4 3
4 - 4 4 7 6 - -
- - 6 6 5 6 5 4
3 6 4 6 7 7 - 3
- - 6 8 6 6 5 4
3 4 5 - 6 5 4 -
1 - 3 4 4 - 3 2
As posições marcadas com "-" são as posições já visitadas pelo cavalo. Na matriz acima, Um inteiro $X$ significa que, se o cavalo estivesse naquela posição, ele teria $X$ possibilidades para a próxima posição. Por exemplo, se o cavalo estivesse na posição R abaixo, ele poderia ir para as posições S, T e U (lembre que "-" significa que o cavalo já passou por lá):
- 3 - - 4 R - -
- - 4 S - - 4 U
4 - 4 4 T 6 - -
- - 6 6 5 6 5 4
3 6 4 6 7 7 - 3
- - 6 8 6 6 5 4
3 4 5 - 6 5 4 -
1 - 3 4 4 - 3 2
Assim, nesse exemplo, o valor de $X$ é $3$ (veja o inteiro na posição R na matriz anterior). Vamos chamar esse valor $X$ de "grau" daquela posição.
Voltemos agora ao passeio parcial visto acima:
1 . 3 18 . . 13 16
4 19 . . 14 17 . .
. 2 . . . . 15 12
20 5 . . . . . .
. . . . . . 11 .
6 21 . . . . . .
. . . 8 . . . 10
. 7 . . . 9 . .
Note que o cavalo poderia ir agora para as posições A, B, C ou D:
1 . 3 18 . . 13 16
4 19 . . 14 17 . .
. 2 . . . . 15 12
20 5 D . . . . .
. . . C . . 11 .
6 21 . . . . . .
. . . 8 . . . 10
A 7 B . . 9 . .
Como há quatro possibilidades para a próxima posição do cavalo, quatro chamadas recursivas devem ser executadas para explorar essas quatro possibilidades. Em KnightOnePlain.java, essas possibilidades são exploradas na ordem C, D, A e B (verifique essa afirmação). Em KnightOneDeluxe.java, essas possibilidades devem ser exploradas em ordem crescente dos graus. Assim, KnightOneDeluxe.java deve explorar as possibilidades A, B, C e D nessa ordem, pois os graus dessas posições são 1, 3, 6, 6. Seu programa pode quebrar eventuais empates de forma arbitrária; assim, nesse exemplo, a ordem de exploração poderia também ser A, B, D, C.
Filas de prioridade. Use, obrigatoriamente, a fila de prioridade implementada em IndexMinPQ.java para fazer com que sua recursão escolha o próximo passo em ordem crescente dos graus.
Modos de execução. KnightOneDeluxe.java deve ter dois modos de execução. O usuário poderá dar apenas $N$ na linha comando. Nesse caso, seu programa deve imprimir um passeio do cavalo no tabuleiro $N$ por $N$. O usuário poderá dar um segundo argumento na linha de comando (arbitrário). Nesse caso, seu programa deve apenas dizer se há ou não um passeio de cavalo para o valor de $N$ dado.
Exemplos de execução. Seu programa deve comportar-se como nos exemplos abaixo (naturalmente, os tempos de execução podem variar).
$ java-algs4 KnightOneDeluxe 4
Found no tour
$ time java-algs4 KnightOneDeluxe 9
1 80 3 16 31 68 45 14 29
4 17 78 81 46 15 30 59 44
79 2 73 32 67 76 69 28 13
18 5 52 77 74 47 60 43 58
51 72 33 66 53 70 75 12 27
6 19 50 71 64 61 48 57 42
37 34 65 22 49 54 63 26 11
20 7 36 39 62 9 24 41 56
35 38 21 8 23 40 55 10 25
real 0m0.291s
user 0m0.288s
sys 0m0.064s
$ time java-algs4 KnightOneDeluxe 10 > 10.out
real 0m1.214s
user 0m0.353s
sys 0m0.198s
$ time java-algs4 -Xss10M KnightOneDeluxe 30 > 30.out
real 0m0.391s
user 0m0.504s
sys 0m0.090s
$ time java-algs4 KnightOneDeluxe 50 .
There is a Knight's tour on an 50x50 board
real 0m0.247s
user 0m0.304s
sys 0m0.063s
$ time java-algs4 KnightOneDeluxe 50 | head -n1 > 50_1.out
real 0m1.933s
user 0m4.235s
sys 0m0.319s
$ time java-algs4 -Xss10M KnightOneDeluxe 100 .
There is a Knight's tour on an 100x100 board
real 0m0.294s
user 0m0.390s
sys 0m0.067s
$ time java-algs4 -Xss10M KnightOneDeluxe 200 .
There is a Knight's tour on an 200x200 board
real 0m0.347s
user 0m0.543s
sys 0m0.076s
$ time java-algs4 -Xss10M KnightOneDeluxe 215 .
There is a Knight's tour on an 215x215 board
real 0m0.354s
user 0m0.557s
sys 0m0.076s
Observação. A opção -Xss10M fornecida acima é para possibilitar ao Java executar recursões "mais profundas". Isto é, é para ele poder lidar com árvores de recursão mais altas.
- 23. April 2021, 13:35
- 23. April 2021, 13:35
- 23. April 2021, 13:35
- 23. April 2021, 13:35