From rusin@vesuvius.math.niu.edu Thu Oct 21 00:37:23 CDT 1999 Article: 277514 of sci.math Path: news.math.niu.edu!rusin From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Freecell Date: 15 Oct 1999 23:15:07 GMT Organization: Northern Illinois Univ., Dept. of Mathematical Sciences Lines: 29 Message-ID: <7u8chr$oeg$1@gannett.math.niu.edu> References: <3806e3e2@webpc1.vai.co.at> <7u71bl$plm$1@autumn.news.rcn.net> NNTP-Posting-Host: vesuvius.math.niu.edu X-Trace: gannett.math.niu.edu 940029307 25040 131.156.3.93 (15 Oct 1999 23:15:07 GMT) X-Complaints-To: news@math.niu.edu NNTP-Posting-Date: 15 Oct 1999 23:15:07 GMT Xref: news.math.niu.edu sci.math:277514 In article <7u71bl$plm$1@autumn.news.rcn.net>, Bruce Frech wrote: >Minesweeper: you have about a one in six chance of solving the minesweeper >game at the expert level. > >Reference: I wrote a program to play the game using most of the simple rules >one uses to play the game. When none of the rules give 100% confidence in >marking a cell it picks the safest cell. Then I had it play 1000s of games. > >It was an interesting exercise in converting the techniques used to play the >game into code. Most rules involved simple sets and unions and >intersections of sets. I did this at least 5 years ago and don't know if I >could find the code. It's linear algebra: let X_i be the number of mines in square i; obviously this number is either 0 or 1, but you can use these variables to process information. Every time a cell is uncovered (safely!) we see a number, which information can be written as a linear equation of the form X_{i1} + ... + X_{i8} = N . The equation is a little simple when you've uncovered an edge or corner cell. You have also the single equation Sum( X_i ) = (Total number of mines). I found that typically one need only make a couple of random guesses (when the equations fail to specify an additional X_i which had to equal 0) in order to solve a puzzle completely. http://www.math.niu.edu/~rusin/uses-math/games/minesweeper/ dave