This is slightly off-topic but I thought it may be of interest to the
list.
I wrote a program that automatically solves Freecell games. For those
who are not familiar with it, Freecell is a card game, in which there
are several stacks which should be moved to the decks with the aid of
freecells, which are cells that can hold one card each.
In any case, the program operates by keeping record of the states for
which it checked whether they are solveable, so if the same state is
reached twice, it will only be checked once. (and thus also, it makes
sure there are no infinite loops). I wrote two versions of the program,
one which uses states where the representitive integers have widthes of
ints and shorts. And the second the integers are chars, and semi-chars.
(I use shifts and bit masks to get the card deck and card number).
I noticed that the program that uses the chars representation runs much
faster than the int/short based program. For 100 given initial boards,
it finished them in 11 minutes and 12 seconds. The wider program took
more than 19 minutes when it was terminated in the middle of board No.
62, which is a complex board that takes 42,940 checked states to
solution.
The question is why the wide-integer based program is slower because
obviously my Pentium 166 MHz processor takes less time for 32-bit or
16-bit integer computations and memory access than for 8-bit
ones. My best guess so far is that the majority of the time is spent
storing and searching for states, and because the char storage occupies
less space, that it is considerably faster.
What do you think?
You can download Freecell Solver and take a look at the source code
from the following URL:
http://t2.technion.ac.il/~shlomif/fcs/
This is not going to be its permanent homepage, but I resorted to
putting it there because vipe.technion.ac.il has a momentary problem of
hosting the users' homepages.
I discovered a few other insights while working on Freecell Solver. For
instance, I realized that one should not use qsort to insert a sort
margin into a sorted array, because it's quite slow. Instead, a
binary-search based merging function should be used.
Another curious thing is that the program runs differently on Windows
NT than it does on i386 Linux and SPARC Solaris. On IRIX 64-bit it runs
differnetly than both of the above. I still don't know what's the cause
of this behaviour but I'm investigating it.
Best regards,
Shlomi Fish
----------------------------------------------------------------------
Shlomi Fish [EMAIL PROTECTED]
Home Page: http://t2.technion.ac.il/~shlomif/
Home E-mail: [EMAIL PROTECTED]
The prefix "God Said" has the extraordinary logical property of
converting any statement that follows it into a true one.
=================================================================
To unsubscribe, send mail to [EMAIL PROTECTED] with
the word "unsubscribe" in the message body, e.g., run the command
echo unsubscribe | mail [EMAIL PROTECTED]
