Laura Creighton schrieb:
In a message of Wed, 02 Sep 2009 03:29:36 +0200, Gregor Lingl writes:
Laura Creighton schrieb:
In a message of Mon, 31 Aug 2009 22:23:55 PDT, kirby urner writes:
<snip>
On break, we encourage playing with Pysol maybe...
http://www.pysol.org/
http://pysolfc.sourceforge.net/
http://tktable.sourceforge.net/tile/
http://pygames.sourceforge.net/
Kirby
4D
I think that the pysol game 'Pile On' is always solvable.
Anybody know for sure? Writing a program that exhaustively creates
all the possible layouts and then solves them seems possible,
Hi Laura,
I fear that this is not practicable. There are 52! =
80658175170943878571660636856403766975289505440883277824000000000000
permutations of 52 cards. If one considers the permutations of the 13 pil
es
as equivalent and also the permutations of the four suits one still
arrives at a number
of possible Pile On games that exceeds by far the number of nanoseconds
that passed
since the beginning of the universe.
I don't think that it is quite as bad as all that, given that all we
really have is a set of 52 cards which are 4 sets of 13 cards with
different marks on them. Thus there is a significant reduction you
can make at the start because an initial set where all the 8s are
swapped for all the 4s are equivalent.
Yes, you are certainly right. Nevertheless, if I take 52!,
- divide it by (4!)**13 accounting for the not-distinguishability of the
four sorts of a suit
- divide this by 13! accounting for the interchangability of the ranks
(your suggestion)
- divide this by 13! accounting for the permutations of the 13 piles
I arrive at 2373239768247142364082899540328 which is still
approx. 3.7 e+12 times the age of the universe in seconds.
May be there are still more symmetries to be considered. For me
combinatorics
is an unstable ground :-(
But then, I wasn't really looking for the brute-force proof, but the
elegant one. I was hoping for an induction proof for 4 sets of 4
cards, n cards, and n + 1 cards, but so far I haven't managed it.
Yes, I understood. An elegant mathematical proof for this would be
interesting. I'd like
to see one. But what if the conjecture is wrong?
My ugly little backtracking program could not solve the following
configuration:
(
(8, 4, 10, 4),
(9, 3, 2, 10),
(11, 6, 3, 9),
(8, 7, 1, 13),
(6, 8, 7, 12),
(5, 9, 12, 1),
(13, 3, 2, 1),
(13, 4, 6, 3),
(12, 6, 7, 7),
(11, 4, 10, 9),
(12, 5, 11, 11),
(2, 1, 5, 13),
(5, 8, 2, 10),
(),
()
)
Although out of of a series of 100 randomly generated start situations
this is the
only one it could not solve, I fear chances are much higher, that my
program has a bug
than that this is indeed not solvable. However I'd be very glad to see a
solution for this
configuration. (Do you have a deck of cardes at hand?)
I for my part cannot check this, because there are many configurations I
cannot solve
by hand that *are* solvable by my script. So, if I cannot mange it, that
means nothing.
(Indeed originally I started to write this script because I tought
it might find a counterexample).
Best wishes (for finding the proof, and more)
Gregor
Yes, I would also be interested in such a proof. I for my part learned
to know Pile On
only today and I find it rather difficult to play. So from my own very
irrelevant
experience would expect that there are start configurations which might
not be solvable -
--- at least for me :-(
Don't believe the strategy that pysol gives about not stacking 3 cards
of a same rank on a single. As far as I can tell that is nonsense. But
do keep track of what cards are on the bottom.
Thanks for the deverting hint
Gregor
You are most welcome. :-)
Laura
_______________________________________________
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig
