From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Minesweeper is driving me nuts. Date: 7 Jan 1995 17:47:43 GMT In article <3elan2$8vg@mp.cs.niu.edu>, Dave Rusin wrote: ...nothing useful. (Mailreading from home makes me more prone to screw-ups). Here's what I intended to say: Whenever a new game enters the house, Daddy seems to disappear for a few days until he has analyzed it, run computer simulations, and so on. One time I taught the computer to play a solitaire game -- that is, I didn't play solitaire on the computer, I had the computer doing it. [It was a card game called 10-20-30 and I was interested in studying strategies.] Minesweeper was no exception last year. Claiming to be doing it 'for the kids' I wrote a simulation which would run on our old non-Windows machine. Along the way I tried to teach it how I solved the problem. An undocumented feature of the program allowed me to hit 'X' to automatically do the thinking I do methodically. Each time you make a move, you're solving a set of linear equations: one equation for each number revealed on the board, with one variable for each uncovered cell representing the number of bombs hidden there (0 or 1). What we do when playing is solve this system (partially) in a fast way. I wrote the computer program to carry out the tricks I knew. The program I posted will give you an indication of why I'm not a professional programmer. It's written in -- don't laugh now -- Turbo Pascal III. After I posted it (of course) I kept rummaging around and found a version produced a few days later, which has the eXpert option working correctly. It automatically handles situations like this: 1 1 ? ? ? ? and knows that the two cells in the last column are not bombs. Having already breached netiquette once by posting long code, I won't do it again, but if anyone wants I can send them the source or PC executable for this fancier version of my minesweeper solver. In examining the newer version I see it still fails to solve certain sets of equations; I think it's the ones which would require combining three or more at a time; for example, in 0 1 ? 1 2 ? ? ? ? you know the last cell is safe. I don't intend to pursue this project since the eXpert mode I have already works splendidly in many cases. Also, I have not addressed the question of how best to select the next square to uncover when you must make a guess. dave (always on the lookout for games amenable to mathematical analysis) (Anyone got Chutes and Ladders?) ============================================================================== From: bobs@access.digex.net (Bob Smith) To: rusin@washington.math.niu.edu Subject: Re: Minesweeper is driving me nuts. Date: Sat, 07 Jan 95 21:08:56 GMT ... I'd love to see your program, source and executable. For comparison, see my version in ftp://ftp.digex.net/pub/acess/bobs/mysweep.zip ============================================================================== Date: Sat, 7 Jan 95 23:58:43 CST From: rusin (Dave Rusin) To: bobs@access.digex.net, rusin@washington.math.niu.edu Subject: Re: Minesweeper is driving me nuts. I found your version of minesweeper. It's great! As a mathematician rather than a computer programmer I wasn't trying for anything so impressive in the display. I just got tired of clicking squares when I knew how I would solve the problem in 90% of the cases. I rigged up a PC simulation that would carry out that solution for me upon request. This seems to be more or less equivalent to your incorporation of Clues. So I don't think that, mathematically speaking, the incarnations of the game are different. Your documentation does seem to suggest that you would expect to use brute force enumeration of cases to pin down the remaining hard cases. I would suggest instead treating each exposed number as one side of an equation, the other side being the sum of variables corresponding to the adjacent unexposed cells. You don't want to do a lame diagonalization and solution of the corresponding system of equations since the variables must take on only the values 0 or 1; but this system of equations (together with one more recording the total number of still-hidden mines) does include all information available to the player at each moment, so the general problem of constructing Clues is equivalent to finding solution sets to these equations. I'll send two files with this letter. The first is Pascal source for the simulation I wrote, the second a uuendcoded compile of that source. I'm having some trouble with my file-transfer software from home, so there may be a copy error, but it 'sum -r's OK, so you should be all right. Run it right from DOS; hit H for a short summary of what's available. In addition to uncovering cells and marking them as bombs, I added features not in the Windows version -- each additional feature an attempt to codify another thing I do by hand in Windows: expose all remaining adjacent cells when neighboring mines are all accounted for mark all remaining adjacent cells as mines when you know they all have to be Then I added two 'hidden' routines when I figured out how to express the information you used in your Clue routines. I forget just how much each routine did, but if you hit T or X you'll have the computer clear up quite a bit of what's unexposed. The default sizes I programmed in were a 20x39 grid with 111 bombs (I think); if your first guess uncovers at least a half-dozen adjacent blank cells, chances are that one iteration of routine X will completely solve the puzzle. A couple of iterations almost always reduces the problem to an insolvable requiring guessing. As I recall, the simplest configuration I could solve by hand which I did not attempt to encode was when given a top-left corner of the array containing 0 1 ? 1 2 ? ? ? ? in which case the last '?' covers a safe cell. Determining this requires the use of three of the equations (x1+x2=1, x3+x4=1, x1+x2+x3+x4+x5=2 imply x5=0.) My program won't do that for you automatically. There is also the question of which square is the best choice to uncover when it is impossible to find a safe cell. I don't know how to address this most effectively. 'Best' could be interpreted to mean 'least likelihood of being a mine' or 'most likely to yield useful information' or a combination of these. The former characterization is at least computable. One need only enumerate all solutions to the linear equations, and then find the variable x_i which is =0 in the largest number of these solutions. This is unlikely to be effective when the number of still-uncovered cells is more than a dozen or so. I see you've stashed away solutions to a few other puzzles and games. I'll have to keep your URL handy. ============================================================================== Date: Thu, 12 Jan 95 10:56:04 CST From: rusin (Dave Rusin) To: lloyd@lfmcal.cuc.ab.ca Subject: Re: no subject (file transmission) Thanks for your comments. Actually you were responding to someone else's post, not mine (see the attributions below) because I screwed up a follow-up post, quoting the previous person without posting my comments. Yes, certainly, there is some guessing involved. The following points were raised by other posters: 1. Windows' Minesweeper is rigged to never show a mine on the first move. 2. Methodical treatment of the data known often permit a safe solution; combining comments 1 and 2, it is happens rather frequently that no guessing is required to complete the solution. 3. Certain configurations permit no deductions of the locations of the mineswithout a guess. 4. Based on the information available at any point during the game, if a guess is necessary, there may be some squares which are more likely to contain mines than others. No one posted a method for selecting the safest guess, although in most cases an exhaustive enumeration of cases is feasible. Frankly, I think most people either eyeball it or select a square randomly when they do have to guess. 5. The game is additictive. I found out I was not the only one to code a simulation of the game which could incorporate some known methods of attack. ============================================================================== From: prm@rz.uni-jena.de (Ralf Muschall) Newsgroups: sci.math Subject: Re: Minesweeper is driving me nuts. Date: 29 Jan 1995 21:35:19 GMT ... Easy: Press shift, type XYZZY, then hold Alt+Ctrl and watch the upper left pixel on the monitor when moving the mouse. It is black or white depending whether you are on a mine or not. Ralf