MineSweeper March Contest

Guys I have been patiently awaiting an editorial for the MineSweeper.I wanted to know the correct approach so that I can implement it on my own for the practise question.I have submitted an answer and it was accepted and my score was 0.514(dont remember the exact value after 0.5) anyways… the approach I followed was I was greedily choosing the cells which had the maximum value of (Number of Adjacent neighbours + itself).When I have found a cell containing a mine then I would assign that corresponding cell a value of 0 and reduce all adjacent neighbour’s value by 1.if somehow anyadjacent neighbour again reduce to 0,I recursively called dfs on it to make all its neighbours 0 again.Also,when I get an int value for a mine,if its 0 den I make the corresponding cell and all its neighbours 0,otherwise I only made that cell 0 if e.g I got 2 when I am surveying a cell.

and then again after it I am greedily choosing the cell with the maximum value.

How can I improve it?I mean how to optimize it further?

2 Likes

One very simple thing that you could try is the following: When you have a cell with P mines around it and you have exactly P cells around it which are unknown to you, then you can automatically infer that all those P cells are mines (without surveying them), so then you can neutralize them immediately.

4 Likes

Both author’s and tester’s solution are not very smart:
due to a lack of time we both coded only quite simple solutions.
So unlikely you will find something interesting in the editorial.
But if top contestants describe their approaches it should help a lot.

4 Likes

ya good one!

@deepai_dutta : The approach to optimization that @mugurelionut told is obviously correct and should be implemented . Another optimization is this :
Consider the pattern :
222 (line ends)
UUU (line ends)
122 (line ends)
222 (line ends)
Now 1 is adjacent to two unknown squares and 2 is adjacent to three unknown squares . The three unknown’s of 2 share two unknown points with 1 out of which at max 1 can be mine , so the remaining third is also mine .
So whenever you have two numbers which share their unknown neighbours you can look for additional deterministicness .
In particular if ,
neigh(x) - neigh(y) == number(x)-number(y) ,
then all unknowns in neigh(x)-neigh(y) are mine .
Here ,
neigh(x) : denotes set of unknown neighbours of x.
number(x) : number of still unearthed mines adjacent to x .
The ‘-’ is usual set subtraction . Note neigh(y) need not be a subset of neigh(x) for subtraction to be defined .

I implemented a more general approach in my solution. For each square of size 6 x 6 (starting at lines and columns multiples of 3) with sufficiently few unknown cells, I ran a backtracking, to try to set each unknown cell to having a mine or not (that would be 2 at the power of unknown cells, but with sufficiently many optimizations). If a cell could only be a mine or an empty cell in all the solutions I found, then I would immediately infer its type. I would run this backtracking only on squares which contained a cell whose type was changed since the last time I ran the backtracking on it.

1 Like

I got 0.74 for my submission… http://www.codechef.com/viewplaintext/1932681

I basically thought of first surveying positions (0,0), (0,2), (0,4)… (2,0), (2,2), (2,4)… in similar pattern till the end… During the process if any mine is found then I will diffuse it and resurvey it… if during this the result is 0 then I will make the surrounding unavailable or if K with K active position, then I diffuse them all, the result of the survey done is then stored in a probability graph along with the survey book(storing activeness of the position)… from which I can calculate the most probable next position of occurrence of the bomb… then I will survey that position… and if the bomb is found then I will diffuse… otherwise continue with the process…

One can make this more optimized by using the result obtained by surveying the most probable points…

4 Likes

Another very simple thing you can do is

if the number of unknown cells is lower than actual K, use neutralize operation for all those cells and print “Done”

(of course you decrement K if you use neutralize operation)

1 Like

I implemented solution that neutralized always 2 first “unknown” rows, there are only those 2 base cases:

? <-
?

and

d <-
?

where <- is actually processed row, ? is unknown cell (I didn’t performed survey operation) and d is found number of mines returned from previous Survey operation (d is in [0…8])…

It holds that for actual position (ar, ac) I know I already neutralized rows 0-(ar-1) and in actual row I neutralized columns 0-(ac-1).

From this property I know that there are 2 special cases:

For first case there is

2 ? <-
d ?

and I know that both ?s are mines

For second case there is special case

 1 d1
d2 ?

Again I know that ? is mine.

If none of those is true I perform Survey operation for actual cell

  • if there is mine I neutralize it and decrease d for surrounding cells with d value in [0-8]
  • if I got number of surrounding bombs I performed operation described by mugurelionut

That’s it and I scored 0.698 points. Code is here.

What’s the score of those simple solutions ? Just curious, my first I/O test solution got 0.333 - it’s simple: for each cell perform Survey operation and if there is bomb, defuse it…

I got 0.923pts with this simple one (it could be improved A LOT).

Basicly, the main steps are :

  • Find the smallest prime P which is prime with N
  • M is the number of remaining mines
  • K is the number of remaining dynamites
  • U is the number of remaining unknown cells
  • then compute…

Until M == 0 or K >= U :

  • Survey the cell C (0 at the beginning)
  • Solve recursively if possible :
  1. If it’s a mine : neutralize it and decrease numbers around
  2. If it’s a 0 : mark cells around as ‘safe’
  3. If it’s a number between 1 and 8 and this number == unknown cells around, neutralize them
  4. And so on …
  • C += P

When we are out of the loop :

  • if M == 0, it’s finished
  • else if K >= U, then neutralize ALL remaining cells ! (we don’t care if there are mines or not)

At first, i tried several approaches : sequential discovery, random discovery, both mixed, etc.

But the best result i got was with this kind of “linear modulo grid”. :slight_smile:

I had no time to check if the “standard grid” one was better or not.

The main pitfall is that marking cells as ‘safe’ could prevent the program to retrieve further information about the remaining mines. We also could survey the neutralized mine cells (but surveying cost points…). I think that the best idea to survey a cell would be to survey it only if it is surrounded by ONLY unknown cells (until it’s not possible, of course) : in order to maximize the quantity of information brought by the surveying itself.

I actually coded a graphical interface above that, in Python, to “see” what happens on generated test cases.

For those who are intersted in seeing my progression through ideas : come here.

6 Likes

Well, I have used Constraint Satisfaction machinery to find where mines have to be, if it happens that the situation is ambigious I did more surveys. If I had enough information I performed neutralize operation. It worked pretty well, but I didnt manage to exploit for instance extra neutralize operations, and many more so I ended up with small amount of points :slight_smile:

I’ve got 0.967:

My approach started with surveying independent fields, (in blocks of 9x9) i.e.:

  • *************
  • *1**4**2**3**
  • *************
  • *******xxx***
  • *M*1**Mx0x*2*
  • *******xxx***
survey(field)
  case bomb: neutralize it
  case 0: set all surrounding fields to done
  case default: add field in a priorityQueue (Sorted on most surrounding mines first)

Now we can exploit the fact that we can neutralize more than there are mines: let Extra be (N - K)

while( Extra + pq.peek().mines >= 8)
   todo -= pq.peek().mines
   neutralize all neighborcells
   Extra -= 8;
   Extra += pq.poll().mines

The reason that all blocks are independent is that I don’t want to resurvey any of the already surveyed fields.
After that I just checked each field with some rules:

  • check if one of the neighborcells needs a bomb (so all its free nbs Equals the amount of bombs needed): neutralize (as Lionut already stated)
  • if all neighborcells are done: set to done and ignore
  • if Todo = 0, end

Also tried some small optimizations for going from 0.955 to 0.967, u can check my submissions if interested

3 Likes

the priorityQueue trick is great ! :slight_smile: very good idea.

2 Likes

i also have done the same

//