Difficulty of solving a given board size

Want to calculate something or share your results?

Difficulty of solving a given board size

Postby qqwref » Sun Sep 04, 2011 2:07 am

Lately I was thinking about how to tell how difficult a given size of board is to complete. There are a lot of different custom boards available but nobody seems to really know how hard they are, except that larger boards are slightly harder and denser boards are much harder. I recently had the idea of checking how many guess patterns an average board of a given size had; that seems to be a decent indication of how much guessing you can expect to do to complete the board. (Of course, to get better numbers, you would want to have your program actually try to solve the boards and tell you how often it succeeds - although I don't know how to program this.)

So anyway, I ran 10k or 100k boards for all of these, and searched for three types of guess patterns: the standard 50-50 pattern, the 50-50 square, and two 50-50s in a line (with unknown squares in the form XX XX). Here are the numbers I got for the various boards:

Code: Select all
name                             h   w   m    difficulty
Beginner (new minesweeper)       9   9   10   0.05
Beginner (official)              8   8   10   0.10
Intermediate                     16  16  40   0.19
Expert (beta minesweeper)        24  24  99   0.41
Huge (narkomania)                30  40  200  0.52
Expert                           16  30  99   0.78
Expert Plus (minesweepers.org)   24  30  149  0.93
Alptraum (minesweeper league)    24  36  180  1.09
Challenge (narkomania)           24  40  200  1.16
Wahnsinn (minesweeper league)    30  40  250  1.28
Int-density size WR              100 110 1719 1.35
Expert-density size WR           100 100 2063 4.41
24x30 density WR                 24  30  225  4.96
16x16 density WR                 16  16  95   5.07
16x30 density WR                 16  30  160  5.13
9x9 density WR                   9   9   42   7.92
8x8 density WR (old)             8   8   37   9.47
8x8 density WR (new)             8   8   49   17.94
NF player. Best scores 1-10-39.
qqwref
 
Posts: 121
Joined: Thu Sep 23, 2010 4:17 pm

Re: Difficulty of solving a given board size

Postby computronium » Fri Feb 01, 2013 3:40 am

See, if you wait long enough, someone will eventually respond :)

I've been thinking about this sort of thing lately, in hand with my efforts to find the optimal solving algorithm. Very likely it would be possible to mathematically determine the likelihood of some or all of these scenarios for a given board size and mine density, which would give you an upper limit on the completion percentage possible for any algorithm. E.g. if a 50-50 guess comes up in 20% boards, then the best an algorithm could hope to achieve would be a 90% completion rate.

Granted there are enough other situations where guessing is required, that would be considerably harder to compute the odds of occurring. The best solving algorithm we could find would likely have a completion rate far lower than the maximum bound we could compute. But I still think it would be of mathematical interest.

Also, it's theoretically possible to improve the odds of solving a board that has a 50-50 square (are there official names for these things?), by, say, having your initial guess be along the edge, where they seem to be more likely to occur. (If your initial guess is inside one, it may be more likely to solve it without guessing. Maybe not though.)

Can I ask, if you can remember or still have the code, what specifically did you search for? I.e. what constitutes a 50-50 square?
computronium
 
Posts: 23
Joined: Thu Oct 11, 2012 8:32 am
Location: Melbourne, Australia


Return to Math & Theory

Who is online

Users browsing this forum: No registered users and 1 guest

cron