March 11, 2009
Beginner == Expert?
PlayConnect
Cracked by: udupendra , Jean Valjean , sidsen , Ps , username , Raghuvansh , Mo , Ananth , shrik , darthshak and sand.
Answer: Minesweeper, just like the Hamiltonian path(cycle) problem, is NP-Complete.
Minesweeper is used as a common example while teaching NP-Completeness :)
Subscribe
Play
Head 2 Head
this->bb();
March 11th, 2009 at 10:32 pm, GMT +0000 ( 1236810761 )
Don’t know if this is what you are looking for, but a valid connect is that both Minesweeper, and the Travelling Salesperson Problem (which is nothing but finding a Hamiltonian Path like the one shown above) have been both proved to be NP-Complete.
March 11th, 2009 at 10:37 pm, GMT +0000 ( 1236811068 )
NP-Complete problems :
1. Determination whether a position in a Minesweeper game is consistent with some placement of mines. Used as the unofficial description of the P vs Np problem by CMI
2. Determining whether Hamiltonian paths and cycles exist in graphs. Classic NP complete problem.
March 11th, 2009 at 10:55 pm, GMT +0000 ( 1236812156 )
np complete
March 11th, 2009 at 10:58 pm, GMT +0000 ( 1236812312 )
1. Minesweeper game
2.hamiltonian path
Connect: NP-Complete (Nondeterministic Polynomial time) problems
http://en.wikipedia.org/wiki/NP-complete
March 12th, 2009 at 12:00 am, GMT +0000 ( 1236816021 )
Minesweeper and Hamiltonian Path
NP complete
March 12th, 2009 at 12:50 am, GMT +0000 ( 1236819008 )
Minesweeper and Hamiltonian path problems. NP-complete.
March 12th, 2009 at 4:28 am, GMT +0000 ( 1236832091 )
Confusion over whether difficulty level in Minesweeper is related to ordinal numbers?
Dug this up from wiki:
“The subtraction of one from the time is required in some implementations due to the fact that minesweeper begins with one second on the clock (as opposed to zero) and as such the time shown is always about one second greater than the actual time taken and nothing related to ordinal numbers as someone could wrongly believe”
March 12th, 2009 at 4:53 am, GMT +0000 ( 1236833591 )
Both Hamiltonian Paths and Minesweeper are NP-Complete
March 12th, 2009 at 5:23 am, GMT +0000 ( 1236835384 )
All i can think of is A Hamilton cycle is the solution to Minesweeper
March 12th, 2009 at 6:52 am, GMT +0000 ( 1236840768 )
Hamiltonian path is NP Complete.
Apparently, Minesweeper is too.
March 12th, 2009 at 7:40 am, GMT +0000 ( 1236843655 )
NP-completeness!
Minesweeper and the Hamiltonian Cycle path.
March 12th, 2009 at 8:45 am, GMT +0000 ( 1236847502 )
The P=NP problem
Minesweeper was proven to be NP-complete. On the right is the Hamiltonian path problem which is also NP-complete.
March 12th, 2009 at 12:02 pm, GMT +0000 ( 1236859377 )
NP complete problems.
March 14th, 2009 at 8:08 am, GMT +0000 ( 1237018114 )
surprising P v NP and his merry men missed it :D