Jay Little - Software Obsessionist
The Minesweeper Algorithim - Introduction

I heard your solution doesn't work... is that true?

The current version of this algorithim does not return consistent results - stay tuned for my next attempt though. The current version is a major step up from previous versions though. It is far more consistent than they ever were. Based upon the nature of the inconsistency - it may be possible to eliminate it with additional checks and balances.

How did you prove that the results were not consistent?

I wrote a validation routine which served the purpose of validating the most important concept to this algorithim: That keypoints could be processed independently of each other. This of course ended up not being the case. Check out the code and the thread at ArsTechnica.

When will the next version be out?

Not anytime soon - I'm pretty burned out on Minesweeper as I've spent the last week frying my brain cells on this problem. I'm taking a vacation :-)

What is the Minesweeper consistency problem?

The "Minesweeper Consistency Problem" (aka MCP) is a problem in which you are trying to determine whether or not a given Minesweeper board in logically consistent with the rules of the game.

Whats the big deal? Its just a stupid game?

Yes Minesweeper is just a game. But the consistency problem deals with a subject that goes far beyond simple games. The MCP is considered to be NP complete. NP complete problems are not supposed to have P solutions. This one does.

Doesnt that just mean that the MCP is a P Problem?

No it doesnt. Through a process of reduction using another NP complete problem known as SAT - Minesweeper has been proven to be at least as hard as that problem. Of course if Minesweeper has a P solution - that means the SAT problem also has a P solution.

What is your point?

That the mathmatical process of reducing one problem to another can in fact be used to solve NP complete problems in P time. I highly doubt the MCP problem is actually NP complete - but the SAT problem is. If the SAT NP problem now has a P solution - this means that P=NP.

Do you get a kick out of making stuff up?

No. This is the real deal. Check the download page for the VB source code to the ActiveX library I wrote that attempts to prove this. Check the Explanation page for a detailed explanation on why my algorithim should works.

[Top] [Rss] [Email]