Thursday, September 13, 2007

Spider Solitaire

Ok, I've waited a long time to write this post. It's a reflection back to Arizona where I played large amounts of Spider Solitaire. Most of the time, I played it on easy, with only one suit. However, I decided to move up and tackle medium. I must say, it was quite a switch, and it took me a while to find out the secret of doing it. And I'll reveal that secret right now.

But first, here's something I call one of the fundamental problems of computer science (in reality it's probably not so grandiose, but to me it's extremely intriguing). Lets say you have two objects and you wanted to swap them. The only way to do it is by having a temporary space to move one object, then to move it back. Here's a graphical example of it (forgive its horribleness. I can't draw, even on a computer):
Here, we start out with our two objects, out of order. Now, what we have to do is move them. However, we can only do this with the temporary space: as shown by the next slides (if you could come up with a way to do it without the extra space, you'd probably be able to win an important prize of some sort).We moved X into the temporary storage slot. Now we swap Y.We moved Y, and now we move X back, and they're in order. As you can see.
See, now the objects have been swapped and are in order. However, if you just look before and after, the temp is empty. However, the seemingly unused temp area is integral for the ability to swap the two elements. However, it's not just swapping which needs this. Anyone who has tried switching the name of two files has encountered this, because two files cannot have the same name. So, in order to do it, you need a temporary name for one file while you rename the other file.

Now you're wondering how this connects with Spider Solitaire. Well, in Spider Solitaire you're going to have to eventually mix red cards and black cards, you can't keep them separate for very long. However, Lets say you have a six of diamonds on a seven of spades on an eight of diamonds (8D/7S/6D). Then all of the sudden, an eight of spades turns up (8S). You'd like to put your 7 on there, but you can't directly. However, if you have an empty column (a temp), this impossible task becomes very easy. You move the 6D to the temp, then the 7S onto the 8S, then move the 6D back onto the 7S. So, you'll end up having the more orderly 8S/7S/6D. And your temp will be empty to accept a new card. Now you can do it over and over until you stop having cards in this position. Now, if you have TWO temps, you can go deeper. For example, if that 8S was a 9D instead, you can move the 6D to one temp, the 7S to the other, the 8D to the 9D, and move them back. You're left with the two black columns again. Now, this strategy does NOT guarantee you will win (my victory rate was about 50%). However, gaining this concept is essential to being able to beat Spider Solitaire past the easy level. Heck, if you apply this to the easy level, it's pretty much guaranteed you'll win. So, I find it funny that I was able to gain a fundamental insight in computer science, and even the physical world by playing a simple card game (one by Microsoft too). And that's my lesson for tonight! Don't expect more original picture by me.

1 comment:

Khaled Khalil said...

Spider Solitaire, it is the most essential task i have to do in my job, so a rate of 50% seems to through me out of this job (if they can) :) .
my really nightmare in Spider Solitaire is of course the expert mode with 4 suits (apparently it is the only mode in gnome's AisleRiot :( ).
but about replacing objects, the most common (and interresting) game for a fan of computer science is of course the tower of hanoi, i am pretty sure you already know it better than me