DESENVOLVIMENTO DE UM JOGO COM UTILIZACAO DE INTERFACE GRÁFICA

...

Pode até parecer brincadeira, mas o Jogo do Campo Minado de Tabuleiro reúne hoje em dia mundialmente campeonatos convocando jogadores profissionais para disputas internacionais.

Mas como joga? Como são feitos os cálculos? Existe empate? Ao longo desta monografia serão explicadas as regras do jogo, métodos de dedução, cálculos feitos e também as técnicas usadas.

Regras e Funcionamento do Jogo (conceitos gerais) (4-8 paginas) OK

Regras

O jogo contém com o objetivo de encontrar os quadrados vazios e evitar as minas dentro de um tabuleiro, quanto mais rápido o jogador esvaziar o tabuleiro, melhor será a sua pontuação.

Cada quadrado pode ser revelado clicando sobre ele. Se descobrir uma mina, o jogo acaba, senão o jogo continua.

Ao clicarmos sobre o quadrado, uma de ambas as opções poderão acontecer: um número aparece, indicando a quantidade de minas que estão escondidas ao redor do quadrado clicado, se nenhum número aparecer o jogo revela automaticamente os quadrados que se encontram ao redor do quadrado vazio.

O jogo é ganho quando todos os quadrados que não têm minas são revelados.

Opcionalmente, o jogador pode marcar qualquer quadrado em que acredita que contenha uma mina com uma bandeira, bastando para isso, clicar sobre o quadrado do tabuleiro com o botão direito do mouse. Em alguns casos, carregar com ambos os botões do mouse um número que contenha tantas bandeiras, imediatamente à sua volta quanto o valor desse número revela todos os quadrados sem bombas que se encontrem adjacentes a ele. Em contrapartida, o jogo acaba se efetuar essa ação quando os quadrados errados estiverem marcados com as bandeiras.

Algumas versões do Campo Minado de Tabuleiro ajudam o jogador, na medida em que, nunca colocar uma mina no primeiro quadrado do tabuleiro, como acontece na maioria dos programas ou sempre deixar uma abertura no primeiro clique, como ocorre nas versões posteriores do Windows Vista.

Análise do jogo

Padrões de problemas e solução

Durante o andamento do jogo, existem múltiplos padrões de quadrados numerados que permitem somente uma determinada configuração de minas. A fim de propor ao jogador a terminar o jogo o mais cedo quanto possível. É preferível processar tais padrões primeiramente, e continuar analisando padrões mais complexos posteriormente. Existem diversos métodos para resolver problemas do jogo sem contar com o uso de adivinhação.

Análise de um quadrado

Quando o número de quadrados não descobertos ao redor de um quadrado numerado é igual ao número sendo mostrado, todos os quadrados adjacentes são minas. Em contrapartida, quando o número de quadrados com minas descobertas ao redor de um quadrado numerado é igual ao número sendo mostrado, quaisquer outro quadrado adjacente não possui mina, está seguro.

Análise de dois quadrados

Com dois números de um campo minado, denominados x e y, existem três áreas distintas no campo:

a) minas ao redor de tanto x e y

b) minas ao redor de x somente

c) minas ao redor de y somente.

Esse método de análise funciona melhor quando os quadrados relativos a x e y são adjacentes, mas também pode ser usado em outras situações. Sabe-se que o número de minas exclusivas a x menos o número de minas exclusivas a y é igual a x-y, o que pode ser usado para marcar bandeiras em minas ou descobrir quadrados seguros.

Análise de minas compartilhadas

Suponha que o campo possui um número "1" descoberto. De alguma forma descobre-se que dois quadrados adjacentes ao "1" compartilham uma mina. Isso significa que todos os outros quadrados adjacentes ao "1" são seguros, exceto pelos dois que compartilham a mina.

Análise final

Usada no final do jogo, ela pode ser usada para descobrir um quadrado seguro quando todos os outros do campo são ou seguros ou marcados como minas. Geralmente, tais quadrados finais estão localizados nas paredes do campo. Em algumas versões do jogo, a quantidade de minas presentes no campo é conhecida. Perto do final do jogo quase todos os quadrados já foram descobertos, e saber a quantidade de minas restantes (ainda não descobertas) pode ser útil para resolver o padrão final do jogo.

Adivinhação às vezes necessária

O jogador deve adivinhar em qual dos quadrados marcados com o ponto de interrogação está localizada a mina. Outro caso que demonstra a necessidade de adivinhação é aquele onde um quadrado não descoberto é completamente rodeado por minas com número "1", ou quando há uma combinação de minas e o perímetro do campo de jogo. Nesse caso, já que nenhum número rodeia o quadrado não descoberto, o jogador não possui informação sobre o conteúdo do quadrado. Entretanto, há uma estratégia para remediar a situação que evita a adivinhação: continuar jogando e ignorar o quadrado que requer adivinhação.

NP-completude

Em 2000, Kaye publicou a prova de que o jogo é NP-completo para determinar se uma posição no campo minado é consistente com a marcação de minas. Atualmente, o campo minado é mencionado pelo Clay Mathematics Institute na descrição não oficial do problema P versus NP.

Cálculo P Versus NP

O problema "P versus NP" é o principal problema aberto da Ciência da Computação. Possui também enorme relevância em campos que vão desde a Engenharia até a criptografia aplicada aos serviços militares e às transações comerciais e financeiras via Internet.

Definição do problema

De modo simplificado, o problema pergunta se existem problemas matemáticos cuja resposta pode ser verificada em tempo polinomial, que não possam ser resolvidos (diretamente, sem se ter um candidato à solução) em tempo polinomial. Ilustrando: se alguém lhe disser que o número 13.717.421 pode ser escrito como o produto de dois outros inteiros, você provavelmente demorará para provar isso; contudo, se lhe assoprarem que ele é o produto de 3.607 por 3.803,