Ir ao conteúdo
  • Cadastre-se
apollosky1

C Desenvolvimento de algorítimo para resolução de um Campo Minado

Recommended Posts

Foi comprovado que resolver o jogo campo minado é um problema NP-completo:

http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

 

Logo, não há um algoritmo que resolva todos os campos minados, e em algum ponto pode não ter nenhuma jogada certa, e ser forçado a fazer um chute, o qual poderia ser determinado probabilisticamente para minimizar a chance de erro.

 

 

 

Na internet pode achar algumas ideias de algoritmo para resolver até onde der:

https://stackoverflow.com/questions/1738128/minesweeper-solving-algorithm

 

Achei interessante essa usando sistemas lineares binários:

https://massaioli.wordpress.com/2013/01/12/solving-minesweeper-with-matricies/

 

Mas não é uma solução perfeita, alguém até aponta nos comentários um possível caso em que o método não identificaria que um quadrado não tem mina mas seria possível identificar, então o método pode ser melhorado para obter melhores resultados.

 

 

E aqui outro tópico do fórum com implementações do jogo:

 

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×