Problema diário de codificação: use suas habilidades de codificação para verificar o xeque-mate

Verifique o xeque-mate

Bem-vindo bem-vindo com mais um problema para resolver! Se você gosta de jogar xadrez e programar : este é para você! Hoje vamos ajudar o rei a sobreviver mais um dia no campo de batalha, também escrevendo um monte de código bem grande.

Então, sem mais delongas, vamos ver nosso problema. Antes de começar, porém, como sempre, dois avisos:

• Esses problemas são fornecidos pelo maravilhoso boletim Daily Coding Problem, que você pode assinar aqui : confira e tente resolver seu desafio diário também!
• Não sou um programador especialista, apenas um cara que gosta de compartilhar suas tentativas (e falhas). Se você tiver uma ideia ou solução melhor, sinta-se à vontade para compartilhá-la: adoraria ver você resolvendo isso!

O problema

O problema de hoje foi perguntado inicialmente pela Oracle.

Você é apresentado a uma matriz de 8 por 8 representando as posições das peças em um tabuleiro de xadrez. As únicas peças no tabuleiro são o rei preto e várias peças brancas. Dada esta matriz, determine se o rei está em xeque.

Para detalhes sobre como cada peça se move, veja aqui .

Por exemplo, dada a seguinte matriz:

 ...K.... ........ .B...... ......P. .......R ..N..... ........ .....Q..

Você deve retornar True , já que o bispo está atacando o rei na diagonal.

O problema é bastante claro, por isso não vamos elaborar mais sobre isso. Só precisamos de algumas especificações iniciais:

1. Estamos em um gráfico, não em um tabuleiro: vamos considerar cada ponto dado pelo problema como o centro de um caso no tabuleiro . O resultado é o mesmo;
2. O rei branco saiu de férias com outros 7 peões: o rei e os peões são as peças mais chatas de todas e removê-los não vai mudar muito nossa solução;
3. Precisamos verificar se o rei está em xeque neste mesmo turno , ou seja, no próximo turno do branco será feito se ele não se mover;
4. As posições são inicialmente dadas pelo jogo : não irei verificar se há peças sobrepostas ou posições iniciais erradas.

A solução

Em primeiro lugar, uma rápida recapitulação de peças e conjuntos de movimentos:

Dada a posição inicial de cada peça e seu conjunto de movimentos, podemos calcular “facilmente” todos os próximos movimentos possíveis de cada peça .

E como todos estão interessados em capturar o rei o mais rápido possível, podemos supor que o próximo movimento deles será capturar o rei preto . Portanto, como também conhecemos a posição do rei preto, precisamos apenas verificar se a posição do rei preto é um dos próximos movimentos possíveis das outras peças . Se for, durante o próximo turno branco, a peça branca se moverá para capturar o rei preto.

A situação é mais ou menos assim:
Na foto acima você pode ver (… espero que sim, desculpe a confusão…) todas as jogadas possíveis de cada peça do lado branco, coloridas com cores diferentes, e o rei preto acima esperando para ser capturado. Assim, por exemplo, o bispo, começando em (2,7), pode mover-se para (1,6), (1,8), (3,8), (3,6), (4,5), (5, 4) e assim por diante.

Eu decidi aleatoriamente as posições iniciais dessas peças, pois isso não afeta o resultado final.

Como estamos em um gráfico 8x8 (para ficar claro, qualquer outra dimensão funcionará da mesma maneira) e temos as coordenadas iniciais de cada peça, podemos construir séries de coordenadas x,y que serão os próximos movimentos de nossas peças. Para fazer isso, primeiro definimos uma classe para cada peça, definimos suas coordenadas e depois definimos as regras para calcular todos os movimentos possíveis a partir daí.

As peças — O peão

Vamos começar simples com o Peão. A propósito, estou construindo isso em Python , já que é uma das linguagens mais populares no momento e sem dúvida a mais legível por qualquer pessoa. Ainda assim, você vai precisar saber o que é uma aula para poder acompanhar a partir de agora. aqui está uma explicação bem legal desse conceito.

Vamos explicar brevemente: primeiro definimos a classe class Pawn e __init__ suas coordenadas x,y . Depois disso, definimos o método possibleMoves para calcular os possíveis movimentos do peão a partir daí. Os movimentos do peão são relativamente fáceis, então simplesmente os adicionamos à variável moves , depois de verificar se ele não se move fora de nossa grade, e retornamos a matriz moves . Duas coisas a serem observadas aqui, especificamente para o peão:

1. Consideramos que o peão branco se move de baixo para cima, como se fôssemos o jogador branco movendo nosso peão adiante em direção ao nosso oponente. Isso realmente não muda nada, apenas mantém as coisas em ordem.

