Hi Gary!
On Wednesday 13 May 2009 16:55:05 Gary Campbell wrote:
> Let's take another crack at this puzzler. If there is anyone
> "out there" who is remotely interested in FreeCell solvers,
> you have got to be concerned about the theoretical fanout
> of FreeCell moves. Fanout needs to be restricted to the
> minimum of necessary moves at each step. Investigating
> every possible move is not only unnecessary, but it
> guarantees that a solver cannot perform an exhaustive
> search in any practical time.
Well, I'm not if the fanout is so important. If we want to solve a given
Freecell initial layout, then we may encounter some positions with a large
fanout, but can you show that it affects the effectiveness of the solver?
Moreover, given that my solver does meta-moves, the number of possible meta-
moves extending from one position, is theoretically bigger than the number of
individual moves (including multi-card moves). So counting the individual
moves may not be so revealing.
>
> Therefore, the purpose of this exercise is to discuss the
> maximum fanout with the maximum of limitations, i.e.
> never allowing an unnecessary move. Clearly, at certain
> points, there are few or zero moves possible. At other
> points there may be quite a few. However, a possible
> move may not be a necessary move. For example, if
> you try moving a card to one of 4 empty free cells, and
> can't find a solution by doing so, moving it to one of
> the other free cells does not need to be tried. This 2nd
> move is unnecessary or redundant. There are many
> such moves. This is essentially a discussion of them.
>
> I can imagine that the proof that a move is redundant
> could get to be quite complex, indeed.
>
> So, again, what is the maximum NECESSARY
> fanout given some constructed layout, such as the
> one Shlomi proposes below (or one of your own
> choosing)? I chose a layout with only one empty
> free cell and one empty column to produce the
> maximum of 41 moves that I came up with.
May you tell us which layout this is, so we can learn from it, and try to
improve upon it?
>
> By the way, regarding Shlomi's layout below, I
> calculate that there are zero NECESSARY moves.
> The layout produces an immediate flourish!
>
Well, my solver still has to do all the moves of the cards to the foundations
explicitly. In most configurations, this will be the first thing it tries to
do, but these are still counted as explicit moves.
> It was a useful example to get the discussion
> started, however. But no discussion occurred!
> Is there anybody out there?
Maybe only I. ;-)
Regards,
Shlomi Fish
--
-----------------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
What Makes Software Apps High Quality - http://xrl.us/bkeuk
God gave us two eyes and ten fingers so we will type five times as much as we
read.
Received on Thu May 14 2009 - 02:11:41 IDT