Verifique o xeque-mate Bem-vindo bem-vindo com mais um problema para resolver! Se você gosta de jogar xadrez e : 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. programar 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 : confira e tente resolver seu desafio diário também! aqui 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. matriz de Você é apresentado a uma 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: Estamos em um gráfico, não em um tabuleiro: . O resultado é o mesmo; vamos considerar cada ponto dado pelo problema como o centro de um caso no tabuleiro 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; Precisamos , ou seja, no próximo turno do branco será feito se ele não se mover; verificar se o rei está em xeque neste mesmo turno : não irei verificar se há peças sobrepostas ou posições iniciais erradas. As posições são inicialmente dadas pelo jogo 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 . Portanto, como também conhecemos a posição do rei preto, . Se for, durante o próximo turno branco, a peça branca se moverá para capturar o rei preto. o próximo movimento deles será capturar o rei preto precisamos apenas verificar se a posição do rei preto é um dos próximos movimentos possíveis das outras peças A situação é mais ou menos assim: Na foto acima você pode ver (… espero que sim, desculpe a confusão…) 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. todas as jogadas possíveis de cada peça 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 que serão os próximos movimentos de nossas peças. Para fazer isso, primeiro definimos uma definimos suas coordenadas e depois x,y classe para cada peça, 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 , já que é uma das linguagens mais populares no momento e sem dúvida a mais legível por qualquer pessoa. Ainda assim, para poder acompanhar a partir de agora. uma explicação bem legal desse conceito. Python você vai precisar saber o que é uma aula aqui está https://gist.github.com/NicolaM94/ae4e0e850250a6974042b0ac72be7585?embedable=true#file-pawn-py Vamos explicar brevemente: primeiro definimos a classe e suas coordenadas . Depois disso, definimos o método 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 , depois de verificar se ele não se move fora de nossa grade, e retornamos a matriz . Duas coisas a serem observadas aqui, especificamente para o peão: class Pawn __init__ x,y possibleMoves moves moves 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. , 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. Pulamos intencionalmente o movimento normal Agora podemos simplesmente verificar os movimentos do peão dando a ele suas coordenadas e chamando o método , assim: e devemos obter algo como . possibleMoves print(Pawn(7,2).possibleMoves()) [(6,3),(8,3)] Além disso, você pode ver na parte superior que , para que possamos alterá-las para executar o algoritmo em placas de outras dimensões. definimos nossas dimensões de grade como variáveis Agora vamos passar para a torre. A torre https://gist.github.com/NicolaM94/7897939bdd7933cb09d8915b7b8bc0b5?embedable=true#file-tower-py Novamente, iniciamos a classe Tower com suas coordenadas e definimos a função . Para coletar todos os movimentos possíveis aqui variáveis , que serão retornados após todos os loops. Como antes, para verificar os movimentos da torre, podemos simplesmente e devemos obter algo como isto: . possibleMoves , variamos todos os pontos nos dois eixos da torre e adicionamos cada coordenada única aos moves print(Tower(5,3).possibleMoves()) [(1,3), (2,3), (3,3), ..., (5,8)] o bispo Agora é a vez do bispo. https://gist.github.com/NicolaM94/a6ae6f6138b78d550b2f2e27d5c453aa?embedable=true#file-bishop-py Os movimentos do bispo são mais complexos que os da torre, então podemos explicar um pouco o que está acontecendo aqui. Basicamente . Depois de declarada a classe e o método init, criamos duas variáveis: , como antes, e , que será usada para rastrear os pontos que coletamos ao mover-nos ao longo de seus eixos. Agora, usando o loop e verificando se não estamos nos movendo para fora de nossa grade, e . Por exemplo, se quisermos mover para cima e para a esquerda de suas posições iniciais, precisaremos diminuir o valor enquanto incrementamos o valor de . Se quisermos mover para baixo à direita, precisaremos incrementar o valor enquanto diminuímos o valor e assim por diante. Finalmente, simplesmente retornamos mais uma vez. , precisamos coletar pontos nos dois eixos diagonais a partir de sua posição inicial moves currentPos while aumentamos e diminuímos x y de acordo com o local para onde queremos nos mover x y x y moves 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. https://gist.github.com/NicolaM94/22bd55aab7a0976f4656403c3749a6ee?embedable=true#file-queen-py Tudo bem, o que está acontecendo aqui? Bem, se pensarmos bem, . 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 como a . a rainha tem os mesmos movimentos do bispo e da torre combinados possibleMoves 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 e na função , seus parâmetros e são fornecidos como , portanto, na verdade, são as coordenadas da rainha. Bishop Tower possibleMoves x y self.x, self.y O Cavaleiro Agora para o cavaleiro! https://gist.github.com/NicolaM94/c19d2c41e4461c66fca54aab239ede9e?embedable=true#file-knight-py 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, . 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. não precisamos realmente implementar seu move-set 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! https://gist.github.com/NicolaM94/75826a753105c3a3aecae4f6890b631a?embedable=true#file-check-py Agora simplesmente criamos uma variável 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 para calcular seu conjunto completo de movimentos. coordenadas : se estiverem, imprimimos que o rei foi verificado por aquela peça em particular. O resultado aqui é algo assim: blackKing possibleMoves Assim que o tivermos, verificamos se as blackKing estão presentes nesses conjuntos de movimentos 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 ou se realmente é xeque-mate? Para isso, precisamos calcular o conjunto de movimentos do rei. se o rei ainda tem alguma chance de sobreviver https://gist.github.com/NicolaM94/cca18293bedb2293bbc621e86236571f?embedable=true#file-king-py Vamos descrevê-lo um pouco. Primeiro, definimos nossa classe e coordenadas como antes. Depois disso, criamos o método 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, e retornamos apenas os . possibleMoves verificamos quais movimentos são ilegais (movimento fora do tabuleiro) validMoves Então agora, para verificar se o rei ainda tem chance de sobreviver, Para fazer isso, simplesmente percorremos os movimentos do rei e os outros movimentos. precisamos verificar se algum de seus movimentos possíveis não está em outro conjunto de movimentos de peças. https://gist.github.com/NicolaM94/9bdb64c10e2d039905e6353ed37cc101?embedable=true#file-checkmate-py 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 , devemos considerar o tempo para inicializar essa instância. instância de uma classe Peças como o não possuem nenhum loop dentro de si e não dependem de nenhuma dimensão variável, portanto podemos considerá-las O(1); peão ou o cavalo A é 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 à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: torre não importa onde ela esteja no tabuleiro, seus movimentos são limitados Infelizmente, não podemos dizer o mesmo do , 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). bispo A precisa do conjunto de movimentos da torre e do bispo combinados. Pois , o tc do bispo prevalece sobre o tc da torre. Assim, devemos considerar um tc de O(n) também para a rainha. rainha ao avaliar a complexidade do tempo devemos focar no pior cenário Por fim, o tem um conjunto de movimentos codificado, mas também um . 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. rei processo de validação envolvido que usa um loop for Neste ponto, usamos . 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. um loop for para cada peça para verificar e imprimir o status do cheque do rei preto Por fim, , que com certeza será um tc de O(n²), dependendo do número de jogadas do rei e das jogadas das demais peças. utilizamos um loop for duplo (interior) para verificar o xeque-mate É 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.

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Este áudio é produzido no idioma original da história!

Muito longo; Para ler

Making security fun one episode at a time

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

Muito longo; Para ler

Nicola Moro

STORY’S CREDIBILITY

Code License

Guide

About Author

Rótulos

Languages

ESTE ARTIGO FOI APRESENTADO EM...

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

Muito longo; Para ler

Nicola Moro

STORY’S CREDIBILITY

Code License

Guide

About Author

Rótulos

Languages

ESTE ARTIGO FOI APRESENTADO EM...

HISTÓRIAS RELACIONADAS