› ›

ITT P is NP

CalicaCalica
in General
Oh look, all the encryption algorithms I thought would be solid are easily breakable!

Finding an optimal path along all these cities is easy!

I can solve Minesweeper, Tetris, and every contrived scenario in every classic board or video game.

Solving Go?  Don't be silly.  That's PSPACE.  Definitely unsolvable.

Comments

  • Imipolex GImipolex G
    Touch the cow. Do it now.
    but do you know why kids love Cinnamon Toast Crunch?
  • KlinotaxisKlinotaxis
    kill living beings
    *runs numbers* yeah it stimulates this network of gustatory receptors and
  • HavenHaven
    Let me tell you. About Fallen London.
    full traveling salesman now
  • BeeBee
    Minesweeper still throws mathematically unsolvable stuff even if P = NP.

    Like, it's pretty trivial to come up with a counterexample because it happens in like 3/4 games.
  • Salix BabylonikaSalix Babylonika
    https://i.imgur.com/7Iil2JW.png
    .....

    there are unsolvable Minesweeper boards?
  • BeeBee
    Yeah, you get unsolvable 50/50 (or worse) guesses all the time.

    It's like the whole reason Hexcells got popular, because it explicitly makes sure that doesn't happen.
  • KlinotaxisKlinotaxis
    kill living beings
    every square's mined. unsolvable
  • BeeBee
    edited 2016-02-16 05:33:45
    As an example.

    This, in the lower-left corner of the board.  Two mines remaining.  Everything else done.

    As an extra fuck you, this can happen at the very end of a large board.  And is distressingly likely to.

    image


    ^ Every square being mined is trivially solvable (at least logically, if not mechanically because you probably have to click something to trigger the game end), because you can compare total mines to the board size.  It becomes unsolvable when not quite every square is mined.

    IIRC the game used to ensure the first click was always safe, too -- not sure if it still does.  If your first click was a mine, it just quietly moved it somewhere else.
  • Imipolex GImipolex G
    Touch the cow. Do it now.
    solution: stop fucking playing minesweeper and get back to work
  • Salix BabylonikaSalix Babylonika
    https://i.imgur.com/7Iil2JW.png
    Bee said:

    Yeah, you get unsolvable 50/50 (or worse) guesses all the time.


    It's like the whole reason Hexcells got popular, because it explicitly makes sure that doesn't happen.
    excuse me I have a friend from 3rd grade I need to phone and call on his bullshit
  • BeeBee
    edited 2016-02-16 05:41:27
    I guess it's possible more recent versions of Minesweeper might generate their levels to deliberately be solvable.  They sure as hell don't do it as recently as Vista.
  • glennmagusharveyglennmagusharvey
    If you want an implementation of Minesweeper that can do things like guarantee safe clicks when guessing and/or guarantee mines when there could be mines, check out MinesPerfect.
  • AlirozAliroz
    ...And even when your hope is gone
    move along, move along, just to make it through
    (2015 self)
    And all this time I thought I was bad at minesweeper.
Sign In or Register to comment.