Densidade: o número que define a dificuldade
A densidade é a fração das casas que têm mina. Ela pesa mais na dificuldade do que o tamanho do tabuleiro.
| Nível | Casas | Minas | Densidade | Densidade fora da área do 1º clique |
|---|---|---|---|---|
| Fácil | 81 | 10 | 12,3% | 13,9% |
| Médio | 256 | 40 | 15,6% | 16,2% |
| Difícil | 480 | 99 | 20,6% | 21,0% |
A última coluna considera que, neste site, as minas são sorteadas fora das nove casas em volta do primeiro clique. Com mais minas por casa, os números ficam maiores, as áreas vazias ficam menores e as deduções ficam mais longas.
Quantos tabuleiros diferentes existem?
O número de jeitos de espalhar as minas é uma combinação simples: escolher em quais casas elas ficam.
- Fácil: 10 minas em 81 casas dão cerca de 1,88 trilhão de tabuleiros diferentes.
- Médio: 40 minas em 256 casas dão cerca de 1,05 × 1047 tabuleiros, um número com 48 dígitos.
- Difícil: 99 minas em 480 casas dão cerca de 5,6 × 10104 tabuleiros, um número com 105 dígitos.
Para comparar: estima-se que o universo observável tenha algo em torno de 1080 átomos. Você nunca vai jogar o mesmo tabuleiro Difícil duas vezes por acaso.
A chance de uma casa ter mina
A pergunta “qual a chance desta casa ter mina?” tem uma resposta exata: contar todas as distribuições de minas compatíveis com os números visíveis e ver em quantas delas aquela casa tem mina. Na prática, usamos duas aproximações.
Casas longe da fronteira
Para uma casa que não encosta em nenhum número, a chance fica perto de: minas que faltam, divididas por casas fechadas que faltam. Com 20 minas restantes em 100 casas fechadas, algo perto de 20%.
Casas na fronteira
Para uma casa vizinha de números, as restrições mudam a conta. Um 1 que enxerga duas casas fechadas, sem outra informação, deixa cada uma perto de meio a meio. Um 1 que enxerga quatro casas dá cerca de 25% para cada uma, se nada mais interferir. Quando vários números se cruzam, a única forma exata é enumerar as possibilidades, que é o que programas de análise fazem.
O 50/50
Quando duas casas são vistas exatamente pelos mesmos números e uma delas tem mina, nenhuma informação disponível favorece um lado. A chance é exatamente metade para cada. Veja o desenho em Padrões.
Por que às vezes é preciso chutar
As minas são sorteadas sem olhar se o tabuleiro tem solução lógica. Quanto maior a densidade, mais comum é aparecer uma configuração em que os números não bastam para decidir. Por isso, no Difícil comum, até jogadores de elite perdem partidas por azar.
No modo Sem chute deste site, o jogo sorteia o tabuleiro e, antes de entregar, roda um solucionador que tenta limpar tudo a partir do seu primeiro clique usando só três tipos de dedução:
- as regras do número completo e do número satisfeito;
- a comparação entre pares de números que enxergam casas em comum, que cobre o 1-1, o 1-2, o 1-2-1 e o 1-2-2-1;
- a contagem total de minas restantes.
Se o solucionador trava, o tabuleiro é descartado e outro é sorteado. No Difícil, isso costuma levar alguns milésimos de segundo. Como o solucionador usa só deduções que uma pessoa também consegue fazer, todo tabuleiro sem chute tem uma solução que você pode encontrar.
Campo Minado é NP-completo
Em 2000, a revista The Mathematical Intelligencer publicou o artigo “Minesweeper is NP-complete”, de Kaye, da Universidade de Birmingham. Ele prova que o seguinte problema é NP-completo: dado um tabuleiro parcialmente aberto, decidir se existe alguma distribuição de minas compatível com todos os números.
Na prática, isso quer dizer que ninguém conhece um método que resolva esse problema rapidamente para qualquer tabuleiro, por maior que ele seja. Se alguém encontrasse um método rápido para ele, encontraria também para milhares de outros problemas difíceis, como agendar tarefas ou montar rotas de entrega, e resolveria a questão “P versus NP”, um dos Problemas do Milênio do Instituto Clay, com prêmio de um milhão de dólares.
Isso não significa que cada partida seja impossível. Os tabuleiros do jogo são pequenos e quase sempre resolvidos com deduções locais. A dificuldade aparece quando o tabuleiro cresce sem limite.
Outros resultados curiosos
- Em 2011, Allan Scott, Ulrike Stege e Iris van Rooij argumentaram que decidir se existe uma casa que pode ser aberta com segurança é um problema co-NP-completo. Em 2024, pesquisadores do MIT apontaram uma falha nessa demonstração e publicaram uma prova corrigida. A matemática do jogo ainda está sendo escrita.
- O mesmo autor do artigo de 2000 também mostrou que uma versão infinita do Campo Minado é Turing-completa: com uma grade infinita, dá para montar configurações que simulam um computador.
Fontes
- Kaye, “Minesweeper is NP-complete”, The Mathematical Intelligencer, v. 22, p. 9–15, 2000.
- Allan Scott, Ulrike Stege e Iris van Rooij, “Minesweeper may not be NP-complete but is hard nonetheless”, The Mathematical Intelligencer, v. 33, p. 5–17, 2011.
- MIT Hardness Group (Della Hendrickson e Andy Tockman), “Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants”, 2024.
- Minesweeper (video game), Wikipédia (em inglês).