Como 8 Rainhas Funciona

Dependendo de quais círculos você frequenta - digamos, seu melhor amigo é um programador de computador e sua irmã é um prodígio do xadrez - você já deve estar familiarizado com o quebra-cabeça das 8 rainhas. Para o resto de nós, o quebra-cabeça das 8 Rainhas (ou problema ou simplesmente "8 Rainhas") provavelmente não é algo em que passamos muito tempo pensando.

O quebra-cabeça é bastante simples. Como você pode colocar 8 rainhas em um tabuleiro de xadrez para que duas não se ataquem? Alternativamente, a pergunta às vezes é declarada como "Qual é o número máximo de rainhas que podem ser colocadas em um tabuleiro de xadrez, para que duas não possam atacar uma à outra", mas esse quebra-cabeça se torna muito menos difícil quando você pesquisa no Google , e o termo "o quebra-cabeça das 8 Rainhas" aparece.

Você pode estar se perguntando por que na Terra alguém se importa onde você mantém suas oito rainhas. E sim, superficialmente, é apenas um quebra-cabeça estratégico. Mas (e é aqui que é útil ter um melhor amigo que codifique computadores) o quebra-cabeça das 8 Rainhas é uma ótima maneira de testar o conhecimento e a alfabetização de um programador.

Agora, não tenha medo. Você não será forçado a entender os meandros da programação de computadores para continuar lendo. Mas você deve saber que resolver o quebra-cabeça pode ser alcançado usando um código de programação - e alguns são mais elegantes do que outros. Por exemplo, você pode definitivamente encontrar a solução usando um programa de "força bruta" que pode simplesmente passar por todos os posicionamentos possíveis, descartando um de cada vez. Mas um codificador sofisticado será capaz de construir um programa que tenha atalhos usando um algoritmo mais refinado para encontrar uma solução mais rapidamente. Ser capaz de encontrar maneiras incomuns ou originais de codificar uma solução para um problema tão amplo quanto 8 Queens pode ser um ótimo teste para o conhecimento de um codificador.

Portanto, embora não estejamos colocando 1s e 0s em você para explicar como funciona o 8 Queens, daremos algumas soluções para o quebra-cabeça.

Agora que temos a premissa básica do quebra-cabeça, devemos estabelecer por que o problema é tão único. Para fazer isso, vamos aprimorar nossos conceitos básicos de xadrez. Em um jogo de xadrez, a rainha é uma força a ser reconhecida. Ela pode se mover em linha reta na vertical, na horizontal ou na diagonal, quantas casas quiser. O único problema é que ela não pode pular peças, então se um peão estiver em seu caminho, ela deve capturá-lo e parar.

Isso é o que torna o quebra-cabeça das 8 Rainhas interessante. Se as rainhas podem se mover para cima, para baixo, para a esquerda, para a direita e na diagonal, então quantas realezas em guerra podem ocupar o tabuleiro sem compartilhar a mesma linha, coluna ou linha diagonal? Agora, você pode pensar que seria uma ótima ideia apenas colocar uma dama no tabuleiro, tentando combinações diferentes antes de acertar todas elas. E claro, isso é possível. Mas existem 4.426.165.368 soluções potenciais, então você pode considerar encontrar um atalho.

Antes de colocarmos nossas rainhas em 4 bilhões de quadrados diferentes, vamos primeiro reconhecer que alguém realmente sentou um dia e decidiu que essa seria uma boa maneira de desperdiçar uma tarde ou duas. Previsivelmente, não era alguém que tinha reprises de "My Big Fat Gypsy Wedding" para se atualizar - era um mestre de xadrez e compositor alemão do século 19 chamado Max Bezzel. (Um compositor de xadrez é alguém que inventa problemas de xadrez - também conhecidos como quebra-cabeças - para resolver.) Ele apareceu pela primeira vez na revista alemã de xadrez DieSchachzeitung em 1848.

Bezzel não estava tão interessado em resolver o quebra-cabeça; ele estava satisfeito em simplesmente fazer a pergunta. No entanto, em 1850, o matemático Franz Nauck escreveu outro artigo que discutia o problema. (As primeiras soluções para o quebra-cabeça foram finalmente resolvidas por Nauck.) Isso chamou a atenção de Karl Gauss, um matemático do século 19 conhecido por descobrir a teoria fundamental da álgebra. Quando Gauss se interessou em encontrar a solução, outros o seguiram e diferentes abordagens para resolver o quebra-cabeça começaram a surgir.

Não é de surpreender que "oito" seja a resposta para nossa pergunta específica de quantas rainhas podem ser colocadas em um tabuleiro sem atacar umas às outras. Mas vamos explorar de quantas maneiras oito rainhas podem ser colocadas e como isso é estabelecido.

Conversamos sobre como os programas de computador de força bruta são uma maneira de resolver o quebra-cabeça - e testar 4.426.165.368 possibilidades manualmente certamente se qualificaria como força bruta - mas existem maneiras mais fáceis de restringir as soluções. Um método simplificado foi fornecido quando JWL Glaisher, outro matemático, publicou um artigo em 1874 descrevendo seu uso de determinantes para encontrar uma solução. "Determinantes" soa um pouco difícil, mas tudo o que você realmente precisa saber é que Glaisher basicamente construiu uma matriz e - usando um sistema que ele derivou dessa matriz - foi capaz de reduzir as soluções possíveis para 92.

E 92 soluções permanece. Mas não se deixe enganar; você não poderá alinhar 92 tabuleiros de xadrez, cada um com um conjunto único de 8 rainhas resolvidas pacificamente, porque na verdade existem apenas 12 soluções únicas.

Confuso? A diferença entre 12 soluções únicas e 92 soluções fundamentais está, literalmente, em como você as vê. Embora você possa configurar 12 tabuleiros diferentes distintamente com suas oito rainhas, basta você simplesmente virar o tabuleiro - ou mesmo refleti-lo em um espelho - para fazer com que os tabuleiros pareçam tecnicamente diferentes e, assim, tenham um "diferente" solução. (Isso é chamado de operações de simetria rotacional e reflexiva.) Então você pega suas 12 pranchas únicas, gira-as 90, 180 e 270 graus e depois as reflete em cada rotação. Mas mais uma coisa - uma placa única é simétrica, então parece a mesma de dois ângulos. Enquanto todas as outras placas têm oito variantes, a placa simétrica tem apenas quatro. Então, em vez de 12 tabuleiros vezes 8 variações (96), estamos na verdade subtraindo os quatro que não existem com o tabuleiro simétrico. O que obtemos? 92 soluções fundamentais.

Agora, não deixe a matemática enganar você. Você sempre pode encontrar um tabuleiro de xadrez e tentar descobrir algumas posições para si mesmo. (Encontrar uma resposta, é claro, é muito mais fácil do que encontrar todas as 12.) E existem até programas na Web que permitem que você descubra algumas soluções diferentes. (Aviso: eles podem fazer você se sentir estúpido.)

Antes de embaralhar suas rainhas, confira a próxima página para saber mais informações.

Sendo uma pessoa menos interessada em um algoritmo do que em um alfabeto, eu não tinha grandes esperanças de entender o quebra-cabeça das 8 Rainhas. Embora eu tivesse certeza de que tinha algum tipo de aplicação prática, não consegui ver. Ironicamente, foi quando entendi a vastidão do problema que comecei a ver por que ele poderia ser útil. Encontrar um conjunto de soluções a partir de uma enorme quantidade de possibilidades é uma das razões pelas quais o código existe. O problema das 8 Rainhas desafia programadores e matemáticos a descobrir novas técnicas para simplificar a busca.

Links Relacionados

Origens