E13 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. Lembre que estudamos o seguinte material:
https://www.ime.usp.br/~yoshi/Sedgewick/Algs4th/Slides/67CombinatorialSearch.pdf
Vimos um programa relevante para o presente exercício em setembro:
https://www.ime.usp.br/~yoshi/2021ii/mac0121/sandbox/2021.09.23/KNIGHT/
Você também encontra algumas variantes do programa Knight.java na URL acima em
https://www.ime.usp.br/~yoshi/2019ii/ccm118/sandbox/2019.10.16/
Note que os programas acima devem ser compilados e executados com javac-introcs e java-introcs. O resto deste enunciado supõe que você já estudou os programas acima.
Versão para encontrar um passeio. Como o número total de passeios do cavalo em um tabuleiro \(N\) por $N$ cresce muito rapidamente com $N$, em tempo razoável, o 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 contar todos esses passeios gerando cada um deles é um tanto 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.
Versão incrementada de KnightOnePlain.java. Neste exercício, você escreverá uma versão incrementada de KnightOnePlain.java, que faz a busca recursiva de forma um pouco mais sofisticada (bastará alterar a ordem das chamadas recursivas). 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.
Fila 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 ser um diferentes).
$ 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.
Versão super deluxe. Você verá que, para certos valores de $N$, KnightOneDeluxe.java ainda pode demorar. (Experimente executar KnightOneDeluxe.java para todos os valores entre $100$ e $200$.)
Neste exercício, você deve escrever um segundo programa, chamado KnightOneSuperDeluxe.java, que implementa uma ideia adicional. A ideia adicional vem do seguinte: quando começamos a busca a partir de uma posição $(i, j)$ do tabuleiro, talvez a busca demora, mas talvez começando de outra posição $(i', j')$ a busca seja rápida. Usando um Stopwatch, podemos abortar buscas que demoram mais de um certo tempo, como, por exemplo, um segundo.
Seu programa KnightOneSuperDeluxe.java deve procurar passeios começando de cada posição $(i, j)$ do tabuleiro, mas deve abortar a busca começando em $(i, j)$ quando ela demorar mais de um segundo.
Ademais, KnightOneSuperDeluxe.java deve receber dois inteiros $A$ e $B$ na linha de comando e deve considerar todos os tabuleiros $N\times N$ com $A\leq N\leq B$. KnightOneSuperDeluxe.java deve também imprimir os pontos de partida que ele está tentando. O que se espera são saídas como abaixo:
$ time java-algs4 KnightOneSuperDeluxe 1 5
1: (0, 0) : There is a Knight's tour on a 1x1 board
2: (0, 0) : Found no tours
3: (0, 0) : (0, 1) : (1, 1) : Found no tours
4: (0, 0) : (0, 1) : (1, 1) : Found no tours
5: (0, 0) : There is a Knight's tour on a 5x5 board
real 0m0.263s
user 0m0.186s
sys 0m0.052s
$ time java-algs4 -Xss30m KnightOneSuperDeluxe 190 200
190: (0, 0) : (0, 1) : (0, 2) : (0, 3) : (0, 4) : There is a Knight's tour on a 190x190 board
191: (0, 0) : (0, 1) : (0, 2) : (0, 3) : (0, 4) : (0, 5) : (0, 6) : (0, 7) : (0, 8) : (0, 9) : (0, 10) : (0, 11) : (0, 12) : (0, 13) : (0, 14) : (0, 15) : (0, 16) : (0, 17) : (0, 18) : (0, 19) : (0, 20) : (0, 21) : (0, 22) : (0, 23) : (0, 24) : (0, 25) : (0, 26) : (0, 27) : (0, 28) : (0, 29) : (0, 30) : (0, 31) : (0, 32) : There is a Knight's tour on a 191x191 board
192: (0, 0) : There is a Knight's tour on a 192x192 board
193: (0, 0) : (0, 1) : (0, 2) : (0, 3) : (0, 4) : (0, 5) : (0, 6) : (0, 7) : (0, 8) : (0, 9) : (0, 10) : There is a Knight's tour on a 193x193 board
194: (0, 0) : (0, 1) : There is a Knight's tour on a 194x194 board
195: (0, 0) : (0, 1) : (0, 2) : There is a Knight's tour on a 195x195 board
196: (0, 0) : (0, 1) : (0, 2) : There is a Knight's tour on a 196x196 board
197: (0, 0) : (0, 1) : (0, 2) : There is a Knight's tour on a 197x197 board
198: (0, 0) : (0, 1) : There is a Knight's tour on a 198x198 board
199: (0, 0) : There is a Knight's tour on a 199x199 board
200: (0, 0) : There is a Knight's tour on a 200x200 board
real 0m54.902s
user 1m1.602s
sys 0m0.878s
$ time java-algs4 -Xss100m KnightOneSuperDeluxe 490 500
490: (0, 0) : (0, 1) : (0, 2) : (0, 3) : (0, 4) : (0, 5) : (0, 6) : (0, 7) : (0, 8) : (0, 9) : (0, 10) : (0, 11) : (0, 12) : (0, 13) : (0, 14) : (0, 15) : There is a Knight's tour on a 490x490 board
491: (0, 0) : (0, 1) : (0, 2) : (0, 3) : (0, 4) : (0, 5) : (0, 6) : There is a Knight's tour on a 491x491 board
492: (0, 0) : (0, 1) : (0, 2) : (0, 3) : There is a Knight's tour on a 492x492 board
493: (0, 0) : (0, 1) : (0, 2) : (0, 3) : (0, 4) : (0, 5) : (0, 6) : (0, 7) : (0, 8) : (0, 9) : (0, 10) : (0, 11) : (0, 12) : (0, 13) : (0, 14) : (0, 15) : (0, 16) : (0, 17) : (0, 18) : (0, 19) : (0, 20) : (0, 21) : (0, 22) : (0, 23) : (0, 24) : (0, 25) : (0, 26) : (0, 27) : (0, 28) : (0, 29) : (0, 30) : (0, 31) : (0, 32) : (0, 33) : (0, 34) : (0, 35) : (0, 36) : (0, 37) : (0, 38) : (0, 39) : (0, 40) : (0, 41) : (0, 42) : (0, 43) : (0, 44) : (0, 45) : (0, 46) : (0, 47) : (0, 48) : (0, 49) : (0, 50) : (0, 51) : (0, 52) : (0, 53) : (0, 54) : (0, 55) : (0, 56) : (0, 57) : (0, 58) : There is a Knight's tour on a 493x493 board
494: (0, 0) : (0, 1) : (0, 2) : (0, 3) : (0, 4) : (0, 5) : (0, 6) : There is a Knight's tour on a 494x494 board
495: (0, 0) : (0, 1) : (0, 2) : (0, 3) : (0, 4) : (0, 5) : (0, 6) : (0, 7) : (0, 8) : (0, 9) : (0, 10) : There is a Knight's tour on a 495x495 board
496: (0, 0) : (0, 1) : (0, 2) : (0, 3) : (0, 4) : (0, 5) : (0, 6) : (0, 7) : (0, 8) : (0, 9) : (0, 10) : (0, 11) : (0, 12) : (0, 13) : (0, 14) : (0, 15) : (0, 16) : (0, 17) : (0, 18) : (0, 19) : (0, 20) : (0, 21) : (0, 22) : (0, 23) : (0, 24) : (0, 25) : (0, 26) : (0, 27) : (0, 28) : (0, 29) : There is a Knight's tour on a 496x496 board
497: (0, 0) : (0, 1) : (0, 2) : (0, 3) : (0, 4) : (0, 5) : (0, 6) : (0, 7) : (0, 8) : (0, 9) : (0, 10) : (0, 11) : (0, 12) : (0, 13) : (0, 14) : (0, 15) : (0, 16) : (0, 17) : (0, 18) : (0, 19) : (0, 20) : (0, 21) : (0, 22) : There is a Knight's tour on a 497x497 board
498: (0, 0) : (0, 1) : (0, 2) : (0, 3) : (0, 4) : (0, 5) : (0, 6) : (0, 7) : (0, 8) : (0, 9) : (0, 10) : (0, 11) : (0, 12) : There is a Knight's tour on a 498x498 board
499: (0, 0) : (0, 1) : (0, 2) : (0, 3) : (0, 4) : (0, 5) : (0, 6) : (0, 7) : (0, 8) : (0, 9) : (0, 10) : (0, 11) : (0, 12) : (0, 13) : (0, 14) : (0, 15) : (0, 16) : (0, 17) : (0, 18) : (0, 19) : (0, 20) : (0, 21) : (0, 22) : (0, 23) : (0, 24) : (0, 25) : (0, 26) : (0, 27) : (0, 28) : (0, 29) : (0, 30) : (0, 31) : (0, 32) : (0, 33) : (0, 34) : (0, 35) : (0, 36) : (0, 37) : (0, 38) : (0, 39) : (0, 40) : (0, 41) : (0, 42) : (0, 43) : (0, 44) : (0, 45) : (0, 46) : (0, 47) : (0, 48) : (0, 49) : (0, 50) : (0, 51) : (0, 52) : (0, 53) : (0, 54) : (0, 55) : (0, 56) : (0, 57) : (0, 58) : (0, 59) : (0, 60) : (0, 61) : (0, 62) : (0, 63) : (0, 64) : (0, 65) : (0, 66) : (0, 67) : (0, 68) : (0, 69) : (0, 70) : (0, 71) : (0, 72) : (0, 73) : (0, 74) : (0, 75) : (0, 76) : (0, 77) : (0, 78) : (0, 79) : (0, 80) : (0, 81) : (0, 82) : (0, 83) : (0, 84) : (0, 85) : (0, 86) : (0, 87) : (0, 88) : (0, 89) : (0, 90) : (0, 91) : (0, 92) : (0, 93) : (0, 94) : (0, 95) : (0, 96) : (0, 97) : (0, 98) : (0, 99) : (0, 100) : (0, 101) : (0, 102) : (0, 103) : (0, 104) : (0, 105) : (0, 106) : (0, 107) : (0, 108) : (0, 109) : (0, 110) : (0, 111) : (0, 112) : (0, 113) : (0, 114) : (0, 115) : (0, 116) : (0, 117) : (0, 118) : (0, 119) : (0, 120) : (0, 121) : (0, 122) : (0, 123) : (0, 124) : (0, 125) : (0, 126) : (0, 127) : (0, 128) : (0, 129) : (0, 130) : (0, 131) : (0, 132) : (0, 133) : (0, 134) : (0, 135) : (0, 136) : (0, 137) : (0, 138) : (0, 139) : (0, 140) : (0, 141) : (0, 142) : (0, 143) : (0, 144) : (0, 145) : (0, 146) : (0, 147) : (0, 148) : (0, 149) : (0, 150) : (0, 151) : (0, 152) : (0, 153) : (0, 154) : (0, 155) : (0, 156) : (0, 157) : (0, 158) : (0, 159) : (0, 160) : (0, 161) : (0, 162) : (0, 163) : (0, 164) : (0, 165) : (0, 166) : (0, 167) : (0, 168) : (0, 169) : (0, 170) : (0, 171) : (0, 172) : (0, 173) : (0, 174) : (0, 175) : (0, 176) : (0, 177) : (0, 178) : (0, 179) : (0, 180) : (0, 181) : (0, 182) : (0, 183) : (0, 184) : (0, 185) : (0, 186) : (0, 187) : (0, 188) : (0, 189) : (0, 190) : (0, 191) : (0, 192) : (0, 193) : (0, 194) : (0, 195) : (0, 196) : (0, 197) : (0, 198) : (0, 199) : (0, 200) : (0, 201) : (0, 202) : (0, 203) : (0, 204) : There is a Knight's tour on a 499x499 board
500: (0, 0) : (0, 1) : (0, 2) : (0, 3) : (0, 4) : (0, 5) : (0, 6) : (0, 7) : (0, 8) : (0, 9) : (0, 10) : (0, 11) : (0, 12) : (0, 13) : (0, 14) : (0, 15) : (0, 16) : (0, 17) : (0, 18) : (0, 19) : (0, 20) : (0, 21) : (0, 22) : (0, 23) : (0, 24) : (0, 25) : (0, 26) : (0, 27) : (0, 28) : (0, 29) : (0, 30) : (0, 31) : (0, 32) : (0, 33) : (0, 34) : (0, 35) : (0, 36) : (0, 37) : (0, 38) : (0, 39) : (0, 40) : There is a Knight's tour on a 500x500 board
real 7m2.181s
user 8m4.362s
sys 0m12.899s
$
Na saída acima, por exemplo, a linha
190: (0, 0) : (0, 1) : (0, 2) : (0, 3) : (0, 4) : There is a Knight's tour on a 190x190 board
significa o seguinte: o programa está tentando encontrar um passeio no tabuleiro $190\times190$; ele disparou uma busca começando em $(0,0)$, mas abortou a busca; ele tentou então $(0,1)$, mas novamente abortou. Ao tentar a busca a partir de $(0,4)$, ele encontrou um passeio.
As saídas acima mostram que, quando fazemos backtracking, podemos implementar essa ideia de abortar buscas longas.
Uma pequena ideia adicional. Neste problema, é claro que podemos nos restringir a buscas começando nas posições $(i, j)$ do tabuleiro, onde $0\leq i\leq j<N/2$ (por quê?). Essa ideia deve ser implementada em KnightOneSuperDeluxe.java.
Tempos de execução. Como de costume, é esperado que seus programas tenham, grosso modo, tempo de execução comparáveis aos tempos nos exemplos acima.
Entrega. Entregue seus programas KnightOneDeluxe.java KnightOneSuperDeluxe.java.
- 24. November 2021, 20:26
- 24. November 2021, 20:26