2. Pulamos intencionalmente o movimento normal , pois estamos interessados em capturar o rei preto: como o peão só pode capturar na diagonal e não nos preocupamos em mover as peças em outras direções, podemos pular seu movimento normal.

   
   

Agora podemos simplesmente verificar os movimentos do peão dando a ele suas coordenadas e chamando o método possibleMoves , assim: print(Pawn(7,2).possibleMoves()) e devemos obter algo como [(6,3),(8,3)] .

Além disso, você pode ver na parte superior que definimos nossas dimensões de grade como variáveis , para que possamos alterá-las para executar o algoritmo em placas de outras dimensões.

Agora vamos passar para a torre.

A torre

Novamente, iniciamos a classe Tower com suas coordenadas e definimos a função possibleMoves . Para coletar todos os movimentos possíveis aqui , variamos todos os pontos nos dois eixos da torre e adicionamos cada coordenada única aos moves variáveis , que serão retornados após todos os loops. Como antes, para verificar os movimentos da torre, podemos simplesmente print(Tower(5,3).possibleMoves()) e devemos obter algo como isto: [(1,3), (2,3), (3,3), ..., (5,8)] .

o bispo

Agora é a vez do bispo.

Os movimentos do bispo são mais complexos que os da torre, então podemos explicar um pouco o que está acontecendo aqui. Basicamente , precisamos coletar pontos nos dois eixos diagonais a partir de sua posição inicial . Depois de declarada a classe e o método init, criamos duas variáveis: moves , como antes, e currentPos , que será usada para rastrear os pontos que coletamos ao mover-nos ao longo de seus eixos. Agora, usando o loop while e verificando se não estamos nos movendo para fora de nossa grade, aumentamos e diminuímos x e y de acordo com o local para onde queremos nos mover . Por exemplo, se quisermos mover para cima e para a esquerda de suas posições iniciais, precisaremos diminuir o valor x enquanto incrementamos o valor de y . Se quisermos mover para baixo à direita, precisaremos incrementar o valor x enquanto diminuímos o valor y e assim por diante. Finalmente, simplesmente retornamos moves mais uma vez.

A rainha

Agora você pode pensar: se os movimentos da torre são complexos e os do bispo são ainda mais, como diabos vamos codificar a rainha? Na verdade, os movimentos da rainha são os mais fáceis de codificar, apenas com a ajuda de um truque simples. Vamos ver a rainha então.

Tudo bem, o que está acontecendo aqui? Bem, se pensarmos bem, a rainha tem os mesmos movimentos do bispo e da torre combinados . Ela é mais como um mecha-bot bispo em forma de torre do que uma rainha. Por esse motivo, codificar seus movimentos é realmente simples. Depois de declarar sua classe, simplesmente definimos seus possibleMoves como a matriz da união de movimentos resultantes dos possíveis movimentos do bispo e da torre .

Observe que, ao chamar as instâncias das classes Bishop e Tower na função possibleMoves , seus parâmetros x e y são fornecidos como self.x, self.y , portanto, na verdade, são as coordenadas da rainha.

O Cavaleiro

Agora para o cavaleiro!

O cavaleiro é o mais particular para mim. Seu conjunto de movimentos é estranho, como em forma de “L”, então não encontrei uma maneira particularmente inteligente ou rápida de codificá-lo e acabei codificando seus movimentos simplesmente calculando cada um dos 8 movimentos possíveis que ele tem de sua posição inicial .

O rei

Alguns breves conceitos sobre o rei. Como não somos obrigados a mover o rei, apenas informando se ele deu check ou não, não precisamos realmente implementar seu move-set . No entanto, também veremos uma breve implementação no final do artigo. Além disso, codificá-lo não é tão simples quanto enfraquecer o conjunto de movimentos da rainha, como veremos mais adiante. Então, por enquanto, vamos pular seus movimentos e ver a solução.

O código da solução

Dado que temos as posições possíveis para cada peça, a solução agora é bastante simples: basta verificar se as coordenadas do rei preto estão no conjunto de jogadas de uma ou mais das outras peças. Vamos codificar!

Agora simplesmente criamos uma variável blackKing como um par de coordenadas. Então, para cada peça, criamos uma instância de sua classe que acabamos de construir e chamamos o método possibleMoves para calcular seu conjunto completo de movimentos. Assim que o tivermos, verificamos se as coordenadas blackKing estão presentes nesses conjuntos de movimentos : se estiverem, imprimimos que o rei foi verificado por aquela peça em particular. O resultado aqui é algo assim:

 Pawn moves: [(8, 3), (6, 3)] Tower moves: [(1, 3), (2, 3), (3, 3), (4, 3), (6, 3), (7, 3), (8, 3), (5, 1), (5, 2), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8)] Check by the tower! Bishop moves: [(3, 8), (1, 6), (1, 8), (3, 6), (4, 5), (5, 4), (6, 3), (7, 2), (8, 1)] Queen moves: [(4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (2, 1), (2, 3), (1, 4), (4, 1), (1, 2), (2, 2), (4, 2), (5, 2), (6, 2), (7, 2), (8, 2), (3, 1), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8)] Knight moves: [(4, 7), (4, 5), (8, 7), (8, 5), (5, 4), (7, 4), (7, 8), (5, 8)] Check by the knight!

