PROBLEM LINKS
DIFFICULTY
CHALLENGE
PREREQUISITES
Ad Hoc
PROBLEM
Hurray to Codechef hosting its first Interactive Challenge!
The classic game of Mine Sweeper is presented with a twist. On a grid of size N by N, there are several mines. You are given K dynamites. You can perform two types of opeartations
- Survey(x,y) = returns whether (x,y) is a mine or not. If (x,y) is not a mine, then you come to know how many of the 8 adjacent cells are mines.
- Neutralize(x,y) = uses one dynamite on cell (x,y). If (x,y) was a mine, then it no longer will. Otherwise, nothing happens (but a dynamite gets used anyway).
Design an algorithm to neutralize all the mines using the least number of Survey operations used.
QUICK EXPLANATION
Interactive Judges bring a vital capability to effective Challenge Problems. The ability to randomize test cases on the fly. Without this all challenge problems were susceptible to hacks by the solvers, aimed at guessing the test cases. Once that happens, optimal scores on the test data are not far away.
Thus, the interactive judge randomizes the input available to the program across multiple runs. The same program, that doesn’t rely upon randomization, may score differently on different runs! This leads to a harder challenge for the participant than conventional static test cases.
That said, compared to typical Challenge problems, Minesweeper was easier. All easier means here is you could get an AC with a simple program, without worrying about score. Of course, it is never easy to score among the top brass in any Challenge Problem.
EXPLANATION
You can get an AC easily by doing the following two things.
- Survey each of the cells to find the mines.
- Neutralize all the mines you have found.
But this submission ensures that you at the lower end of the rankings. How can you do better? There is much information to be used in the return of a Survey operation.
Let us look at some possible optimizations. The best submissions of course have multiple of these optimizations and more.
Maintian a map of known cells
We should always (obviously) maintain the state of known cells. Using all our previous Survey operations are also critical. For each cell, it is good to know
- The number of safe cells in the neighbourhood
- The number of mines in the neighbourhood
Maintain the number of mines found
It is good to know that we can mark the remaining cells as mines, whenever we can.
This also serves as a Last Resort, since when the number of dynamites are equal to number of mines, we can resort to survey wasteful techniques that guarantee correctness.
You may re-survey a neutralized cell
This can sometimes be very useful. Spending a Survey operation to find a mine is waste of precious score. It is better to let your heuristics find mines. Now, cells that have been neutralized are surely useful because you know a survey operation is never wasted on them.
Partition the board by mine densities
We can partition the board into 3x3 mini-boards and consider each one of their centers. If the mine density is low in a cell, we should preserve our survey operations for those cells. The denser ones will eat up more survey operations.
Heuristics for finding mines
In the sparse parts of the board you may survey half the cells (every alternate cell). This can then be fed into a BFS that tests whether a cell can be a mine or not.
We can start from a corner of the sparse area and test whether a cell is not a mine, since this will force other cells to be mines indeed. Once you reach a contradiction (that the cell that should be a mine is known to be safe), we know that our original cell was a mine indeed.
For example, consider a board explored as below
..... ..*.. ....* .*... ...*.
We do not know mines before hand, but still survey the following cells (marked with hash)
.#.#. #.#.# .#.#* #*#.# .#.#.
We end up spending 12 survey operations and finding 2 mines. We neutralize them and re survey the cells, a total of 14 survey operations to get the following table
.0.0. 0.0.1 .1.1. 1.1.1 .1.0.
We can find the remaining mine from this table.
Use extra neutralize oppotunities
On denser parts of the board, we can waste extra opportunities to neutralize by calling it without a survey. This ensures that the subsequent survey is always safe. This way, we get more information about denser parts in fewer surveys.
There is already a great thread active where participants are discussing their approaches. You can visit that thread to gather more ideas 
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.