A couple of observations.
A move from an incompatible parent is not well defined as such, in my opinion.
I like to think of the contents of a column as empty, singletons, sequenced,
partially sequenced, and fully unsequenced. It is only from a fully unsequenced
column to a freecell that you get an irreversible move (from any other type of
parent, you get a reversible move). Likewise, from one column to another you
have to move the entire top sequence to get an irreversible move.
Secondly, I think the number of irreversible moves is far fewer than 52*2.
Every column to column, irreversible move, puts another card into sequence.
When all 52 cards are in sequence, the game is (the same as) solved. A trip
from one column to another might be through a free cell, but the move from
freecell to column is reversible, so it wouldn’t be counted.
My definitions are based on treating a valid multi-card move as a single
move. If that definition isn’t used, I admit to not having thought through
the above statements. It just seems to me that a freecell solver needs
to handle multi-card moves as a single unit, or they become needlessly
complex.
From: Shlomi Fish
Sent: Tuesday, January 24, 2012 8:31 AM
To: Freecell Solving Discussions
Subject: [RFC] Spec for a new Freecell solver based on Fully Connected Components
Hi all,
this is a spec for a new solver I'd like to write based on partitioning the
graph of the positions emerging from a certain initial position, into fully
connected components. My hope is that this will allow to conserve space
further in case we would just like to know whether an initial board layout is
solvable and if so - what would be one of its solutions (not necessarily at a
very good speed).
I had the idea for doing something like that for a long time now, but kept
reaching dead ends, until I came up with the final "Eureka" moment today.
Any comments would be welcome.
Regards,
Shlomi Fish
Irreversible moves:
-------------------
1. Moving a card from a freecell/column to the foundations.
2. Moving a card from an incompatible parent (by initial layout) to a different
freecell/column.
Reversible moves:
-----------------
All the rest.
Analysis of the game graph:
---------------------------
The game graph is a DAG (directed acyclic graph) of
fully-connected components (FCCs),
where the fully-connected components are composed of reversible moves and
the edges between fully-connected components are irreversible moves.
Furthermore, in order to reach FCC we need to perform all the relevant
irreversible moves that yielded it. As a result, one needs the same amount of
irreversible moves to reach a certain FCC so they can be sorted according to
their depth, which is measured by the number of irreversible moves.
Note that the depth of an FCC cannot exceed 52*2 which is the maximal number
of irreversible moves.
Represnting a Fully-connected Component:
----------------------------------------
typedef struct
{
/* The minimal state in the fully-connected component, according to
the lexical sorting of the encoded state keys. This is used to identify
it and avoid collisions and re-processing.
*/
fcs_encoded_state_buffer_t min_by_sorting;
/* The minimal state by absolute depth (including that of
reversible moves). Not absolutely minimal, because the first
$depth-1 FCC that reaches it, wins the jackpot.
*/
fcs_encoded_state_buffer_t min_by_absolute_depth;
/* Moves to the min_by_absolute_depth from the initial state.
(accumlative).
*/
MOVE_STACK_T moves_to_min_by_absolute_depth;
} fcs_fully_connected_component_t;
The solver's state:
-------------------
struct
{
struct prev_depth_FCCs
{
int fcc_depth_idx;
List<fcs_fully_connected_component_t> to_scan_queue;
};
struct next_depth_FCCs
{
int fcc_depth_idx;
Map{min_by_sorting => Bool Exists} DoesExists;
List<fcs_fully_connected_component_t> queue;
/* Optionally: */
LRU_Map{any_state_in_the_FCCs => Bool Exists} Cache;
};
} fcs_fcc_solver_state_t;
The algorithm:
#. FOREACH <prev_depth_FCCs.to_scan_queue >
#. Perform a BrFS from min_by_absolute_depth to find all the next FCC
startpoints (the positions in the graph that followed an irreversible move).
#. For each of these startpoints:
#. Perform a BrFS scan to find the new FCC min_by_sorting (the scan will
be only on reversible moves).
#. ==> This is done while performing a lookup+insert for each state on
next_depth_FCCs.Cache, and stopping if it's there.
#. If it does not exist in next_depth_FCCs.DoesExists, add the new
min_by_sorting and min_by_absolute_depth (the start point) append a new FCC
to next_depth_FCCs.queue.
#. If it does, halt the search for this startpoint.
#. END FOREACH <prev_depth_FCCs.to_scan_queue>
#. Free next_depth_FCCs.DoesExists , next_depth_FCCs.Cache.
#. Free prev_depth_FCCs.to_scan_queue.
#. prev_depth_FCCs.fcs_depth_idx = next_depth_FCCs.fcs_depth_idx
#. next_depth_FCCs.fcs_depth_idx++;
#. prev_depth_FCCs.to_scan_queue ← next_depth_FCCs.queue;
#. next_depth_FCCs.DoesExists = new empty one ;
next_depth_FCCs.queue = new empty one ;
next_depth_FCCs.Cache = new empty one ;
--
----------------------------------------------------------
Shlomi Fish http://www.shlomifish.org/
My Favourite FOSS - http://www.shlomifish.org/open-source/favourite/
Emacs is a nice operating system, but what it lacks, in order to compete with
Linux, is a good text editor.
— based on http://en.wikiquote.org/wiki/Emacs
Please reply to list if it's a mailing list post - http://shlom.in/reply .
Received on Tue Jan 24 2012 - 08:59:05 IST