Great result! Solving deals manually brought me something like 350 moves per deal.
Have you used "heuristic strategy" from the paper
that you gave a link on it: "Solitaire: Man Versus Machine"?
Proving optimality looks to me is like giving it a full tree search - hardly a real option
Yes, I get around 350 moves manually too. The best human solvers get around 320 moves.
I remember reading an article describing some better heuristics. Use scholar.google.com and search for klondike or spider solitaire.
Personally, I use an heuristic, but it's completely different (and simpler too !).
I spent a lot of time tuning it though...
A full tree search doesn't seem impossible, because a lot of pruning is possible.
In fact, I still have several possible improvements, like a better moves generator. For example, I can move cards simply by swapping 2 bytes.
But right now, I'll take some rest, since I used a lot of time on this contest
