Permutações e a Ideia das N-Rainhas
Posicione itens e retroceda quando houver conflitos.
Permutações e a Ideia das N-Rainhas é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
Dos subconjuntos às ordenações
Uma permutação é uma disposição de todos os elementos em uma determinada ordem. Gerá-las é a próxima habilidade de retrocesso depois dos subconjuntos. 🔀
Quantas permutações existem
Existem n fatorial permutações de n itens, porque o primeiro espaço tem n opções, o próximo tem n menos um, e assim por diante. Esse número cresce rapidamente.
Coloque um item de cada vez
A recursão preenche as posições da esquerda para a direita. A cada etapa, você escolhe um elemento não utilizado, coloca-o e faz a recursão com o restante.
Registre o que foi usado
Um vetor booleano de uso indica quais elementos já foram colocados, para que cada um apareça exatamente uma vez em toda permutação.
Permutações no código
Este retrocesso coloca um valor não utilizado, faz a recursão e depois o libera para o próximo ramo.
def perm(cur):
if len(cur) == n:
out.append(cur[:]); return
for x in a:
if x not in cur:
perm(cur + [x])Use itertools quando permitido
Em competições rápidas, o itertools.permutations do Python fornece todas as ordenações sem que você precise escrever a recursão.
from itertools import permutations
for p in permutations(a):
print(p)O problema das N rainhas
O problema das N rainhas pede que você coloque n rainhas em um tabuleiro n por n de modo que nenhuma ataque as outras. É o quebra-cabeça clássico de retrocesso. 👑
Uma rainha por linha
Como duas rainhas não podem compartilhar uma linha, você coloca exatamente uma rainha por linha e escolhe apenas sua coluna. Isso reduz muito a busca.
Verifique os três conflitos
Antes de colocar uma rainha, rejeite qualquer coluna ou diagonal já ocupada. Registre as colunas usadas e as duas direções diagonais em conjuntos.
if c in cols or r-c in d1 or r+c in d2:
continueFaça retrocesso em um beco sem saída
Se nenhuma coluna funcionar em uma linha, o ramo falha. Você retrocede, remove a última rainha e tenta a próxima opção dela.
O padrão compartilhado
Permutações e N rainhas têm a mesma estrutura: escolher, recorrer, desfazer. Quando você a identifica, a maioria dos problemas de posicionamento pode ser resolvida com o mesmo modelo.
Verificação rápida
Por que o problema das N rainhas coloca apenas uma rainha por linha?
Recapitulação: escolha, recorra, desfaça
Você gerou permutations colocando itens não utilizados e aprendeu que N rainhas usam o mesmo padrão de escolher, recorrer e desfazer, com verificações de conflitos. 🎯
Perguntas Frequentes
A aula “Permutações e a Ideia das N-Rainhas” é grátis?
Sim — o texto completo de “Permutações e a Ideia das N-Rainhas” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Permutações e a Ideia das N-Rainhas”?
Posicione itens e retroceda quando houver conflitos. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Permutações e a Ideia das N-Rainhas”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Pense Recursivamente: Base e Recursão
- Gere Todos os Subconjuntos
- Permutações e a Ideia das N-Rainhas
- Faça Poda para Sobreviver ao Limite de Tempo