How to solve Demina
Did You enjoy Demina and want to know more about how can it help You solving the game ? Then continue to read as this will clarify the techniques it uses.
Terminology
First a little bit of terminology, tiles still to be discovered are called unstable to underline the fact that their content will change (when they'll be clicked or flagged), then there are flags and stable tiles i.e. the tiles whose content will not change as they are already clicked.
Obvious approach
The Obvious technique oh, well, it's pretty obvious as it proceeds as a human being would proceed. It considers each stable tile in turn and all the tiles around it; if all the tiles around are flags and other stable tiles then there is nothing to do, but if there is still an unstable tile around it then it sums up flags and still covered (unstable) tiles. If the expected number of bombs is equal to the flags' number then it's possible to click all unstable tiles around as there should be no more bombs around. If, instead, the expected number of bombs is equal to the sum of flags and unstable tiles then all unstable tiles around are bombs and can be flagged. And that's all. Simple, isn't it ?
More terminology
The default technique is more complex as it requires a brute-force (namely try all possibilities) approach. First of all the algorithm identifies subsets of the stable tiles and of the unstable ones. It calls contour tiles the unstable tiles who have at least a stable tile around and checkable tiles the stable tiles who have at least a contour tile around. For example in the following image contour tiles are still covered tiles highlighted in yellow, while checkable tiles are every stable tile next to a contour tile.
Contour and checkable tiles are grouped together to form isles. In an isle all tiles are reachable starting from any of them, the only rule is that from a contour tile only checkable tiles can be visited and from a checkable tile only contour tiles can be visited. Isles are important 'cause they are independent from each other (i.e. they don't influence each other) so they can be solved independently. In the following image for example there are a 1-tile yellow isle, a 5-tile aqua isle and so on (note however that only the contour part of the isles is highlighted, but the checkable part is essential too), but the important thing is that no matter how a bomb is placed on a contour of an isle, it cannot influence other isles' checkable tiles.
Brute-force approach
When every isle has been recognized it's possible to try to solve each of them. Solving involves deciding if contour tiles hide a bomb or not. This is a binary condition bomb/empty, 0/1 so a contour with n tiles can be viewed as a n-bits integer where for every bit the condition can be interpreted as 0 == free of bombs, 1 == it hides a bomb. So to try every possible configuration is sufficient to start with value 0 for the n-bits integer (i.e. all bits set to 0) and increment it by one unit until the value with n bits set to 1 is reached.
Obviously when a candidate configuration has been prepared it must be checked to verify if it's acceptable/admissible or not. This is where checkable tiles come into play. For example in the previous image we can easily recognize an invalid configuration because for example the corner '1' tile at the right-bottom of the image isn't satisfied as its only contour neighbour holds a 0 (no bomb).
When an admissible configuration is found we must increase the number of admissible configurations found so far and the number of times a contour tile has been a bomb for every tile set to 1.
Weird things ... i.e. Huston we have problems !
At the end of the exploration phase, when all the possible configurations have been generated and checked it's time to go back to counters accumulated so far and to decide ! First of all if the number of admissible configurations (which we will call NAC from here onwards) found is 0 then we can say that either the starting configuration is not valid or a bug is lurking somewhere :-).
Normal course of things
If nothing strange happens and at least an admissible config has been found then it's really possible to produce suggestions ... yesss ! All contour tiles with a zero bomb count are then a safe place to jump on ... ehm ... to click on ! while all tiles with a bomb count equal to the NAC are a place waiting for a flag.
Need more information i.e. fuzzy outcome
Ok, ok am I just a little bit too optimistic ? Well there are situations where safe places and flags are nothing but far mirages; in such situations we cannot produce sound suggestions but only elaborate probabilities so for every contour tile Ci the probability to be bomb is pi=bomb_counti/NAC.
That's all. Goodbye.
But 'wait a minute' I hear some of You screaming, 'brute force approaches' are lengthy and time-consuming so how can be Demine so fast ?'. The most important thing is to break down the problem into isles (divide et impera) but this obviously isn't sufficient as even pieces can sometime require a lot of work to be completely explored. The very truth is that even using another 'dirty trick' there are configuration for which Demine takes a big amount of time. They have a little probability to appear in a 'normal' game session, but can be easily prepared by hand for example. In general in such situations using first of all the obvious approach and then brute-force helps, be however prepared to wait for a while in some situations.
The (not so) dirty trick.
Luckily the characteristics and the very nature of the game allow us to shorten the road to suggestions quite a bit sometimes. We saw earlier that to explore all the possible configurations we can add 1 to the binary representation of the contour tiles, i.e. we increment the least-significant bit of the representation. All configurations are then checked against the isle' set of checkable tiles. Every checkable must be satisfied for the configuration to be accepted. And precisely here is the key that let us 'visit implicitly' some configurations without having to actually/really generate them.
Consider in fact a situation where a checkable tile isn't satisfied by a configuration: the associated neighbour contour tiles holds wrong numbers/bits. If the associated bits are high in the bit representation of the configuration then it can take some time (remember we add only 1 each time to consider next config) before such bits will be changed, but we know every configuration generated before such bits will be changed will be surely rejected as the above checkable cannot be satisfied ! Eureka, now we can see the light at the end of the tunnel !
The right thing to do in such a situation is to consider the lowest associated bit of all dissatisfied/unhappy checkable tiles, then select among them the higher and increment the configuration's representation at that level. Obviously, as said, high and low have a meaning with respect to the binary configuration. Also all bits lower the intervention point can be zeroed to avoid missing possible admissible configs.
Surprised ? Just You don't believe what I am saying ? Do You think I am joking just to detect who fell asleep in the meanwhile ? Well this is how Demine works so this approach must deserve some attention from Your part.
Ah, now I understand it's just my explanation that sounds like an obscure voodoo spell ! :-). Well as You probably have already guessed I'm not good at explaining things, even less so, if possible, in a foreign language so, please be patient with me.
The goal is to change the configuration representation at the highest possible level without missing admissible configurations. In the equation the 'not missing good configs' part is guaranteed by the fact we select the lowest associated bit of checkable tiles as the key bit and then we set to zero every bit lower the intervention point, while the 'highest possible level' part is guaranteed by the selection of the higher among the key bits.
This can seem not to be a great improvement, but as an example let's consider an isle with 27 contour tiles as the following.
The total number of different configurations that is possible to generate whit 27 binary digits is 2^27 = 134.217.728. The program explores all the configurations to find that the good ones are only 2 !!! The smarter version explores only 1498 configs and it finds the same 2 good configs i.e. the dumb brute-force approach visits about 89598 more times the configs visited by the smarter algo to find the same 2 good configs. Well, needless to say this is really a great improvement.
Final Phase
In general when there is still a great number of bombs the above is all the program can do to guess bombs' positions, but when the number of bombs still to be located become little enough some more techniques can be used. As we saw earlier the bombs's number of the good configs for an isle can vary from a min M to a max N. We don't know how many bombs an isle really uses, but we know for sure that it uses at least M bombs. So if the sum of the min number M of bombs used by each isle is equal to the number of bombs still to be discovered we know for sure that all the remaining bombs are on contour tiles. Now the next step is easy: if there are uncovered tiles that aren't part of the contour of some isle we can click them all as they are safe 'cause all the bombs are forced to stay on contour tiles.
But, as TPReal suggested, there is also more that we can do when there are few bombs around. Isles are usually independent and can be solved independently. But if the number of bombs still to be discovered is little enough they starts influencing each other in rather a surprising way i.e. in the final phase of the game the isles aren't so independent after all.
Suppose, for example that the Solve phase found 2 isles, one with good configs all using exactly 4 bombs and the other using from 3 to 5 bombs; suppose then
that there are still 7 bombs around. It's now clear that all the configurations with 4 and 5 bombs of the 2nd isle must be rejected or the total number of bombs still around should be 8 or 9
respectively. Generalizing such technique Demine tries all possible combinations of bombs and rejects the combinations that requires more bombs than available.
Let 8 be the number of bombs still around, then suppose isle A has configs with 2 bombs, isle B has configs with 2, 3 or 4 bombs and isle C configs with 3 or 4 bombs; Demine
considers the following combinations:
A B C Sum
2 2
3 7 OK this combination is accepted
2
2 4 8 OK
2 3
3 8 OK
2 3 4 9
KO this combination is rejected
2 4
3 9 KO
2 4 4 10 KO
From the above example is clear that all configs with 2 bombs of isle A are accepted, then all configs with 2 or 3 bombs of isle B are accepted, too and then all configs with 3 and 4 bombs of isle C are accepted, too. Configs with 4 bombs of isle B, however, are rejected 'cause they aren't used by any accepted combination. This added bit of information is sometimes enough to discover the position of a bomb or a safe tile.
And that's really all Demine does just to help You !
Links to code
The program uses a worker thread to avoid to block interface updates.
In the code TTilehandler and TIslehandler are responsible to handle the isle concept; TTileHandler creates TIsleHandler(s) but they can auto-break themselves into more pieces too as required.
TTileHandler is also the implementation of the IDemineProblem interface and as such can be required to provide the problem size (at the beginning) and then to verify/check the admissibility of the configurations provided by the algorithms by mean of the IAlgorithmResult interface asking the checkable tiles.
A (possible) result for the problem as modeled by the IAlgorithmResult interface must be able to say if contour tile i is a bomb or not.
TConfiguration is the implementation of the IAlgorithmResult interface and is nothing else that the bit representation of the configuration that can be mapped on the isle's contour tiles set.
TProbKeeper is responsible for keeping configs number, good configs number and bomb number for every contour tile in the isle.
A std::vector<TConfiguration> also holds good cfgs (if required to remember) for the solving algorithm.
TAlgorithmImpl<> is the body of the brute-force solver; it's a template class accepting templates parameters (or policies). The most important policy is the 1st one: using TAllCfgExplorer as the first policy force the solver to explore all possible configurations, while the class TSuggestedCfgExplorer force the solver to exploit the dirty trick explained above. Other parameters of the solver decide the way the algorithm can produce feedback for the user, the configuration representation, the probability keeper and a controller that decides when to communicate (if needed) the explored/good cfgs numbers. It's used by TMoreCorrectJob to solve all isles.
Gianni Luciani