4 ms·

Clay Mathematics Institute: Ian Stewart on Minesweeper

RiderOfGiraffes 16y ago
I've submitted an interview with Ian Stewart here: http://news.ycombinator.com/item?id=1594526 http://news.ycombinator.com/item?id=1594526 He's a serious mathematician, and a serious writer of both fiction and non-fiction.
aerique 16y ago
Maybe I should read more, but this is the clearest explanation of P vs NP I've read so far.
- Jun8 16y ago
  Ditto. Tying something quite abstract as SAT to a game that a 5-year old can understand is a great way to teach it.
- RiderOfGiraffes 16y ago
  Interesting. Do you think it's clearer than the one I gave here? http://news.ycombinator.com/item?id=1587884 http://news.ycombinator.com/item?id=1587884
acangiano 16y ago
I will be interviewing Ian soon for Math-Blog.com. If you have any specific questions you think I should ask him, please feel free to let me know.
NinetyNine 16y ago
Figure 3 is incomplete; as the space depicted in it is not a valid board configuration. If either x or x' is false, then the respective 1s on the extreme sides will be invalid. This is either a crop of a real situation (in which we assume the wire repeats beyond the scope of the image), or an error.
- RiderOfGiraffes 16y ago
  It is a crop of a board containing a wire that extends beyond the area shown. It is not an error, although indicating (somehow - people's intuitions vary) that it's a crop would help.
  - deleted 16y ago
    [deleted]
jcl 16y ago
As a side note, if you enjoy playing Minesweeper but don't like losing to a bad guess, you might want to try the implementation in Simon Tatham's puzzle collection: http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ Unlike most other implementations, it only generates boards that can be solved by logic, so you never need to guess; your first square is guaranteed to be safe and to reveal enough information to progress. (IIRC, the algorithm used to pre-solve each generated level bottoms out in an exhaustive search, so I guess this game variant is still in NP.)

I've submitted an interview with Ian Stewart here: http://news.ycombinator.com/item?id=1594526 http://news.ycombinator.com/item?id=1594526 He's a serious mathematician, and a serious writer of both fiction and non-fiction.

aerique 16y ago

Maybe I should read more, but this is the clearest explanation of P vs NP I've read so far.

Jun8 16y ago
Ditto. Tying something quite abstract as SAT to a game that a 5-year old can understand is a great way to teach it.
RiderOfGiraffes 16y ago
Interesting. Do you think it's clearer than the one I gave here? http://news.ycombinator.com/item?id=1587884 http://news.ycombinator.com/item?id=1587884

acangiano 16y ago

I will be interviewing Ian soon for Math-Blog.com. If you have any specific questions you think I should ask him, please feel free to let me know.

NinetyNine 16y ago

Figure 3 is incomplete; as the space depicted in it is not a valid board configuration. If either x or x' is false, then the respective 1s on the extreme sides will be invalid. This is either a crop of a real situation (in which we assume the wire repeats beyond the scope of the image), or an error.

RiderOfGiraffes 16y ago
It is a crop of a board containing a wire that extends beyond the area shown. It is not an error, although indicating (somehow - people's intuitions vary) that it's a crop would help.
- deleted 16y ago
  [deleted]

jcl 16y ago

As a side note, if you enjoy playing Minesweeper but don't like losing to a bad guess, you might want to try the implementation in Simon Tatham's puzzle collection: http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ Unlike most other implementations, it only generates boards that can be solved by logic, so you never need to guess; your first square is guaranteed to be safe and to reveal enough information to progress. (IIRC, the algorithm used to pre-solve each generated level bottoms out in an exhaustive search, so I guess this game variant is still in NP.)