A primeira versão do quebra-cabeça em 1850, quando duas rainhas são pré-instaladas no tabuleiro e o jogador deve organizar as rainhas restantes (para duas soluções para o problema, veja abaixo)A tarefa das N rainhas é colocar N rainhas em um tabuleiro N × N para que nenhuma dama esteja sob a batalha da outra, com várias rainhas pré-instaladas no tabuleiro. Ou seja, no final, duas rainhas não devem estar na mesma linha ou na diagonal. O problema foi formulado pela primeira vez em 1848, e em 1850 eles surgiram com uma variante de quebra-cabeça, quando um certo número de rainhas foi colocado no tabuleiro com antecedência, e o jogador deve organizar o resto, se possível.
Pesquisadores da Universidade St Andrews (Escócia) publicaram um
artigo científico comprovando que o problema do N-Queens não é apenas o número P completo, mas também o NP completo. Além disso, o Clay Institute of Mathematics (EUA) está pronto para pagar um milhão de dólares a quem puder otimizar a solução desse problema como um problema de prova P = NP.
Como você sabe, na teoria da complexidade, #P é uma classe de problemas cuja solução é o número de caminhos bem-sucedidos, ou seja, concluindo na admissão de estados, caminhos computacionais para alguma máquina de Turing não determinística que opera em tempo polinomial. Os problemas computacionais da classe #P (problemas de contagem) estão relacionados aos problemas de decisão correspondentes da classe NP.
Os cientistas observam que esta tarefa pode ser a mais simples das tarefas completas de NP para explicar a essência desses problemas para quem conhece as regras do jogo de xadrez. Esta tarefa tem uma história muito interessante. Ao mesmo tempo, ela atraiu a atenção de Gauss, que até cometeu um pequeno erro em sua decisão (no quadro 8 × 8, ele relatou 76 decisões, mas depois reconheceu quatro delas erradas, de modo que restavam apenas 72, e mais tarde Gauss estabeleceu todas as 92 decisões. para uma placa 8 × 8).
Uma generalização do problema para o quadro N × N atraiu a atenção de muitos matemáticos. Nos últimos meio século, várias dezenas de artigos científicos dedicados a esse problema foram publicados. Pelo menos seis deles são citados mais de 400 vezes no Google Scholar: isto é Golomb & Baumert, 1965; Bitner e Reingold, 1975; Mackworth e Freuder, 1985; Minton, Johnston, Philips e Laird, 1992; Selman, Levesque e Mitchell, 1992; Crawford, Ginsberg, Luks e Roy, 1996.
A complexidade do problema do N-Queens é frequentemente mal avaliada. Mesmo em trabalhos amplamente citados, costuma ser chamado de problema NP-hard (NP-hard), mas será apenas se P = NP. De fato, a versão computacional do problema, ou seja, a determinação do número de soluções para N rainhas, é uma
sequência A000170 da Enciclopédia on-line de
sequências inteiras . Esta sequência é agora conhecida como máximo para n = 27, onde o número de soluções excede 2,34 × 10
17 . Nenhuma solução mais eficaz para o problema é conhecida do que uma simples pesquisa exaustiva. Assim, para n = 27 em 2016, foi utilizada uma pesquisa paralela em larga escala no FPGA.
Ao mesmo tempo, se o computador começar a enumerar as possíveis posições de rainhas em uma placa de célula 1000 × 1000, ele carregará essa tarefa para sempre. De acordo com os cientistas, se alguém encontrar uma maneira realmente rápida e eficaz de resolvê-lo, será capaz de se beneficiar muito mais de um milhão de dólares do Clay Institute of Mathematics. "Se você escrever um programa que possa resolver o problema rapidamente, poderá adaptá-lo para resolver muitas tarefas importantes que enfrentamos todos os dias", diz o professor de ciência da computação Ian Gent, um dos autores do trabalho científico. "Entre eles estão problemas triviais, como encontrar o maior grupo de amigos no Facebook que não se conhecem, ou tarefas muito importantes, por exemplo, quebrar códigos que garantem a segurança de todas as nossas transações online".
Mas essas são invenções puramente teóricas. Na prática, ninguém ainda abordou a solução do problema de N rainhas de maneira rápida e eficaz. Para a prova de que existe uma maneira mais eficaz de resolver o problema do que uma simples enumeração de todas as opções, elas renderão um milhão de dólares.
Um artigo científico foi
publicado em agosto de 2017 na revista
Journal of Artificial Intelligence Research (doi: 10.1613 / jair.5512,
pdf ).
PS Duas soluções para o problema com o KDPV:
