tldr: Win a million dollars by finding a polynomial-time algorithm to solve Minesweeper, or by proving it can't be done. From the Clay Mathematics Institute: http://www.claymath.org/Popular_Lectures/Minesweeper/
I realize that the paper, "Minesweeper is NP-complete" by Richard Kaye, was first published in 2000, but the idea is new to me! I just found out about it yesterday when doing background research for a new app idea.
So, basically, Richard Kaye knew Minesweeper was hard, but wasn't quite sure how hard. He arranged mines on the board so that they would simulate logic circuits (AND, OR, NOT...). He then correlated the logic circuits to a previously-known NP-complete problem, SAT.
I found a version of Minesweeper online that allows players to write Java code in order to solve the game, but unfortunately, it doesn't appear to be working.
The reason I'm probably interested in this is because when I learned how to play this game many, many years ago (before I was programming), I started to write an algorithm for it. I thought, an algorithm is the perfect way to teach somebody how to do something -- it is all very logical. I shouldn't have to explain more.
References:
[1] http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm
[2] "Minesweeper is NP-complete", Mathematical Intelligencer, vol 22, number 2, pp9-15, 2000.
~ Simply Advanced ~
ps - I'm very likely going to create apps that revolve around Minesweeper now. Actually, I was already considering it. That's how I found out about the NP-completeness.
I realize that the paper, "Minesweeper is NP-complete" by Richard Kaye, was first published in 2000, but the idea is new to me! I just found out about it yesterday when doing background research for a new app idea.
So, basically, Richard Kaye knew Minesweeper was hard, but wasn't quite sure how hard. He arranged mines on the board so that they would simulate logic circuits (AND, OR, NOT...). He then correlated the logic circuits to a previously-known NP-complete problem, SAT.
I found a version of Minesweeper online that allows players to write Java code in order to solve the game, but unfortunately, it doesn't appear to be working.
The reason I'm probably interested in this is because when I learned how to play this game many, many years ago (before I was programming), I started to write an algorithm for it. I thought, an algorithm is the perfect way to teach somebody how to do something -- it is all very logical. I shouldn't have to explain more.
References:
[1] http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm
[2] "Minesweeper is NP-complete", Mathematical Intelligencer, vol 22, number 2, pp9-15, 2000.
~ Simply Advanced ~
ps - I'm very likely going to create apps that revolve around Minesweeper now. Actually, I was already considering it. That's how I found out about the NP-completeness.
No comments:
Post a Comment