O problema das oito damas
O problema das oito damas pede oito damas em um tabuleiro de xadrez sem que duas se ataquem. O compositor de problemas de xadrez Max Bezzel o publicou em 1848, e ele se tornou o primeiro exemplo clássico de busca com backtracking.
Um problema de xadrez de 1848
Max Bezzel, um compositor alemão de problemas de xadrez, propôs o problema em uma revista de xadrez de Berlim em 1848. Franz Nauck publicou todas as 92 soluções em 1850 e fez a mesma pergunta para tabuleiros maiores. Carl Friedrich Gauss acompanhou o problema com interesse e o discutiu em suas cartas.
Uma dama por linha e coluna
Oito damas que não se atacam precisam estar em oito linhas diferentes e em oito colunas diferentes. Então uma solução é um embaralhamento dos números de 1 a 8, uma permutação, com uma regra a mais: duas damas não podem compartilhar uma diagonal. Das 40.320 permutações, só 92 passam.
Backtracking
O backtracking constrói uma solução uma peça de cada vez e volta atrás assim que chega a um beco sem saída. Para as damas: coloque uma dama na primeira casa segura da próxima linha e, quando uma linha não tiver nenhuma casa segura, volte para a linha de cima e avance aquela dama. Em 1972, Edsger Dijkstra usou o problema para explicar a programação estruturada com exatamente esta busca.
Simetria
Gire o tabuleiro um quarto de volta, ou o reflita, e uma solução continua sendo uma solução. Isso dá até oito versões de cada uma. As 92 soluções se dividem em 12 famílias assim: onze com 8 membros e uma com apenas 4, porque essa solução fica igual depois de meia volta.
O problema das n damas
Em um tabuleiro n×n, a pergunta é a mesma com n damas. Há soluções para todo n a partir de 4, e o número delas cresce rápido: 2 para 4×4, 92 para 8×8 e 14.200 para 12×12. Não se conhece nenhuma fórmula para a contagem; os valores recordes vêm de grandes buscas por computador.
Experimente no PictorX
Abra Oito damas e clique em uma casa para colocar uma dama; clique de novo para tirá-la. Mostrar ataques marca com um ponto as casas que as suas damas atacam, e damas em vermelho se atacam. Resolver executa a busca com backtracking um passo de cada vez e mantém as damas que você colocou. Próxima solução percorre todas as soluções em ordem, e Tamanho muda o tabuleiro de 4×4 até 12×12.
Perguntas frequentes
Quem inventou o problema das oito damas?
Max Bezzel, um compositor alemão de problemas de xadrez, em 1848. Franz Nauck publicou o primeiro conjunto completo de soluções em 1850.
Quantas soluções existem?
92 no tabuleiro padrão. Contando rotações e reflexões como uma só, são 12.
Por que o tabuleiro 6×6 tem tão poucas soluções?
Ele tem só 4, todas de uma única família. O tabuleiro 5×5, menor, tem 10. Tabuleiros maiores têm cada vez mais: 40 no 7×7 e 92 no 8×8.
O PictorX envia alguma coisa?
Não. O tabuleiro é desenhado numa tela no seu navegador. Salvar baixa um PNG, e Editar abre essa imagem no editor do PictorX.
Ferramentas relacionadas
Oito damas
Coloque oito damas em um tabuleiro de xadrez sem que nenhuma ataque outra. Tente você mesmo, veja a busca com backtracking encontrar uma solução passo a passo e percorra todas as 92 soluções.
Passeio do cavalo
Faça um cavalo de xadrez saltar por todas as casas do tabuleiro exatamente uma vez. Jogue você mesmo com as dicas de Warnsdorff ou veja Resolver terminar um passeio aberto ou fechado. Salve o caminho como PNG.
O passeio do cavalo
A história e a matemática do passeio do cavalo: Euler e Warnsdorff, passeios abertos e fechados, por que tabuleiros ímpares não têm passeio fechado e como um computador encontra um.
Torre de Hanói
Mova uma torre de discos entre três hastes no seu navegador. Um disco de cada vez, nunca um maior sobre um menor. A solução mais curta tem 2ⁿ − 1 movimentos.
Torre de Hanói
A Torre de Hanói: três hastes, um disco de cada vez e nunca um maior sobre um menor. A solução mais curta tem 2ⁿ−1 movimentos. Édouard Lucas apresentou o quebra-cabeças em 1883.
Formiga de Langton
Execute a formiga de Langton no navegador. Veja a simetria, o caos e a autoestrada de 104 passos e depois experimente regras multicoloridas, várias formigas, uma grelha hexagonal e turmites.
Pronto para experimentar?
Abra o PictorX em seu navegador – sem instalação, sem necessidade de cartão de crédito para iniciar.
Experimentar Oito damas