Welcome to the group. Here's what little I have to share about writing a
FreeCell solver.
As I understand it, FreeCell is part of the Traveling Salesman class of
problems. As such, the complexity of solving a given problem increases
exponentially as you proceed along exploring solution paths. This makes
it too complicated and time consuming to try and solve by simply
traveling all possible paths. Even if your objective is to simple find
any solution, this technique is very time consuming before you reach the
first solution. Basically, "brute force" won't work on FreeCell.
In addition, many paths are composed of move sequences that are simply
permutations of each other. As such, there are many sequences that lead
you to the same FreeCell layout. One of the first things needed in an
effective solver is to remove "redundant" paths. Even so, the remaining
paths continue to grow exponentially and it's not feasible to examine
all of them in a reasonable amount of time.
At some point, you will be forced to give-up on trying every search path
and narrowing your searches through some restriction mechanism. How you
narrow the list depends on what you want from your solver. If you only
want to know if a deal can be solved, then that's been done to death and
there are lists readily available for the few unsolvable deals. If you
only want to solve the odd deal that has you beaten, then I suggest you
just download someone else's solver. It'll save you a lot of headache!
However, if you still feel committed to writing your own solver, then be
prepared to put in a lot of time and effort. Good Luck!!!
HELSER ERIC JOSEPH wrote:
> Hello, my name is Taren, and I'm new to this group. Monday, I played a
> long marathon of Freecell games. By the end of all that, my wrist was
> really sore. Tuesday I decided I'd write a program to do all the
> thinking for me, and began shortly after. So here it is, Thursday at
> 1AM and I'm stuck. Just as expected.
>
> I'm finding that my program gets stuck in loops very often. I've told
> it to play MS#1 and #12345, and it'll get a good 10 moves in before
> getting stuck in a rut. Usually it's more than just 3D from 4C to 4S
> and back.
>
> Sure, I could just go download someone else's work, but I'm mostly
> doing this just for a challenge (and the ability to use it to test
> seemingly impossible variants featured on NetCell).
>
> Has anyone else had issues with the program not being able to
> recognize endless loops? Maybe it's just the algorithm I used? I bet
> you guys enjoy deciphering source code as much as I do, so I'll try to
> avoid posting that for now.
>
> Looking forward to a reply.
> -Taren
Received on Thu Nov 13 2003 - 16:33:22 IST