Oito rainhas quebra-cabeça

ImprimirCitar

	um	b)	c	D	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	um	b)	c	D	e	f	g	h

A única solução simétrica para o quebra-cabeça de oito rainhas (até rotação e reflexão)

O quebra-cabeça das oito rainhas é o problema de colocar oito rainhas em um tabuleiro de xadrez 8 × 8 de modo que duas rainhas não ameacem uma à outra; assim, uma solução requer que duas rainhas não compartilhem a mesma linha, coluna ou diagonal. Existem 92 soluções. O problema foi colocado pela primeira vez em meados do século XIX. Na era moderna, é frequentemente usado como um problema de exemplo para várias técnicas de programação de computadores.

O quebra-cabeça das oito rainhas é um caso especial do problema mais geral das n rainhas de colocar n rainhas não atacantes em um n×n tabuleiro de xadrez. Existem soluções para todos os números naturais n com exceção de n = 2 e n = 3. Embora o número exato de soluções seja conhecido apenas para n ≤ 27, a taxa de crescimento assintótica do número de soluções é aproximadamente (0,143 n)ⁿ.

História

O compositor de xadrez Max Bezzel publicou o quebra-cabeça das oito rainhas em 1848. Franz Nauck publicou as primeiras soluções em 1850. Nauck também estendeu o quebra-cabeça para o problema das n rainhas, com n rainhas em um tabuleiro de xadrez de n×n casas.

Desde então, muitos matemáticos, incluindo Carl Friedrich Gauss, trabalharam tanto no quebra-cabeça das oito rainhas quanto em sua versão generalizada de n-rainhas. Em 1874, S. Gunther propôs um método usando determinantes para encontrar soluções. J.W.L. Glaisher refinou a abordagem de Gunther.

Em 1972, Edsger Dijkstra usou este problema para ilustrar o poder do que ele chamou de programação estruturada. Ele publicou uma descrição altamente detalhada de um algoritmo de retrocesso em profundidade.

Construindo e contando soluções quando n = 8

O problema de encontrar todas as soluções para o problema das 8 rainhas pode ser bastante caro computacionalmente, pois existem 4.426.165.368 arranjos possíveis de oito rainhas em um tabuleiro de 8 × 8, mas apenas 92 soluções. É possível usar atalhos que reduzam os requisitos computacionais ou regras práticas que evitem técnicas computacionais de força bruta. Por exemplo, aplicando uma regra simples que escolhe uma rainha de cada coluna, é possível reduzir o número de possibilidades para 16.777.216 (ou seja, 8⁸) combinações possíveis. A geração de permutações reduz ainda mais as possibilidades para apenas 40.320 (ou seja, 8!), que podem ser verificadas quanto a ataques diagonais.

O quebra-cabeça das oito rainhas tem 92 soluções distintas. Se as soluções que diferem apenas pelas operações de simetria de rotação e reflexão do tabuleiro forem contadas como uma, o quebra-cabeça tem 12 soluções. Estas são chamadas de soluções fundamentais; representantes de cada um são mostrados abaixo.

Uma solução fundamental geralmente tem oito variantes (incluindo sua forma original) obtidas girando 90, 180 ou 270° e, em seguida, refletindo cada uma das quatro variantes rotacionais em um espelho em uma posição fixa. No entanto, uma das 12 soluções fundamentais (solução 12 abaixo) é idêntica à sua própria rotação de 180°, portanto, possui apenas quatro variantes (ela mesma e sua reflexão, sua rotação de 90° e a reflexão desta). Tais soluções têm apenas duas variantes (ela mesma e seu reflexo). Assim, o número total de soluções distintas é 11×8 + 1×4 = 92.

Todas as soluções fundamentais são apresentadas abaixo:

	um	b)	c	D	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	um	b)	c	D	e	f	g	h

Solução 1

	um	b)	c	D	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	um	b)	c	D	e	f	g	h

Solução 2

	um	b)	c	D	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	um	b)	c	D	e	f	g	h

Solução 3

	um	b)	c	D	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	um	b)	c	D	e	f	g	h

Solução 4

	um	b)	c	D	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	um	b)	c	D	e	f	g	h

Solução 5

	um	b)	c	D	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	um	b)	c	D	e	f	g	h

Solução 6

	um	b)	c	D	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	um	b)	c	D	e	f	g	h

Solução 7

	um	b)	c	D	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	um	b)	c	D	e	f	g	h

Solução 8

	um	b)	c	D	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	um	b)	c	D	e	f	g	h

Solução 9

	um	b)	c	D	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	um	b)	c	D	e	f	g	h

Solução 10

	um	b)	c	D	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	um	b)	c	D	e	f	g	h

Solução 11

	um	b)	c	D	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	um	b)	c	D	e	f	g	h

Solução 12

