No jogo de xadrez, há uma peça chamada rainha que pode atacar qualquer outra peça que esteja na mesma linha, coluna ou diagonal. No xadrez, normalmente existem dois lados, preto e branco, com cada peça pertencendo a uma das equipes. Peças não podem atacar peças pertencem ao mesmo time.
Seu objetivo é descobrir os maiores exércitos pacíficos coexistentes para um tabuleiro quadrado. Esse é o maior número de rainhas em preto e branco que podem caber no quadro, de modo que duas rainhas não possam se atacar e o número de rainhas pretas é igual ao número de rainhas brancas.
Você receberá como entrada o comprimento lateral de um quadro quadrado e deverá produzir o número de tamanho dos maiores exércitos coexistentes pacíficos que podem caber nesse quadro.
Isso é código-golfe, portanto, regras padrão para a tag se aplicam.
Esses casos de teste abrangem todas as respostas conhecidas. Sua solução deve ser uma resposta generalizada que, com tempo e poder de computação suficientes, possa computar a solução para qualquer valor de entrada.
1: 0 2: 0 3: 1 4: 2 5: 4 6: 5 7: 7 8: 9 9: 12 10: 14 11: 17 12: 21 13: 24
Respostas:
C, 476 bytes, DFS iterando rainhas brancas, O (2 n 2 )
518 bytes, DFS com poda, O (2 n )
577 bytes, DFS iterando rainhas brancas e pretas, O (?)
Basicamente, o código itera as possibilidades da rainha branca e verifica se a rainha negra pode ser colocada então.
Tabela de referência de velocidade (em segundos):
fonte
Clingo , 90 bytes
Demo
fonte
Python 2 |
325284217 bytesExperimente online!
Editar: tuplas substituídas por números inteiros em ge outras edições triviais.
Edit2: bytes até 217, graças ao musicman523 e CalculatorFeline !
Como funciona
O programa itera sobre todas as posições possíveis das
nrainhas e filtra os pontos não pacíficosgcausados pela posição das rainhas. Se os pontos restantes forem maiores quenisso, significa que é possível que osnexércitos da rainha permaneçam em paz. Se para o próximo valor den, nenhuma situação pacífica for encontrada, o programa sairá com o código de saída:,n-1que é a resposta. Em suma, é força brutaO programa pode ser acelerado alterando as duas últimas linhas para
fonte
from module import*para importar tudo de um módulo e salvar bytes.Haskell ,
169 156 153152 152 bytesDefine uma função
g, pode ser ainda mais jogável. Experimente online! No TIO, quando compilado-O2, leva cerca de 36 segundos para n = 4 e expira em n = 5 . A complexidade do tempo deve ser O (n 2 4 n 2 ) .Explicação
Nós iteramos sobre os valores possíveis para o número de rainhas ( q ). Para cada q , geramos todos os pares de tamanho- q subconjuntos de [1..n] 2 , um conjunto de rainhas pretas ( b ) e uma das rainhas brancas ( w ). Então, cada elemento de b é verificado em relação a cada elemento de w para ver se eles compartilham uma linha, coluna, diagonal ou anti-diagonal. Isso também cuida de duas partes que compartilham a mesma coordenada. O maior valor de q que admite uma configuração pacífica é o valor final.
As duas primeiras linhas do programa definem a função
!, que calcula asksubsequências de comprimento de uma listax. A implementação é feita por uma recursão básica: escolha o primeiro elemento que está no conjunto ou não e recue até a cauda, diminuindo,kse necessário. Em seguida, a lista vazia ou alcançada, verifique issok==0.A segunda função auxiliar
&pega um númeroq(número de rainhas em ambos os lados) e uma listal(as coordenadas x da placa, também usadas como coordenadas y) e retorna um valor booleano indicando se existe uma configuração pacífica. Primeirop, calculamos a lista deqsubsequências de comprimento da lista de valores[x,y,x-y,x+y], ondexe oyintervalo está acimal. Eles representam a linha, coluna, diagonal e anti-diagonal de um quadrado(x,y)no quadro.Em seguida, temos o resultado de
q&l. Chamamos duas subseqüênciasbewdep, emparelhar os 4 listas de-los juntos em todas as formas possíveis, e verifique se eles são sempre diferentes em todas as 4 coordenadas. Se algumas opções debewresultarem em um resultado verdadeiro, retornamosTrue.A última linha é a função principal. Dado
n, ele simplesmente encontra o maior valor possívelqpara o qualq&[1..n]é verdadeiro.fonte