O Campo Minado ficou conhecido como o joguinho que vinha de brinde no computador, mas também já foi tema em pesquisas de matemática e de computação. A palavra-chave é ”NP-completo“.
O Campo Minado é NP-completo
Por volta do ano 2000, o matemático Richard Kaye mostrou, segundo se conta, que o problema a seguir, ligado ao Campo Minado, faz parte da família dos problemas difíceis chamados “NP-completos”.
Dado um tabuleiro com números, existe pelo menos uma forma de posicionar as minas que não contradiga esses números?
A pergunta “esta casa é segura?”, que fazemos quando jogamos, também tem muito a ver com esse problema.
O que é NP-completo
Dito de forma simples, NP-completo é um problema com estas características:
- Conferir se uma resposta está certa é fácil: se alguém lhe mostra uma disposição de minas, você verifica logo se ela bate com todos os números.
- Encontrar a resposta é trabalhoso (acredita-se): quando o tabuleiro cresce, o número de disposições possíveis explode. Entre os métodos conhecidos, nenhum consegue achar rapidamente a resposta para qualquer tabuleiro.
Além disso, sabe-se que os problemas NP-completos podem ser traduzidos uns nos outros. Se alguém achar um método rápido para um só deles, em qualquer caso, todos os outros NP-completos também ficariam rápidos de resolver. Saber se existe esse método rápido é o famoso problema em aberto chamado “conjectura P≠NP”, um dos problemas que têm um prêmio de 1 milhão de dólares.
O número de disposições cresce depressa
Investigar as disposições é trabalhoso porque o número de candidatas fica enorme.
- Colocar 8 minas em um tabuleiro 9×7 equivale a escolher 8 casas entre 63, o que dá cerca de 3,9 bilhões de maneiras.
- Colocar 75 minas em um tabuleiro 26×15 equivale a escolher 75 casas entre 390, um número com mais de 80 algarismos.
É claro que, ao jogar de verdade, você não precisa examinar tudo. As casas que não encostam em nenhum número podem ser tratadas em bloco, e em muitas situações basta olhar um ou dois números. Ainda assim, quando os números se entrelaçam de forma complicada, chegar a uma resposta segura pode dar trabalho.
O app escolhe só tabuleiros que uma pessoa resolve com raciocínio
Ao gerar um tabuleiro, o app Campo Minado confere se ele pode ser resolvido do começo ao fim usando apenas estas 3 regras que as pessoas usam:
- O que se deduz de um único número
- O que se deduz combinando dois números
- O que se deduz do número de minas restantes no tabuleiro inteiro
Todas essas regras olham uma região pequena e são rápidas de conferir. Se um tabuleiro não pode ser resolvido com essas 3, as minas são movidas e o tabuleiro é refeito. Por isso, quem joga sempre consegue ir até o fim sem precisar de um raciocínio pesado, que examine todas as disposições.
Os tabuleiros para jogar dentro do artigo deste site são feitos com a mesma ideia. Medindo no computador o tempo para gerar um tabuleiro do tamanho do ★5, foram em média alguns milissegundos por tabuleiro.
Quebra-cabeças e matemática
Muitos outros quebra-cabeças de lápis e papel, como o Sudoku, também são conhecidos por ser NP-completos na forma geral, com tabuleiros cada vez maiores. Muitos quebra-cabeças que as pessoas gostam de resolver são feitos de modo que dê para chegar à solução por raciocínio, sem examinar tudo. Os tabuleiros sem chute do app Campo Minado são um desses casos.
O cálculo de probabilidades está em Probabilidades no Campo Minado.