A solução 10 tem a propriedade adicional de que não há três rainhas em linha reta. As soluções 1 e 8 têm uma linha de 4 rainhas.

Existência de soluções

Algoritmos de força bruta para contar o número de soluções são gerenciáveis computacionalmente para $n = 8$ , mas seriam intratáveis para problemas de $n \geq 20$ , como 20! = 2,433 × 10¹⁸. Se o objetivo é encontrar uma única solução, pode-se mostrar que existem soluções para todo n ≥ 4 sem nenhuma pesquisa. Essas soluções exibem padrões em degraus, como nos exemplos a seguir para n = 8, 9 e 10:

	um	b)	c	D	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	um	b)	c	D	e	f	g	h

Solução de escada para 8 rainhas

	um	b)	c	D	e	f	g	h	Eu...
9										9
8										8
7										7
6										6
5										5
4										4
3										3
2										2
1										1
	um	b)	c	D	e	f	g	h	Eu...

Solução de escada para 9 rainhas

	um	b)	c	D	e	f	g	h	Eu...	JJ
10.											10.
9											9
8											8
7											7
6											6
5											5
4											4
3											3
2											2
1											1
	um	b)	c	D	e	f	g	h	Eu...	JJ

Solução de escada para 10 rainhas

Os exemplos acima podem ser obtidos com as seguintes fórmulas. Seja (i, j) o quadrado na coluna i e na linha j no n × n tabuleiro de xadrez, k um número inteiro.

Uma abordagem é

Se o restante da divisão n 6 não é 2 ou 3, então a lista é simplesmente todos os números pares seguidos de todos os números ímpares não maiores do que n.
Caso contrário, escreva listas separadas de números pares e ímpares (2, 4, 6, 8 – 1, 3, 5, 7).
Se o restante for 2, troque 1 e 3 em lista ímpar e mova 5 para o final (3, 1, 7, 5).
Se o restante for 3, mova 2 para o final da lista uniforme e 1,3 para o fim da lista ímpar (4, 6, 8, 2 - 5, 7, 9, 1, 3).
Anexar lista ímpar para a lista uniforme e colocar rainhas nas linhas dadas por esses números, da esquerda para a direita (a2, b4, c6, d8, e3, f1, g7, h5).

Para $n = 8$ , isso resulta na solução fundamental 1 acima. Seguem mais alguns exemplos.