Usei a imagem confusa acima como referência, para que você possa verificar se o rei é realmente verificado pela torre e pelo cavalo.

xeque-mate

E se também quisermos calcular se o rei ainda tem alguma chance de sobreviver ou se realmente é xeque-mate? Para isso, precisamos calcular o conjunto de movimentos do rei.

Vamos descrevê-lo um pouco. Primeiro, definimos nossa classe e coordenadas como antes. Depois disso, criamos o método possibleMoves e codificamos os possíveis movimentos do rei (novamente, tenho certeza de que existe uma maneira mais rápida, mas existem apenas 8 movimentos possíveis, então…). Depois disso, verificamos quais movimentos são ilegais (movimento fora do tabuleiro) e retornamos apenas os validMoves .

Então agora, para verificar se o rei ainda tem chance de sobreviver, precisamos verificar se algum de seus movimentos possíveis não está em outro conjunto de movimentos de peças. Para fazer isso, simplesmente percorremos os movimentos do rei e os outros movimentos.

Portanto, ainda há esperança de que nosso rei sobreviva! Sorte dele eu acho...

Complexidade de tempo

Como sempre, uma breve olhada na complexidade de tempo desta solução.

Primeiramente, como cada peça é uma instância de uma classe , devemos considerar o tempo para inicializar essa instância.

• Peças como o peão ou o cavalo não possuem nenhum loop dentro de si e não dependem de nenhuma dimensão variável, portanto podemos considerá-las O(1);
• A torre é um pouco complicada: como ela contém 4 loops for, você pode pensar instantaneamente que sua complexidade de tempo é O(n), certo? Na verdade, se pensarmos em como a torre se move, perceberemos que não importa onde ela esteja no tabuleiro, seus movimentos são limitados às caixas livres do tabuleiro em seus eixos vertical e horizontal. E como o tabuleiro é um quadrado, sempre teremos 14 caixas livres para mover nossa torre. Portanto, sua complexidade de tempo deveria ser O(1), constante para 14 pares de coordenadas. Aqui está um exemplo gráfico:

• Infelizmente, não podemos dizer o mesmo do bispo , cujo conjunto de jogadas parece ser um pouco mais complexo. Basicamente, tem 7, 9, 11 ou 13 jogadas dependendo de onde está colocado no tabuleiro. Portanto, os passos necessários para calcular seu conjunto de movimentos são baseados em sua posição, portanto, podemos considerar um tc de O(n).

• A rainha precisa do conjunto de movimentos da torre e do bispo combinados. Pois ao avaliar a complexidade do tempo devemos focar no pior cenário , o tc do bispo prevalece sobre o tc da torre. Assim, devemos considerar um tc de O(n) também para a rainha.

• Por fim, o rei tem um conjunto de movimentos codificado, mas também um processo de validação envolvido que usa um loop for . Portanto, tecnicamente, mesmo que o conjunto de movimentos do rei seja relativamente pequeno, devemos considerar seu tc como O(n), também dependendo de sua posição no tabuleiro.

  
  

Neste ponto, usamos um loop for para cada peça para verificar e imprimir o status do cheque do rei preto . Isso não nos dá problemas onde o tc é constante (pegue a torre, por exemplo: calculamos seus 14 movimentos e depois voltamos outros 14 vezes no máximo, então podemos considerá-lo também tempo fixo). Ainda assim, teremos problemas onde o tc for O(n) ou superior, pois estamos adicionando um loop que também crescerá à medida que o número de movimentos aumentar.

Por fim, utilizamos um loop for duplo (interior) para verificar o xeque-mate , que com certeza será um tc de O(n²), dependendo do número de jogadas do rei e das jogadas das demais peças.

É isso; aí está a minha solução. Sei bem que alguns pontos não são os mais eficientes possíveis, mas enquanto escrevia gostei mais da ideia de descrever o processo do que construir a solução perfeita.

O que você pensa sobre isso? Dê-me sua opinião sobre isso e vamos discutir suas soluções nos comentários!

Como sempre, se você gostou do artigo, deixe um clap ou dois e se inscreva, ou compartilhe com alguém que possa se interessar por este tipo de algoritmos, se puder! Obrigado por ler até o final, desta vez mais do que sempre, dada a extensão desta solução!

Como sempre, obrigado pela leitura.