search

ShootMe / Klondike-Solver

https://github.com/ShootMe/MinimalKlondike for the updated Solver
MIT License
64 stars 29 forks source link

Very very rarely you have to worry back to the same pile #10

Open turingfan opened 5 years ago

turingfan commented 5 years ago

Hi I've constructed a deal which Klondike Solver reports as unsolvable but in fact it should be solvable.

The problem in this game is that you have to worry back a card immediately after moving it to foundations, to the same pile it came from. The reason this is necessary is because it flips a card, which after worrying back can be moved as a unit.

In this example the action is on tableau piles 3 and 4. We can't move 2H onto 3C yet, but instead we have to move up AC 2C 3C, then immediately move 3C on to the newly flipped 4H, then put the 2H on it and the 2H-3C-4H on 5C. Then we have won.

0: 1: AC 2: 2C -6C 3: 2H -5C-AD 4: 3C -4H-AS-AH 5: 2S -3S-3H-5H-KH 6: 6S -4C-2D-3D-4D-KD 7: 4S -6H-5S-5D-6D-KS-KC 8: QC QD QH QS JC JD JH JS TC TD TH TS 9C 9D 9H 9S 8C 8D 8H 8S 7C 7D 7H 7S 9: 10: 11: 12: Minimum Moves Needed: 82

Impossible. Max cards in foundation 3 at 5 moves. Took 300000 ms.

The input string for the above is 011061012013133132131021051014053042134023043033032062031034022052024041054064063044121122123124111112113114101102103104091092093094081082083084071072073074

While I constructed the above to convince myself it's a bug, I did come across a bug in a random game, which I suspect is either this or a similar issue of refusing to reverse moves, deal 8721. I believe this one is solvable /DC 3 but is reported as unsolvable.

Thanks for your attention.

ShootMe commented 5 years ago

Very interesting. Not sure I'll work on fixing it in this code base, but I have been thinking of working on a newer code base with some extra features at some point, and would check it out then.

Thanks for the info.

turingfan commented 5 years ago

Sure many thanks for the response.

turingfan commented 5 years ago

By the way, I've come across this as I am working on an academic paper about Solitaire solving. I would like to cite Klondike-Solver as it is obviously the best solver for klondike there is out there right now. I am happy to cite you as Devil Squirrel but if you want to get a name check I can obviously give you proper credit if you want it. Feel free to get in touch with me - easy to find my email from my profile my home page. Obviously if you don't want your name revealed that's fine too.