Boiledbeans

Drama! Intrigue! Geekiness!

March 11, 2009

Beginner == Expert?

devadutta @ 10:07 pm, GMT +0000 ( 1236809246 ) Play

Connect

7274d54579acf4b210819f75c6244889de449c4ea5fad3d902cf8b23ee94ff67

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 :)


14 Responses to “Beginner == Expert?”

  1. udupendra
    4
    4
    7

    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.


  2. 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.


  3. sidsen
    2

    np complete


  4. Ps

    1. Minesweeper game
    2.hamiltonian path

    Connect: NP-Complete (Nondeterministic Polynomial time) problems

    http://en.wikipedia.org/wiki/NP-complete


  5. username
    3
    3
    1

    Minesweeper and Hamiltonian Path
    NP complete


  6. Raghuvansh
    1
    9
    4

    Minesweeper and Hamiltonian path problems. NP-complete.


  7. 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”


  8. Mo

    Both Hamiltonian Paths and Minesweeper are NP-Complete


  9. Gautam Dn(RV)

    All i can think of is A Hamilton cycle is the solution to Minesweeper


  10. Ananth
    4
    5
    9

    Hamiltonian path is NP Complete.
    Apparently, Minesweeper is too.


  11. shrik
    10
    7
    9

    NP-completeness!

    Minesweeper and the Hamiltonian Cycle path.


  12. darthshak

    The P=NP problem

    Minesweeper was proven to be NP-complete. On the right is the Hamiltonian path problem which is also NP-complete.


  13. sand

    NP complete problems.


  14. Ps

    surprising P v NP and his merry men missed it :D


« Previous « Desi Awesomeness « | » Better off searching for Carmen Sandiego? » Next »