Problema da caminhada perfeita

Dificuldade Única

Considere uma representação de um tabuleiro de Xadrez em uma matriz de String 8x8 e o seguinte padrão:

• T para Torre (movimenta-se N casas na vertical e horizontal).
• C para Cavalo (movimenta-se em L, um L por vez).
• B para Bispo (movimenta-se N casas em diagonal).
• Q para Rainha (movimenta-se N casas na vertical, horizontal e diagonal).
• K para Rei (movimenta-se uma casa por vez na vertical, horizontal e diagonal).
• 0 (zero) casa não ocupada.

Uma peça disposta neste tabuleiro executa uma caminha perfeita se é possivel que em jogadas sucessivas (sem que exista movimento adversário), ela tome ("coma") todas as outras peças do tabuleiro sem que em nenhuma jogada deixe de tomar peça.

Considerando que só existirá no máximo uma peça de cada tipo no tabuleiro, faça uma classe de nome CaminhadaPerfeita com um método público VerificarExistencia que, recebendo uma matriz 8x8 de String, seja capaz de retornar um booleano indicando se existe ou não peça capaz de executar a caminhada perfeita.

Exemplo 1

Entrada

{ {"0","0","0","0","0","0","0","0","0"},
  {"0","C","0","0","0","0","0","0","0"},
  {"0","0","0","0","0","0","0","0","0"},
  {"0","0","R","0","0","0","0","0","0"},
  {"0","0","0","0","Q","0","0","0","0"},
  {"0","B","0","0","0","0","0","0","0"},
  {"0","0","0","K","0","0","0","0","0"},
  {"0","0","0","0","0","0","0","0","0"} }

Saída

  true

Exemplo 2

Entrada

{ {"0","0","0","0","0","0","0","0","0"},
  {"0","T","0","0","0","0","0","0","0"},
  {"0","0","0","0","0","0","0","0","0"},
  {"0","0","0","0","0","0","0","0","0"},
  {"0","0","0","0","Q","0","0","0","0"},
  {"0","0","0","R","0","0","0","0","0"},
  {"0","0","B","0","0","0","0","0","0"},
  {"0","C","0","0","0","0","0","0","0"} }

Saída

  true

Exemplo 3

Entrada

{ {"0","0","0","0","0","0","0","0","0"},
  {"0","0","0","0","0","0","0","0","0"},
  {"0","0","0","0","0","0","0","0","0"},
  {"0","0","0","0","0","0","0","0","0"},
  {"0","0","0","0","T","0","0","0","0"},
  {"0","0","0","R","0","0","0","0","0"},
  {"0","0","C","0","0","0","0","0","0"},
  {"0","0","0","0","0","0","0","0","0"},
  {"0","0","0","0","0","0","0","0","0"},
  {"0","0","0","0","0","0","0","0","0"} }

Saída

  false