# Discworld (Spider Solitaire Version)

Here is yet another Spider Solitaire short story and puzzle (Disclaimer: I do not have a Bachelor of Arts in creative writing).

Once upon a time there lived a number of $$N$$ wooden circular discs. All discs were of different sizes and they were all avid fans of Spider Solitaire. The largest disc also happened to be the best player. One day she reached an interesting game state (game state A). She had two empty columns and thought it would be desirable to build a run of 10-9-8-7-6-5 in Hearts.

“But that’s easy,” said the second-largest disc. “All you have to do is shift the 3-2 in Column 8 onto a Four in Column 2/5 in order to expose the Six of Clubs.”

The largest disc insisted she dare not touch column 8. Surely it couldn’t hurt to keep in reserve the extra option of not shifting the Three of Spades onto an offsuit four (game state B). She knew from bitter experience that attention-to-detail could often spell the difference between victory and defeat. Alas, not touching column 8 proved more difficult than she anticipated. The other discs also tried to help but to no avail. Against their better judgment the wooden discs toiled on for hour after hour, day after day, week after week … tempers started to fray and the smallest disc had the temerity to offer her own opinion.

“I successfully defended my Ph. D. thesis three weeks ago”, said the smallest disc. “Perhaps we can succeed by attacking the problem systematically instead of trying random stuff and seeing what happens”

“You are the weakest player of the group,” the largest disc replied. “Your advanced math has no place in the Royal Game. It is possible to obtain a respectable win-rate at the four-suit level without undoing any moves, even if you have never heard of the Fundamental Theorem Of Calc-”

“Yeah, leave us alone,” said the second-smallest disc, “and stick to your lousy 40% win rate at the two-suit level!”

“It’s a million-to-one chance,” said the smallest disc. “But it might just work!”

Eventually the team resigned themselves to the inevitable and agreed to analyse the problem more systematically. And lo and behold, after exactly $$2^N – 1$$ days they managed to find the correct sequence of moves. It wasn’t necessarily the shortest move sequence but it was good enough for their purposes. The bullying of the smallest disc had miraculously stopped and everybody lived happily ever after.

THE END

Questions

(1) prove that the following two game states A/B are equivalent, i.e. starting from A/B you can reach B/A with a sequence of legal moves.

(2) What is the significance of $$2^N – 1$$ in the above story?

Note: in both game states, a minus sign indicates a face-down card and the stock is empty. For purposes of this puzzle, please ignore the incorrect card distribution (e.g. fewer than 104 cards).

Game State A

Text version:

-Ac -Ac Ks Qc Js 0c 9d 8h 7h 6h 5h 4c 3h 2c

-2c -2c 0h 9h 8s 7h 6c 5s 4c

empty

-4c -4c 0h

Kd Qd Jd 0d 9d 8d 7d 6d 5d 4d

-6c -6c 0s

empty

-8c -8c 8c 7d 6s 5d 4h 3s 2d 7c 6c 3s 2c

-9c -9c 5s Ks Qh Ac

-0c -0c Qc 2h Ah

Checksum: 14 + 9 + 0 + 3 + 10 + 3 + 0 + 13 + 6 + 5 + (10*0) = 63 < 104

Game State B

Text version:

-Ac -Ac Ks Qc Js 0c 9d 8s 7h 6c 5s 4c

-2c -2c 0h 9h 8h 7h 6h 5h 4c 3h 2c

empty

-4c -4c 0h

Kd Qd Jd 0d 9d 8d 7d 6d 5d 4d

-6c -6c 0s

empty

-8c -8c 8c 7d 6s 5d 4h 3s 2d 7c 6c 3s 2c

-9c -9c 5s Ks Qh Ac

-0c -0c Qc 2h Ah

Checksum: 12 + 11 + 0 + 3 + 10 + 3 + 0 + 13 + 6 + 5 + (10*0) = 63 < 104

Acknowledgement: Thanks to my friend Bart for sending me an interesting game position via email. I have simplified his position by removing irrelevant information (hence the incorrect card distribution of the game states A/B above).