14 rainhas (responsáveis 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
15 rainhas (principal 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
20 rainhas (manutenção 2): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5.

Soluções de contagem para outros tamanhos n

Enumeração exata

Não existe uma fórmula conhecida para o número exato de soluções para colocar n rainhas em um $n \times n$ board, ou seja, o número de conjuntos independentes de tamanho n em um $n \times n$ gráfico da rainha. O tabuleiro 27 × 27 é o tabuleiro de ordem mais alta que foi completamente enumerado. As tabelas a seguir fornecem o número de soluções para o problema das n rainhas, tanto fundamentais (sequência A002562 no OEIS) quanto todas (sequência A000170 no OEIS), para todos os casos conhecidos.

n	fundamental	Todos
1	1	1
2	0	0
3	0	0
4	1	2
5	2	10.
6	1	4
7	6	40
8	12	92
9	46.	352
10.	92	724
11	341	2,680
12	1,787	14,200
13	9,233	73,712
14	45,752	365,596
15	28,053	279,184
16.	1,846,955	14,772,512
17.	11,977,939	95,815,104
18.	83,263,591	666,090,624
19	621,012,754	4,968,057,848
20.	4,878,666,808	39,029,188,884
21	39,333,324,973	314,666,222,712
22	336,376,244,042	2,691,008,701,644
23	3,029,242,658,210	24,233,937,684,440
24.	28,439,272,956,934	227,514,171,973,736
25	275,986,683,743,434	2,207,893,435,808,352
26	2,789,712,466,510,289	22,317,699,616,364,044
27	29,363,495,934,315,694	234,907,967,154,122,528

Enumeração assintótica

Em 2021, Michael Simkin provou que para grandes números n, o número de soluções n problema de rainhas é aproximadamente $(0.143n)^{n}}$ . Mais precisamente, o número ${displaystyle {mathcal {Q}}(n)}$ de soluções tem crescimento assintotic

{displaystyle {mathcal {Q}}(n)=((1pm o(1))ne^{-alpha })^{n}}

- Sim.

Se um em vez considerar um tabuleiro de xadrez toroidal (onde as diagonais "embrulham" da borda superior para a parte inferior e da borda esquerda para a direita), só é possível colocar n rainhas em um ${displaystyle ntimes n}$ placa se ${displaystyle nequiv 1.5mod 6.}$ Neste caso, o número assintótico de soluções é

{displaystyle T(n)=((1+o(1))ne^{-3})^{n}.}

Problemas relacionados

Dimensões mais altas

Encontre o número de rainhas não atacantes que podem ser colocadas em um espaço de tamanho n de xadrez ddimensional. Mais de n rainhas podem ser colocadas em algumas dimensões superiores (o menor exemplo é quatro rainhas não atacantes em um espaço de xadrez 3×3×3), e é de fato conhecido que para qualquer k, existem dimensões superiores onde n^k rainhas não são suficientes para atacar todos os espaços.

Usando peças diferentes de rainhas

Em um tabuleiro de 8×8 pode-se colocar 32 cavalos, ou 14 bispos, 16 reis ou oito torres, de forma que duas peças não se ataquem. No caso dos cavalos, uma solução fácil é colocar um em cada quadrado de uma determinada cor, pois eles se movem apenas para a cor oposta. A solução também é fácil para torres e reis. Dezesseis reis podem ser colocados no tabuleiro, dividindo-o em 2 por 2 quadrados e colocando os reis em pontos equivalentes em cada quadrado. A colocação de n torres em um tabuleiro n×n está em correspondência direta com as matrizes de permutação de ordem n.

Variações de xadrez

Problemas relacionados podem ser solicitados para variações de xadrez, como shogi. Por exemplo, o problema dos n+k reis dragões pede para colocar k peões de shogi e n+ k reis dragões mutuamente não-atacantes em um tabuleiro de shogi n×n.

Placas não padronizadas

Pólya estudou o problema de n rainhas em um tabuleiro toroidal ("em forma de rosquinha") e mostrou que existe solução em um n× n se e somente se n não for divisível por 2 ou 3. Em 2009, Pearson e Pearson preencheram placas tridimensionais algoritmicamente (n× n×n) com n² rainhas, e propôs que múltiplos delas podem produzir soluções para um problema de quatro versão dimensional do quebra-cabeça.

Dominação

Dado um tabuleiro n×n, o número de dominação é o número mínimo de rainhas (ou outras peças) necessárias para atacar ou ocupar cada quadrado. Para n = 8, o número de domínio da rainha é 5.

Rainhas e outras peças

As variantes incluem misturar rainhas com outras peças; por exemplo, colocar m rainhas e m cavalos em um tabuleiro n×n de modo que nenhuma peça ataque outra ou colocando rainhas e peões de forma que duas rainhas não se ataquem.

Quadrados mágicos

Em 1992, Demirörs, Rafraf e Tanik publicaram um método para converter alguns quadrados mágicos em soluções com n-rainhas e vice-versa.

Praças latinas

Em uma matriz n×n, coloque cada dígito de 1 a n em locais n na matriz de modo que não haja duas instâncias do mesmo dígito na mesma linha ou coluna.

Tampa exata

Considere uma matriz com uma coluna primária para cada um dos n níveis do quadro, uma coluna primária para cada um dos arquivos n e uma coluna secundária para cada das 4n − 6 diagonais não triviais do tabuleiro. A matriz tem n² linhas: uma para cada posição de rainha possível, e cada linha tem um 1 nas colunas correspondentes à classificação, arquivo e diagonais e um 0 em todas as outras colunas. Então o problema das n rainhas é equivalente a escolher um subconjunto das linhas dessa matriz de modo que toda coluna primária tenha 1 precisamente em uma das linhas escolhidas e toda coluna secundária tenha 1 em no máximo uma das linhas escolhidas; este é um exemplo de um problema generalizado de cobertura exata, do qual o sudoku é outro exemplo.

n-quere a conclusão

O problema de conclusão pergunta se, dado um tabuleiro n×n no qual algumas rainhas já foram colocadas, é possível colocar uma rainha em cada linha restante de modo que não há duas rainhas se atacando. Esta e outras questões relacionadas são NP-completas e #P-completas. Qualquer colocação de no máximo n/60 rainhas pode ser concluída, embora existam configurações parciais de aproximadamente n/4 rainhas que não podem ser concluídas.

Exercício de design de algoritmo

Encontrar todas as soluções para o quebra-cabeça das oito rainhas é um bom exemplo de um problema simples, mas não trivial. Por esta razão, é frequentemente usado como um problema de exemplo para várias técnicas de programação, incluindo abordagens não tradicionais, como programação de restrição, programação lógica ou algoritmos genéticos. Na maioria das vezes, é usado como um exemplo de um problema que pode ser resolvido com um algoritmo recursivo, formulando o problema de n rainhas indutivamente em termos de adicionar uma única rainha a qualquer solução para o problema de colocação n−1 rainhas em um tabuleiro n×n. A indução chega ao fundo com a solução para o 'problema' de colocar 0 rainhas no tabuleiro, que é o tabuleiro vazio.

Essa técnica pode ser usada de maneira muito mais eficiente do que o algoritmo de busca de força bruta ingênuo, que considera todos os 64⁸ = 2⁴⁸ = 281.474.976.710.656 possíveis posicionamentos cegos de oito rainhas e, em seguida, filtra-os para remover todos os posicionamentos que colocam duas rainhas no mesmo quadrado (deixando apenas 64!/56! = 178.462.987.637.760 posicionamentos possíveis) ou em posições de ataque mútuo. Este algoritmo muito pobre irá, entre outras coisas, produzir os mesmos resultados repetidamente em todas as diferentes permutações das atribuições das oito rainhas, bem como repetir os mesmos cálculos repetidamente para os diferentes subconjuntos de cada uma. solução. Um algoritmo de força bruta melhor coloca uma única rainha em cada linha, levando a apenas 8⁸ = 2²⁴ = 16.777.216 posições cegas.

É possível fazer muito melhor do que isso. Um algoritmo resolve o quebra-cabeça das oito torres gerando as permutações dos números de 1 a 8 (das quais há 8! = 40.320) e usa os elementos de cada permutação como índices para colocar uma rainha em cada linha. Em seguida, rejeita as placas com posições de ataque diagonais.

Esta animação ilustra backtracking para resolver o problema. Uma rainha é colocada em uma coluna que é conhecida por não causar conflito. Se uma coluna não for encontrada, o programa retorna ao último bom estado e, em seguida, tenta uma coluna diferente.

O programa de busca em profundidade com retrocesso, uma ligeira melhoria no método de permutação, constrói a árvore de busca considerando uma linha do tabuleiro por vez, eliminando a maioria das posições do tabuleiro sem solução em um estágio muito inicial de sua construção. Por rejeitar ataques de torre e diagonal mesmo em tabuleiros incompletos, ele examina apenas 15.720 possíveis colocações de rainhas. Uma melhoria adicional, que examina apenas 5.508 rainhas possíveis posicionamentos, é combinar o método baseado em permutação com os primeiros método de poda: as permutações são geradas primeiro em profundidade e o espaço de busca é podado se a permutação parcial produzir um ataque diagonal. A programação de restrições também pode ser muito eficaz nesse problema.

min-conflicts solução para 8 rainhas

Uma alternativa à pesquisa exaustiva é um 'reparo iterativo' algoritmo, que normalmente começa com todas as rainhas no tabuleiro, por exemplo, com uma rainha por coluna. Em seguida, conta o número de conflitos (ataques) e usa uma heurística para determinar como melhorar a colocação das rainhas. Os 'conflitos mínimos' A heurística – mover a peça com o maior número de conflitos para o quadrado na mesma coluna onde o número de conflitos é menor – é particularmente eficaz: encontra facilmente uma solução até mesmo para o problema de 1.000.000 de rainhas.

Ao contrário da busca retroativa descrita acima, o reparo iterativo não garante uma solução: como todos os procedimentos gananciosos, ele pode ficar preso em um ótimo local. (Nesse caso, o algoritmo pode ser reiniciado com uma configuração inicial diferente.) Por outro lado, ele pode resolver tamanhos de problemas que estão várias ordens de magnitude além do escopo de uma busca em profundidade.

Como alternativa ao retrocesso, as soluções podem ser contadas enumerando recursivamente soluções parciais válidas, uma linha por vez. Em vez de construir posições de tabuleiro inteiras, diagonais e colunas bloqueadas são rastreadas com operações bit a bit. Isso não permite a recuperação de soluções individuais.

Exemplo de programa

O programa a seguir é uma tradução da solução de Niklaus Wirth para a linguagem de programação Python, mas sem a aritmética de índice encontrada no original e, em vez disso, usa listas para manter o código do programa o mais simples possível. Usando uma co-rotina na forma de uma função geradora, ambas as versões do original podem ser unificadas para computar uma ou todas as soluções. Apenas 15.720 possíveis colocações de rainhas são examinadas.

de - Sim.(n, Eu..., um, b), c: se Eu... < n: para JJ em gama(n: se JJ não em um e Eu...+JJ não em b) e Eu...- Não.JJ não em c: a partir de - Sim.(n, Eu...+1, um+Não.JJ] b)+Não.Eu...+JJ] c+Não.Eu...- Não.JJ] mais: rendimento umpara solução em - Sim.(8, 0, [] [] [] impressão(solução)

Na cultura popular

No jogo The 7th Guest, o 8o Puzzle: "The Queen's Dilemma" na sala de jogos da mansão Stauf é o quebra-cabeça de fato oito rainhas.
No jogo Professor Layton e o Curious Village, o 130o quebra-cabeça: "Muitas rainhas 5"(クイーンのの5) é um quebra-cabeça de oito rainhas.

Contenido relacionado

Más resultados...