Fórum de discussão

Ois,

Oi professor,...

Antes de mais nada, uma dica , quando vocês colocarem uma mensagem no fórum não restrigam
o universo das pessoas que podem responder.
Simplesmente coloquem a dúvida/pergunta.
Sugestões/respostas/dicas são bem vindas , independentemente da fonte.

como a gente acha o algoritmo da solução pra resolver o tabuleiro no menor número possível de jogadas?

Todas as soluções conhecidas enumera/listam todos os candidatos a solução e ficam
com a melhor. Umas maneiras enumeram menos candidatos que as outras, mas todas
enumeram.

Aqui vai sugestão de uma solução (= processo de enumeração).
Durante a leitura do texto a seguir talvez ajude ir olhando os comentarios
no programa tapinhas.c colocado no diretório do esqueleto do EP1.

Solução alto nivel:

para cada possível lista de tapinhas,
aplique os tapinhas na lista e verifique se eles colocam todos
os turtles para dormir. Dentre as listas que colocam todos
os turtles para dormir, retorne a que tem o menor número
de tapinhas.

Olhando de mais alto nível o problema é essencialmente o
de encontrar o menor elemento de uma sequência. No caso
a sequência é a formada pelas lista de tapinhas que colocam todos
os turtles para dormir e o menor é referente a violência da lista  (número de tapinhas).

Cada lista de tapinhas é representada por uma matriz binária.
O problema passa a ser portanto o de enumerar todas as matriz binárias.
Se a dimensão do turtledorm é n × n, então existem 2^{n × n} matriz binária possíveis , cada uma representa uma lista de tapinhas.
Para exemplificar, suponha que n = 2.
Assim, precisamos enumerar 2⁴ matriz de tapinhas.
Cada uma dessas matriz esta associada a uma sequencia de 4 bits (dígitos binários = zeros e uns).
Por exemplo, as 2⁴ sequência de 4 bits (escritas usando 5) são:

0 0 0 0 0    = representação do 0 na base 2 utilizando 5 bits
0 0 0 0 1    = representação do 1 na base 2 utilizando 5 bits
0 0 0 1 0    = representação do 2 na base 2 utilizando 5 bits
0 0 0 1 1    = representação do 3 na base 2 utilizando 5 bits
0 0 1 0 0    = representação do 4 na base 2 utilizando 5 bits
0 0 1 0 1    = representação do 5 na base 2 utilizando 5 bits
0 0 1 1 0    = ...
0 0 1 1 1    = ...
0 1 0 0 0
0 1 0 0 1
0 1 0 1 0
0 1 0 1 1
0 1 1 0 0
0 1 1 0 1
0 1 1 1 0
0 1 1 1 1
1 0 0 0 0 -----------> acabou

A cada configuração acima corresponde uma matriz de tapinhas:

meu_prompt> ./tapinhas 
Lista de todas as matriz binarias 2 x 2:

Matriz para:  0 0 0 0 0
         1       2   
     +-------+-------+
  1  |       |       |
     +-------+-------+
  2  |       |       |
     +-------+-------+

Matriz para:  0 0 0 0 1
         1       2   
     +-------+-------+
  1  |   T   |       |
     +-------+-------+
  2  |       |       |
     +-------+-------+

Matriz para:  0 0 0 1 0
         1       2   
     +-------+-------+
  1  |       |   T   |
     +-------+-------+
  2  |       |       |
     +-------+-------+

Matriz para:  0 0 0 1 1
         1       2   
     +-------+-------+
  1  |   T   |   T   |
     +-------+-------+
  2  |       |       |
     +-------+-------+

Matriz para:  0 0 1 0 0
         1       2   
     +-------+-------+
  1  |       |       |
     +-------+-------+
  2  |   T   |       |
     +-------+-------+

Matriz para:  0 0 1 0 1
         1       2   
     +-------+-------+
  1  |   T   |       |
     +-------+-------+
  2  |   T   |       |
     +-------+-------+

Matriz para:  0 0 1 1 0
         1       2   
     +-------+-------+
  1  |       |   T   |
     +-------+-------+
  2  |   T   |       |
     +-------+-------+

Matriz para:  0 0 1 1 1
         1       2   
     +-------+-------+
  1  |   T   |   T   |
     +-------+-------+
  2  |   T   |       |
     +-------+-------+

Matriz para:  0 1 0 0 0
         1       2   
     +-------+-------+
  1  |       |       |
     +-------+-------+
  2  |       |   T   |
     +-------+-------+

Matriz para:  0 1 0 0 1
         1       2   
     +-------+-------+
  1  |   T   |       |
     +-------+-------+
  2  |       |   T   |
     +-------+-------+

Matriz para:  0 1 0 1 0
         1       2   
     +-------+-------+
  1  |       |   T   |
     +-------+-------+
  2  |       |   T   |
     +-------+-------+

Matriz para:  0 1 0 1 1
         1       2   
     +-------+-------+
  1  |   T   |   T   |
     +-------+-------+
  2  |       |   T   |
     +-------+-------+

Matriz para:  0 1 1 0 0
         1       2   
     +-------+-------+
  1  |       |       |
     +-------+-------+
  2  |   T   |   T   |
     +-------+-------+

Matriz para:  0 1 1 0 1
         1       2   
     +-------+-------+
  1  |   T   |       |
     +-------+-------+
  2  |   T   |   T   |
     +-------+-------+

Matriz para:  0 1 1 1 0
         1       2   
     +-------+-------+
  1  |       |   T   |
     +-------+-------+
  2  |   T   |   T   |
     +-------+-------+

Matriz para:  0 1 1 1 1
         1       2   
     +-------+-------+
  1  |   T   |   T   |
     +-------+-------+
  2  |   T   |   T   |
     +-------+-------+

Bem, agora tente escrever a parte III usando a ideia acima e como ponto de partida
o programa tapinhas.c que foi colocado com o esqueleto do EP1.