wood burning stoves 2.0*
The moose likes Programming Diversions and the fly likes Minesweeper algorithm Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Minesweeper algorithm" Watch "Minesweeper algorithm" New topic
Author

Minesweeper algorithm

Duran Harris
Ranch Hand

Joined: Nov 09, 2008
Posts: 598

Hi...

This may not be a puzzle in you eyes,but I'm no math guru.So the situation is that I designed a minesweeper game(in Javascript)..Now as you know when a tile is clicked that has no mines surrounding it,the program will continue to evaluate and reveal surrounding tiles in all directions resulting in a polygon with a perimeter defined by tiles that are touching mines(possibly with isolated mines forming islands).
I had a version working which had logic along the following lines:

If a tile is clicked,it's coordinates are passed to the recursive(reveal) function.The function checks all 8 surrounding tiles and passes each tile that has no surrounding mines back to the recursive(well not really recursive,but it does call itself :p)And so in turn each surrounding tile will be checked in this manner.
Problem is though,when I made the game I didn't realise that Javascript was object-oriented!So when I discovered this,I decided to re-write the minesweeper game...but now it's days later and I can't seem to get my reveal function to work....I always get a too much recursion error.

So I have 2 options(one of which might not be valid):

1-Make the recursive method reveal an inner function(because apparently in javascript,a recursive inner function is not repeatedly(compiled?) with each invocation...hence,possibly allowing my method to run to completion.
OR
2-Could someone please give me a functional algorithm to do so?I've googled it,but I only came across a Java game that had very heavy syntax(ternary operators everywhere!)and minesweeper solving algorithms.

Arg,maybe I should make chess instead


===>SCJP 1.5(72%)<===
==>SCWCD1.5(76%)<===
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 42285
    
  64
I always get a too much recursion error.

That sounds like the condition for ending the recursion isn't being triggered (or the condition isn't correct). For each tile you should only recurse for adjacent tiles that have not been checked yet after the last click. So you need to keep track of which tiles have been checked already, regardless of whether the result was to reveal them or not.


Ping & DNS - my free Android networking tools app
Duran Harris
Ranch Hand

Joined: Nov 09, 2008
Posts: 598

Yes,there is no base case to stop the recursion..I can't think of the criteria that need to be meet for recursion to stop.I tried to do what you say but then the result that I get is that only the 8 surrounding tiles get revealed....ie.they have all been marked as checked resulting in them not being checked again.
The revealed tiles sort of form a barrier:
TTTT
000T
0x0T
000T
TTTT

In this case no further tiles can/will be checked .... Another solution that I investigated was performing a check on 8 compass directions...resulting in a star shape,but the further away that the revealing stops the bigger the gaps of unchecked tiles that occur ie:
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 42285
    
  64
Each recursive call should in turn check its 8 surrounding tiles. Of those, either 3 (for a NW/NE/SW/SE tile) or just 1 (for a W/N/S/E tile) should trigger further recursions - assuming those tiles are still covered, and that they haven't been marked checked by previous calls.
vaibhav mishra
Ranch Hand

Joined: Jun 18, 2008
Posts: 168
I had developed same program using recursive algorithm
the sources can be found at project page


SCJP
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Minesweeper algorithm