Timeline for Klondike Solitaire as an NP-complete game
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 7 at 15:28 | history | edited | Daniele Tampieri | CC BY-SA 4.0 |
Added the precise reference
|
| Oct 7 at 15:18 | review | Close votes | |||
| Oct 22 at 3:09 | |||||
| Oct 7 at 15:16 | comment | added | Syl | So even though a large percentage of all possible hands can be solved quickly using information from previously played hands and solitaire has been shown to be NP-complete (see link to paper) that solitaire can still be classified as NP-complete | |
| Oct 7 at 15:10 | comment | added | Will Sawin | That just isn't how NP is defined. One can't say an individual problem like a hand of solitaire is or isn't NP-complete. Rather NP-completeness is a property of an infinite sequence of problems like all possible hands of solitaire (after generalizing solitaire to larger decks of cards so that there are infinitely many possible hands). If a sequence (called for historical reasons a language) is NP-complete then every member is contained in a NP-complete subsequence and every member is contained in a subsequence in P. | |
| Oct 7 at 15:07 | comment | added | Syl | That is what I was looking for "some cases of the problem are hard" are hard and NP-complete while other are simple and P or intermediate NP cases using information from previous plays of a given hand Given any hand there are two possible decisions (1) is there a solution (yes/no) (2) is the solution optimal i.e. done in the fews number of moves (yes/no) I can see that #2 is NP but from what you said it seems #2 can range from P to NP Does this sound correct? | |
| Oct 7 at 15:02 | comment | added | Will Sawin | NP-completeness just means that some cases of the problem are hard - it's fine if these cases are very rare, so rare that they would never occur in practice with random hands. So this isn't really any evidence on the question. | |
| Oct 7 at 14:57 | comment | added | Syl | Yes - I find that using information from previously played hands I can find a solution to more than 60% of hands within 2 or 3 plays. There are some instance that take more plays and other instances that are very difficult are likely NP. There seems to be an unstated assumption in the original rules from a couple of centuries ago when played with cards that the search for a solution was done in only one try. With the advent of the digital form of the game hands can be replayed using information gleaned from failed hands | |
| Oct 7 at 14:44 | comment | added | Will Sawin | I don't know about this specific case, but usually proofs of NP-completeness do not rely on any assumptions about missing information since problems in NP by definition provide all relevant information to the problem-solver. Is there a specific reason that you think this one might? | |
| S Oct 7 at 14:36 | review | First questions | |||
| Oct 7 at 14:52 | |||||
| S Oct 7 at 14:36 | history | asked | Syl | CC BY-SA 4.0 |