/*
 * freecell.c - The various movement tests performed by Freecell Solver
 *
 * Written by Shlomi Fish (shlomif@vipe.technion.ac.il), 2000-2001
 *
 * This file is in the public domain (it's uncopyrighted).
 */

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <limits.h>


#include "fcs_config.h"

#if FCS_STATE_STORAGE==FCS_STATE_STORAGE_LIBREDBLACK_TREE
#include <search.h>
#endif

#include "state.h"
#include "card.h"
#include "fcs_dm.h"
#include "fcs.h"

#include "fcs_isa.h"
#include "tests.h"
#include "ms_ca.h"

#ifdef DMALLOC
#include "dmalloc.h"
#endif

#define state_with_locations (*ptr_state_with_locations)
#define state (ptr_state_with_locations->s)
#define new_state_with_locations (*ptr_new_state_with_locations)
#define new_state (ptr_new_state_with_locations->s)


#ifndef min
#define min(a,b) (((a)<(b))?(a):(b))
#endif

/*
 * Throughout this code the following local variables are used to quickly
 * access the instance's members:
 *
 * state_stacks_num - the number of stacks in the state
 * state_freecells_num - the number of freecells in the state
 * sequences_are_built_by - the type of sequences of this board.
 * */

/*
 * This function tries to move stack cards that are present at the
 * top of stacks to the foundations.
 * */
int freecell_solver_sfs_move_top_stack_cards_to_founds(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();
    int stack;
    int cards_num;
    int deck;
    fcs_card_t card;
    fcs_card_t temp_card;
    int check;
    int state_stacks_num;

    fcs_move_t temp_move;

    tests_define_accessors();

    moves = hard_thread->reusable_move_stack;
    indirect_stacks_buffer = hard_thread->indirect_stacks_buffer;

    state_stacks_num = instance->stacks_num;

    for(stack=0;stack<state_stacks_num;stack++)
    {
        cards_num = fcs_stack_len(state, stack);
        if (cards_num)
        {
            /* Get the top card in the stack */
            card = fcs_stack_card(state,stack,cards_num-1);
            for(deck=0;deck<instance->decks_num;deck++)
            {
                if (fcs_foundation_value(state, deck*4+fcs_card_suit(card)) == fcs_card_card_num(card) - 1)
                {
                    /* We can put it there */

                    sfs_check_state_begin();


                    my_copy_stack(stack);
                    fcs_pop_stack_card(new_state, stack, temp_card);

                    fcs_increment_foundation(new_state, deck*4+fcs_card_suit(card));


		    fcs_move_init(temp_move);
                    fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_FOUNDATION);
                    fcs_move_set_src_stack(temp_move,stack);
                    fcs_move_set_foundation(temp_move,deck*4+fcs_card_suit(card));

                    fcs_move_stack_push(moves, temp_move);

                    fcs_flip_top_card(stack);

                    /* The last move needs to be FCS_MOVE_TYPE_CANONIZE
                     * because it indicates that the internal order of the
                     * stacks
                     * and freecells may have changed. */
                    fcs_move_set_type(temp_move,FCS_MOVE_TYPE_CANONIZE);
                    fcs_move_stack_push(moves, temp_move);

                    sfs_check_state_end()
                    break;
                }
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}


/*
 * This test moves single cards that are present in the freecells to
 * the foundations.
 * */
int freecell_solver_sfs_move_freecell_cards_to_founds(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();
    int fc;
    int deck;
    fcs_card_t card;
    int check;
    fcs_move_t temp_move;
    int state_freecells_num;

    tests_define_accessors();

    state_freecells_num = instance->freecells_num;

    /* Now check the same for the free cells */
    for(fc=0;fc<state_freecells_num;fc++)
    {
        card = fcs_freecell_card(state, fc);
        if (fcs_card_card_num(card) != 0)
        {
            for(deck=0;deck<instance->decks_num;deck++)
            {
                if (fcs_foundation_value(state, deck*4+fcs_card_suit(card)) == fcs_card_card_num(card) - 1)
                {
                    /* We can put it there */
                    sfs_check_state_begin()

                    fcs_empty_freecell(new_state, fc);

                    fcs_increment_foundation(new_state, deck*4+fcs_card_suit(card));

		    fcs_move_init(temp_move);
                    fcs_move_set_type(temp_move,FCS_MOVE_TYPE_FREECELL_TO_FOUNDATION);
                    fcs_move_set_src_freecell(temp_move,fc);
                    fcs_move_set_foundation(temp_move,deck*4+fcs_card_suit(card));

                    fcs_move_stack_push(moves, temp_move);

                    fcs_move_set_type(temp_move,FCS_MOVE_TYPE_CANONIZE);
                    fcs_move_stack_push(moves, temp_move);

                    sfs_check_state_end();
                }
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}

int freecell_solver_sfs_move_freecell_cards_on_top_of_stacks(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();
    
    int dest_cards_num;
    int ds, fc, dc;
    fcs_card_t dest_card, src_card, temp_card, dest_below_card;
    int check;

    fcs_move_t temp_move;
    int is_seq_in_dest;
    int num_cards_to_relocate;
    int freecells_to_fill, freestacks_to_fill;
    int a,b;
    int state_freecells_num, state_stacks_num, sequences_are_built_by;

    tests_define_accessors();

    state_freecells_num = instance->freecells_num;
    state_stacks_num = instance->stacks_num;
    sequences_are_built_by = instance->sequences_are_built_by;

    /* Let's try to put cards in the freecells on top of stacks */

    /* ds stands for destination stack */
    for(ds=0;ds<state_stacks_num;ds++)
    {
        dest_cards_num = fcs_stack_len(state, ds);

        /* If the stack is not empty we can proceed */
        if (dest_cards_num > 0)
        {
            /*
             * Let's search for a suitable card in the stack
             * */
            for(dc=dest_cards_num-1;dc>=0;dc--)
            {
                dest_card = fcs_stack_card(state, ds, dc);

                /* Scan the freecells */
                for(fc=0;fc<state_freecells_num;fc++)
                {
                    src_card = fcs_freecell_card(state, fc);

                    /* If the freecell is not empty and dest_card is its parent
                     * */
                    if ( (fcs_card_card_num(src_card) != 0) &&
                         fcs_is_parent_card(src_card,dest_card)     )
                    {
                        /* Let's check if we can put it there */

                        /* Check if the destination card is already below a
                         * suitable card */
                        is_seq_in_dest = 0;
                        if (dest_cards_num - 1 > dc)
                        {
                            dest_below_card = fcs_stack_card(state, ds, dc+1);
                            if (fcs_is_parent_card(dest_below_card, dest_card))
                            {
                                is_seq_in_dest = 1;
                            }
                        }


                        if (! is_seq_in_dest)
                        {
                            num_cards_to_relocate = dest_cards_num - dc - 1;

                            freecells_to_fill = min(num_cards_to_relocate, num_freecells);

                            num_cards_to_relocate -= freecells_to_fill;

                            if (instance->empty_stacks_fill == FCS_ES_FILLED_BY_ANY_CARD)
                            {
                                freestacks_to_fill = min(num_cards_to_relocate, num_freestacks);

                                num_cards_to_relocate -= freestacks_to_fill;
                            }
                            else
                            {
                                freestacks_to_fill = 0;
                            }

                            if (num_cards_to_relocate == 0)
                            {
                                /* We can move it */

                                sfs_check_state_begin()


                                /* Fill the freecells with the top cards */

                                my_copy_stack(ds);

                                for(a=0 ; a<freecells_to_fill ; a++)
                                {
                                    /* Find a vacant freecell */
                                    for(b=0;b<state_freecells_num;b++)
                                    {
                                        if (fcs_freecell_card_num(new_state, b) == 0)
                                        {
                                            break;
                                        }
                                    }
                                    fcs_pop_stack_card(new_state, ds, temp_card);

                                    fcs_put_card_in_freecell(new_state, b, temp_card);

				    fcs_move_init(temp_move);
                                    fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_FREECELL);
                                    fcs_move_set_src_stack(temp_move,ds);
                                    fcs_move_set_dest_freecell(temp_move,b);
                                    fcs_move_stack_push(moves, temp_move);
                                }

                                /* Fill the free stacks with the cards below them */
                                for(a=0; a < freestacks_to_fill ; a++)
                                {
                                    /* Find a vacant stack */
                                    for(b=0;b<state_stacks_num;b++)
                                    {
                                        if (fcs_stack_len(new_state, b) == 0)
                                        {
                                            break;
                                        }
                                    }
                                    my_copy_stack(b);

                                    fcs_pop_stack_card(new_state, ds, temp_card);
                                    fcs_push_card_into_stack(new_state, b, temp_card);
                                    fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_STACK);
                                    fcs_move_set_src_stack(temp_move,ds);
                                    fcs_move_set_dest_stack(temp_move,b);
                                    fcs_move_set_num_cards_in_seq(temp_move,1);
                                    fcs_move_stack_push(moves, temp_move);
                                }

                                /* Now put the freecell card on top of the stack */
                                
                                fcs_push_card_into_stack(new_state, ds, src_card);
                                fcs_empty_freecell(new_state, fc);
                                fcs_move_set_type(temp_move,FCS_MOVE_TYPE_FREECELL_TO_STACK);
                                fcs_move_set_src_freecell(temp_move,fc);
                                fcs_move_set_dest_stack(temp_move,ds);
                                fcs_move_stack_push(moves, temp_move);

                                sfs_check_state_end()
                            }
                        }
                    }
                }
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}



int freecell_solver_sfs_move_non_top_stack_cards_to_founds(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();
    
    int check;

    int stack;
    int cards_num;
    int c, a, b;
    fcs_card_t temp_card, card;
    int deck;
    int state_freecells_num;
    int state_stacks_num;

    fcs_move_t temp_move;
    fcs_move_init(temp_move);

    tests_define_accessors();

    state_freecells_num = instance->freecells_num;
    state_stacks_num = instance->stacks_num;



    /* Now let's check if a card that is under some other cards can be placed
     * in the foundations. */

    for(stack=0;stack<state_stacks_num;stack++)
    {
        cards_num = fcs_stack_len(state, stack);
        /*
         * We starts from cards_num-2 because the top card is already covered
         * by move_top_stack_cards_to_founds.
         * */
        for(c=cards_num-2 ; c >= 0 ; c--)
        {
            card = fcs_stack_card(state, stack, c);
            for(deck=0;deck<instance->decks_num;deck++)
            {
                if (fcs_foundation_value(state, deck*4+fcs_card_suit(card)) == fcs_card_card_num(card)-1)
                {
                    /* The card is foundation-able. Now let's check if we
                     * can move the cards above it to the freecells and
                     * stacks */

                    if ((num_freecells +
                        ((instance->empty_stacks_fill == FCS_ES_FILLED_BY_ANY_CARD) ?
                            num_freestacks :
                            0
                        ))
                            >= cards_num-(c+1))
                    {
                        /* We can move it */

                        sfs_check_state_begin()

                        my_copy_stack(stack);


                        /* Fill the freecells with the top cards */
                        for(a=0 ; a<min(num_freecells, cards_num-(c+1)) ; a++)
                        {
                            /* Find a vacant freecell */
                            for(b=0; b<state_freecells_num; b++)
                            {
                                if (fcs_freecell_card_num(new_state, b) == 0)
                                {
                                    break;
                                }
                            }
                            fcs_pop_stack_card(new_state, stack, temp_card);

                            fcs_put_card_in_freecell(new_state, b, temp_card);

                            fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_FREECELL);
                            fcs_move_set_src_stack(temp_move,stack);
                            fcs_move_set_dest_freecell(temp_move,b);

                            fcs_move_stack_push(moves, temp_move);

                            fcs_flip_top_card(stack);
                        }

                        /* Fill the free stacks with the cards below them */
                        for(a=0; a < cards_num-(c+1) - min(num_freecells, cards_num-(c+1)) ; a++)
                        {
                            /* Find a vacant stack */
                            for(b=0;b<state_stacks_num;b++)
                            {
                                if (fcs_stack_len(new_state, b) == 0)
                                {
                                    break;
                                }
                            }

                            my_copy_stack(b);

                            fcs_pop_stack_card(new_state, stack, temp_card);
                            fcs_push_card_into_stack(new_state, b, temp_card);

                            fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_STACK);
                            fcs_move_set_src_stack(temp_move,stack);
                            fcs_move_set_dest_stack(temp_move,b);
                            fcs_move_set_num_cards_in_seq(temp_move,1);

                            fcs_move_stack_push(moves, temp_move);

                            fcs_flip_top_card(stack);
                        }

                        fcs_pop_stack_card(new_state, stack, temp_card);
                        fcs_increment_foundation(new_state, deck*4+fcs_card_suit(temp_card));

                        fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_FOUNDATION);
                        fcs_move_set_src_stack(temp_move,stack);
                        fcs_move_set_foundation(temp_move,deck*4+fcs_card_suit(temp_card));

                        fcs_move_stack_push(moves, temp_move);

                        fcs_flip_top_card(stack);

                        sfs_check_state_end()
                    }
                    break;
                }
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}




int freecell_solver_sfs_move_stack_cards_to_a_parent_on_the_same_stack(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();
    int check;

    int stack, c, cards_num, a, dc,b;
    int is_seq_in_dest;
    fcs_card_t card, temp_card, prev_card;
    fcs_card_t dest_below_card, dest_card;
    int freecells_to_fill, freestacks_to_fill;
    int dest_cards_num, num_cards_to_relocate;
    int state_freecells_num;
    int state_stacks_num;
    int sequences_are_built_by;

    fcs_move_t temp_move;
    fcs_move_init(temp_move);

    tests_define_accessors();

    state_freecells_num = instance->freecells_num;
    state_stacks_num = instance->stacks_num;
    sequences_are_built_by = instance->sequences_are_built_by;

    /*
     * Now let's try to move a stack card to a parent card which is found
     * on the same stack.
     * */
    for (stack=0;stack<state_stacks_num;stack++)
    {
        cards_num = fcs_stack_len(state, stack);

        for (c=0 ; c<cards_num ; c++)
        {
            /* Find a card which this card can be put on; */

            card = fcs_stack_card(state, stack, c);


            /* Do not move cards that are already found above a suitable parent */
            a = 1;
            if (c != 0)
            {
                prev_card = fcs_stack_card(state, stack, c-1);
                if ((fcs_card_card_num(prev_card) == fcs_card_card_num(card)+1) &&
                    ((fcs_card_suit(prev_card) & 0x1) != (fcs_card_suit(card) & 0x1)))
                {
                   a = 0;
                }
            }
            if (a)
            {
#define ds stack
                /* Check if it can be moved to something on the same stack */
                dest_cards_num = fcs_stack_len(state, ds);
                for(dc=0;dc<c-1;dc++)
                {
                    dest_card = fcs_stack_card(state, ds, dc);
                    if (fcs_is_parent_card(card, dest_card))
                    {
                        /* Corresponding cards - see if it is feasible to move
                           the source to the destination. */

                        is_seq_in_dest = 0;
                        dest_below_card = fcs_stack_card(state, ds, dc+1);
                        if (fcs_is_parent_card(dest_below_card, dest_card))
                        {
                            is_seq_in_dest = 1;
                        }

                        if (!is_seq_in_dest)
                        {
                            num_cards_to_relocate = dest_cards_num - dc - 1;

                            freecells_to_fill = min(num_cards_to_relocate, num_freecells);

                            num_cards_to_relocate -= freecells_to_fill;

                            if (instance->empty_stacks_fill == FCS_ES_FILLED_BY_ANY_CARD)
                            {
                                freestacks_to_fill = min(num_cards_to_relocate, num_freestacks);

                                num_cards_to_relocate -= freestacks_to_fill;
                            }
                            else
                            {
                                freestacks_to_fill = 0;
                            }

                            if (num_cards_to_relocate == 0)
                            {
                                /* We can move it */

                                sfs_check_state_begin()


                                {
                                    int i_card_pos;
                                    fcs_card_t moved_card;
                                    int source_type, source_index;

                                    i_card_pos = fcs_stack_len(new_state,stack)-1;
                                    a = 0;

                                    my_copy_stack(ds);
                                    while(i_card_pos>c)
                                    {
                                        if (a < freecells_to_fill)
                                        {
                                            for(b=0;b<state_freecells_num;b++)
                                            {
                                                if (fcs_freecell_card_num(new_state, b) == 0)
                                                {
                                                    break;
                                                }
                                            }
                                            fcs_pop_stack_card(new_state, ds, temp_card);
                                            fcs_put_card_in_freecell(new_state, b, temp_card);

                                            fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_FREECELL);
                                            fcs_move_set_src_stack(temp_move,ds);
                                            fcs_move_set_dest_freecell(temp_move,b);

                                            fcs_move_stack_push(moves, temp_move);

                                        }
                                        else
                                        {

                                            /*  Find a vacant stack */
                                            for(b=0;b<state_stacks_num;b++)
                                            {
                                                if (fcs_stack_len(new_state, b) == 0)
                                                {
                                                    break;
                                                }
                                            }

                                            my_copy_stack(b);

                                            fcs_pop_stack_card(new_state, ds, temp_card);
                                            fcs_push_card_into_stack(new_state, b, temp_card);

                                            fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_STACK);
                                            fcs_move_set_src_stack(temp_move,ds);
                                            fcs_move_set_dest_stack(temp_move,b);
                                            fcs_move_set_num_cards_in_seq(temp_move,1);

                                            fcs_move_stack_push(moves, temp_move);

                                        }
                                        a++;

                                        i_card_pos--;
                                    }
                                    fcs_pop_stack_card(new_state, ds, moved_card);
                                    if (a < freecells_to_fill)
                                    {
                                        for(b=0;b<state_freecells_num;b++)
                                        {
                                            if (fcs_freecell_card_num(new_state, b) == 0)
                                            {
                                                break;
                                            }
                                        }
                                        fcs_put_card_in_freecell(new_state, b, moved_card);
                                        fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_FREECELL);
                                        fcs_move_set_src_stack(temp_move,ds);
                                        fcs_move_set_dest_freecell(temp_move,b);
                                        fcs_move_stack_push(moves, temp_move);

                                        source_type = 0;
                                        source_index = b;
                                    }
                                    else
                                    {
                                        for(b=0;b<state_stacks_num;b++)
                                        {
                                            if (fcs_stack_len(new_state, b) == 0)
                                            {
                                                break;
                                            }
                                        }

                                        my_copy_stack(b);
                                        fcs_push_card_into_stack(new_state, b, moved_card);

                                        fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_STACK);
                                        fcs_move_set_src_stack(temp_move,ds);
                                        fcs_move_set_dest_stack(temp_move,b);
                                        fcs_move_set_num_cards_in_seq(temp_move,1);
                                        fcs_move_stack_push(moves, temp_move);

                                        source_type = 1;
                                        source_index = b;
                                    }
                                    i_card_pos--;
                                    a++;

                                    while(i_card_pos>dc)
                                    {
                                        if (a < freecells_to_fill)
                                        {
                                            for(b=0;b<state_freecells_num;b++)
                                            {
                                                if (fcs_freecell_card_num(new_state, b) == 0)
                                                {
                                                    break;
                                                }
                                            }
                                            fcs_pop_stack_card(new_state, ds, temp_card);
                                            fcs_put_card_in_freecell(new_state, b, temp_card);

                                            fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_FREECELL);
                                            fcs_move_set_src_stack(temp_move,ds);
                                            fcs_move_set_dest_freecell(temp_move,b);

                                            fcs_move_stack_push(moves, temp_move);
                                        }
                                        else
                                        {

                                            /*  Find a vacant stack */
                                            for(b=0;b<state_stacks_num;b++)
                                            {
                                                if (fcs_stack_len(new_state, b) == 0)
                                                {
                                                    break;
                                                }
                                            }

                                            fcs_pop_stack_card(new_state, ds, temp_card);
                                            my_copy_stack(b);
                                            fcs_push_card_into_stack(new_state, b, temp_card);

                                            fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_STACK);
                                            fcs_move_set_src_stack(temp_move,ds);
                                            fcs_move_set_dest_stack(temp_move,b);
                                            fcs_move_set_num_cards_in_seq(temp_move,1);

                                            fcs_move_stack_push(moves, temp_move);

                                        }
                                        a++;

                                        i_card_pos--;
                                    }

                                    if (source_type == 0)
                                    {
                                        moved_card = fcs_freecell_card(new_state, source_index);
                                        fcs_empty_freecell(new_state, source_index);

                                        fcs_move_set_type(temp_move,FCS_MOVE_TYPE_FREECELL_TO_STACK);
                                        fcs_move_set_src_freecell(temp_move,source_index);
                                        fcs_move_set_dest_stack(temp_move,ds);
                                        fcs_move_stack_push(moves, temp_move);
                                    }
                                    else
                                    {
                                        my_copy_stack(source_index);
                                        fcs_pop_stack_card(new_state, source_index, moved_card);

                                        fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_STACK);
                                        fcs_move_set_src_stack(temp_move,source_index);
                                        fcs_move_set_dest_stack(temp_move,ds);
                                        fcs_move_set_num_cards_in_seq(temp_move,1);
                                        fcs_move_stack_push(moves, temp_move);
                                    }

                                    fcs_push_card_into_stack(new_state, ds, moved_card);
                                }

                                sfs_check_state_end()
                            }
                        }
                    }
                }
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}
#undef ds


int freecell_solver_sfs_move_stack_cards_to_different_stacks(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();

    int check;

    int stack, c, cards_num, a, dc, ds,b;
    int is_seq_in_dest;
    fcs_card_t card, temp_card, this_card, prev_card;
    fcs_card_t dest_below_card, dest_card;
    int freecells_to_fill, freestacks_to_fill;
    int dest_cards_num, num_cards_to_relocate;
    int seq_end;
    int state_freecells_num;
    int state_stacks_num;
    int sequences_are_built_by;

    fcs_move_t temp_move;
    fcs_move_init(temp_move);

    tests_define_accessors();

    state_freecells_num = instance->freecells_num;
    state_stacks_num = instance->stacks_num;
    sequences_are_built_by = instance->sequences_are_built_by;

    /* Now let's try to move a card from one stack to the other     *
     * Note that it does not involve moving cards lower than king   *
     * to empty stacks                                              */

    for (stack=0;stack<state_stacks_num;stack++)
    {
        cards_num = fcs_stack_len(state, stack);

        for (c=0 ; c<cards_num ; c=seq_end+1)
        {
            /* Check if there is a sequence here. */
            for(seq_end=c ; seq_end<cards_num-1 ; seq_end++)
            {
                this_card = fcs_stack_card(state, stack, seq_end+1);
                prev_card = fcs_stack_card(state, stack, seq_end);

                if (fcs_is_parent_card(this_card,prev_card))
                {
                }
                else
                {
                    break;
                }
            }

            /* Find a card which this card can be put on; */

            card = fcs_stack_card(state, stack, c);

            /* Make sure the card is not flipped or else we can't move it */
            if (fcs_card_get_flipped(card) == 0)
            {
                for(ds=0 ; ds<state_stacks_num; ds++)
                {
                    if (ds != stack)
                    {
                        dest_cards_num = fcs_stack_len(state, ds);
                        for(dc=0;dc<dest_cards_num;dc++)
                        {
                            dest_card = fcs_stack_card(state, ds, dc);

                            if (fcs_is_parent_card(card, dest_card))
                            {
                                /* Corresponding cards - see if it is feasible to move
                                   the source to the destination. */

                                is_seq_in_dest = 0;
                                if (dest_cards_num - 1 > dc)
                                {
                                    dest_below_card = fcs_stack_card(state, ds, dc+1);
                                    if (fcs_is_parent_card(dest_below_card, dest_card))
                                    {
                                        is_seq_in_dest = 1;
                                    }
                                }

                                if (! is_seq_in_dest)
                                {
                                    num_cards_to_relocate = dest_cards_num - dc - 1 + cards_num - seq_end - 1;

                                    freecells_to_fill = min(num_cards_to_relocate, num_freecells);

                                    num_cards_to_relocate -= freecells_to_fill;

                                    if (instance->empty_stacks_fill == FCS_ES_FILLED_BY_ANY_CARD)
                                    {
                                        freestacks_to_fill = min(num_cards_to_relocate, num_freestacks);

                                        num_cards_to_relocate -= freestacks_to_fill;
                                    }
                                    else
                                    {
                                        freestacks_to_fill = 0;
                                    }

                                    if ((num_cards_to_relocate == 0) &&
                                       (calc_max_sequence_move(num_freecells-freecells_to_fill, num_freestacks-freestacks_to_fill) >=
                                        seq_end - c + 1))
                                    {
                                        /* We can move it */
                                        int from_which_stack;

                                        sfs_check_state_begin()


                                        /* Fill the freecells with the top cards */

                                        my_copy_stack(stack);
                                        my_copy_stack(ds);

                                        for(a=0 ; a<freecells_to_fill ; a++)
                                        {
                                            /* Find a vacant freecell */
                                            for(b=0;b<state_freecells_num;b++)
                                            {
                                                if (fcs_freecell_card_num(new_state, b) == 0)
                                                {
                                                    break;
                                                }
                                            }

                                            if (fcs_stack_len(new_state, ds) == dc+1)
                                            {
                                                from_which_stack = stack;
                                            }
                                            else
                                            {
                                                from_which_stack = ds;
                                            }
                                            my_copy_stack(from_which_stack);
                                            
                                            fcs_pop_stack_card(new_state, from_which_stack, temp_card);

                                            fcs_put_card_in_freecell(new_state, b, temp_card);

                                            fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_FREECELL);
                                            fcs_move_set_src_stack(temp_move,from_which_stack);
                                            fcs_move_set_dest_freecell(temp_move,b);
                                            fcs_move_stack_push(moves, temp_move);

                                            fcs_flip_top_card(from_which_stack);
                                        }

                                        /* Fill the free stacks with the cards below them */
                                        for(a=0; a < freestacks_to_fill ; a++)
                                        {
                                            /*  Find a vacant stack */
                                            for(b=0;b<state_stacks_num;b++)
                                            {
                                                if (fcs_stack_len(new_state, b) == 0)
                                                {
                                                    break;
                                                }
                                            }

                                            if (fcs_stack_len(new_state, ds) == dc+1)
                                            {
                                                from_which_stack = stack;
                                            }
                                            else
                                            {
                                                from_which_stack = ds;
                                            }
                                            
                                            my_copy_stack(b);
                                            fcs_pop_stack_card(new_state, from_which_stack, temp_card);
                                            fcs_push_card_into_stack(new_state, b, temp_card);
                                            fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_STACK);
                                            fcs_move_set_src_stack(temp_move,from_which_stack);
                                            fcs_move_set_dest_stack(temp_move,b);
                                            fcs_move_set_num_cards_in_seq(temp_move,1);
                                            fcs_move_stack_push(moves, temp_move);

                                            fcs_flip_top_card(from_which_stack);
                                        }

                                        for(a=c ; a <= seq_end ; a++)
                                        {
                                            fcs_push_stack_card_into_stack(new_state, ds, stack, a);
                                        }

                                        for(a=0; a < seq_end-c+1 ;a++)
                                        {
                                            fcs_pop_stack_card(new_state, stack, temp_card);
                                        }
                                        fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_STACK);
                                        fcs_move_set_src_stack(temp_move,stack);
                                        fcs_move_set_dest_stack(temp_move,ds);
                                        fcs_move_set_num_cards_in_seq(temp_move,seq_end-c+1);
                                        fcs_move_stack_push(moves, temp_move);

                                        fcs_flip_top_card(stack);

                                        sfs_check_state_end()
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}



int freecell_solver_sfs_move_sequences_to_free_stacks(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();
    int check;

    int stack, cards_num, c, ds, a, b, seq_end;
    fcs_card_t this_card, prev_card, temp_card;
    int max_sequence_len;
    int num_cards_to_relocate, freecells_to_fill, freestacks_to_fill;
    int state_freecells_num;
    int state_stacks_num;
    int sequences_are_built_by;

    fcs_move_t temp_move;
    fcs_move_init(temp_move);

    tests_define_accessors();

    if (instance->empty_stacks_fill == FCS_ES_FILLED_BY_NONE)
    {
        return FCS_STATE_IS_NOT_SOLVEABLE;
    }

    state_freecells_num = instance->freecells_num;
    state_stacks_num = instance->stacks_num;
    sequences_are_built_by = instance->sequences_are_built_by;

    max_sequence_len = calc_max_sequence_move(num_freecells, num_freestacks-1);

    /* Now try to move sequences to empty stacks */

    if (num_freestacks > 0)
    {
        for(stack=0;stack<state_stacks_num;stack++)
        {
            cards_num = fcs_stack_len(state, stack);

            for(c=0; c<cards_num; c=seq_end+1)
            {
                /* Check if there is a sequence here. */
                for(seq_end=c ; seq_end<cards_num-1; seq_end++)
                {
                    this_card = fcs_stack_card(state, stack, seq_end+1);
                    prev_card = fcs_stack_card(state, stack, seq_end);

                    if (! fcs_is_parent_card(this_card, prev_card))
                    {
                        break;
                    }
                }

                if ((fcs_stack_card_num(state, stack, c) != 13) &&
                    (instance->empty_stacks_fill == FCS_ES_FILLED_BY_KINGS_ONLY))
                {
                    continue;
                }

                if (seq_end == cards_num -1)
                {
                    /* One stack is the destination stack, so we have one     *
                     * less stack in that case                                */
                    while ((max_sequence_len < cards_num -c) && (c > 0))
                    {
                        c--;
                    }

                    if (
                        (c > 0) &&
                        ((instance->empty_stacks_fill == FCS_ES_FILLED_BY_KINGS_ONLY) ?
                            (fcs_card_card_num(fcs_stack_card(state, stack, c)) == 13) :
                            1
                        )
                       )
                    {
                        sfs_check_state_begin();


                        for(ds=0;ds<state_stacks_num;ds++)
                        {
                            if (fcs_stack_len(state, ds) == 0)
                                break;
                        }

                        my_copy_stack(ds);

                        for(a=c ; a <= cards_num-1 ; a++)
                        {
                            fcs_push_stack_card_into_stack(new_state, ds, stack, a);
                        }

                        my_copy_stack(stack);

                        for(a=0;a<cards_num-c;a++)
                        {
                            fcs_pop_stack_card(new_state, stack, temp_card);
                        }

                        fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_STACK);
                        fcs_move_set_src_stack(temp_move,stack);
                        fcs_move_set_dest_stack(temp_move,ds);
                        fcs_move_set_num_cards_in_seq(temp_move,cards_num-c);

                        fcs_move_stack_push(moves, temp_move);


                        sfs_check_state_end()
                    }
                }
                else
                {
                    num_cards_to_relocate = cards_num - seq_end - 1;

                    freecells_to_fill = min(num_cards_to_relocate, num_freecells);

                    num_cards_to_relocate -= freecells_to_fill;

                    if (instance->empty_stacks_fill == FCS_ES_FILLED_BY_ANY_CARD)
                    {
                        freestacks_to_fill = min(num_cards_to_relocate, num_freestacks);

                        num_cards_to_relocate -= freestacks_to_fill;
                    }
                    else
                    {
                        freestacks_to_fill = 0;
                    }

                    if ((num_cards_to_relocate == 0) && (num_freestacks-freestacks_to_fill > 0))
                    {
                        /* We can move it */
                        int seq_start = c;
                        while (
                            (calc_max_sequence_move(
                                num_freecells-freecells_to_fill,
                                num_freestacks-freestacks_to_fill-1) < seq_end-seq_start+1)
                                &&
                            (seq_start <= seq_end)
                            )
                        {
                            seq_start++;
                        }
                        if ((seq_start <= seq_end) &&
                            ((instance->empty_stacks_fill == FCS_ES_FILLED_BY_KINGS_ONLY) ?
                                (fcs_card_card_num(fcs_stack_card(state, stack, seq_start)) == 13) :
                                1
                            )
                        )
                        {
                            sfs_check_state_begin();


                            /* Fill the freecells with the top cards */

                            my_copy_stack(stack);

                            for(a=0; a<freecells_to_fill ; a++)
                            {
                                /* Find a vacant freecell */
                                for(b=0;b<state_freecells_num;b++)
                                {
                                    if (fcs_freecell_card_num(new_state, b) == 0)
                                    {
                                        break;
                                    }
                                }
                                fcs_pop_stack_card(new_state, stack, temp_card);
                                fcs_put_card_in_freecell(new_state, b, temp_card);

                                fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_FREECELL);
                                fcs_move_set_src_stack(temp_move,stack);
                                fcs_move_set_dest_freecell(temp_move,b);
                                fcs_move_stack_push(moves, temp_move);
                            }

                            my_copy_stack(stack);

                            /* Fill the free stacks with the cards below them */
                            for(a=0; a < freestacks_to_fill ; a++)
                            {
                                /* Find a vacant stack */
                                for(b=0; b<state_stacks_num; b++)
                                {
                                    if (fcs_stack_len(new_state, b) == 0)
                                    {
                                        break;
                                    }
                                }

                                my_copy_stack(b);
                                fcs_pop_stack_card(new_state, stack, temp_card);
                                fcs_push_card_into_stack(new_state, b, temp_card);
                                fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_STACK);
                                fcs_move_set_src_stack(temp_move,stack);
                                fcs_move_set_dest_stack(temp_move,b);
                                fcs_move_set_num_cards_in_seq(temp_move,1);
                                fcs_move_stack_push(moves, temp_move);
                            }

                            /* Find a vacant stack */
                            for(b=0; b<state_stacks_num; b++)
                            {
                                if (fcs_stack_len(new_state, b) == 0)
                                {
                                    break;
                                }
                            }

                            my_copy_stack(b);

                            for(a=seq_start ; a <= seq_end ; a++)
                            {
                                fcs_push_stack_card_into_stack(new_state, b, stack, a);
                            }
                            for(a=seq_start ; a <= seq_end ; a++)
                            {
                                fcs_pop_stack_card(new_state, stack, temp_card);
                            }

                            fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_STACK);
                            fcs_move_set_src_stack(temp_move,stack);
                            fcs_move_set_dest_stack(temp_move,b);
                            fcs_move_set_num_cards_in_seq(temp_move,seq_end-seq_start+1);
                            fcs_move_stack_push(moves, temp_move);

                            sfs_check_state_end();
                        }
                    }
                }
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}



int freecell_solver_sfs_move_freecell_cards_to_empty_stack(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();
    int check;
    int fc, stack;
    fcs_card_t card;

    fcs_move_t temp_move;

    int state_freecells_num;
    int state_stacks_num;

    /* Let's try to put cards that occupy freecells on an empty stack */

    tests_define_accessors();

    if (instance->empty_stacks_fill == FCS_ES_FILLED_BY_NONE)
    {
        return FCS_STATE_IS_NOT_SOLVEABLE;
    }

    state_freecells_num = instance->freecells_num;
    state_stacks_num = instance->stacks_num;

    for(fc=0;fc<state_freecells_num;fc++)
    {
        card = fcs_freecell_card(state, fc);
        if (
            (instance->empty_stacks_fill == FCS_ES_FILLED_BY_KINGS_ONLY) ?
                (fcs_card_card_num(card) == 13) :
                (fcs_card_card_num(card) != 0)
           )
        {
            for(stack=0;stack<state_stacks_num;stack++)
            {
                if (fcs_stack_len(state, stack) == 0)
                {
                    break;
                }
            }
            if (stack != state_stacks_num)
            {
                /* We can move it */

                sfs_check_state_begin();

                my_copy_stack(stack);

                fcs_push_card_into_stack(new_state, stack, card);
                fcs_empty_freecell(new_state, fc);

		fcs_move_init(temp_move);
                fcs_move_set_type(temp_move,FCS_MOVE_TYPE_FREECELL_TO_STACK);
                fcs_move_set_src_freecell(temp_move,fc);
                fcs_move_set_dest_stack(temp_move,stack);
                fcs_move_stack_push(moves, temp_move);

                sfs_check_state_end()
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}

int freecell_solver_sfs_move_cards_to_a_different_parent(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();

    int check;

    int stack, cards_num, c, a, b, ds, dc;
    int is_seq_in_src, is_seq_in_dest;
    int num_cards_to_relocate;
    int dest_cards_num;
    fcs_card_t card, this_card, prev_card, temp_card;
    fcs_card_t dest_card, dest_below_card;
    int freecells_to_fill, freestacks_to_fill;

    fcs_move_t temp_move;

    int state_freecells_num;
    int state_stacks_num;
    int sequences_are_built_by;

    tests_define_accessors();

    state_freecells_num = instance->freecells_num;
    state_stacks_num = instance->stacks_num;
    sequences_are_built_by = instance->sequences_are_built_by;

    fcs_move_init(temp_move);

    /* This time try to move cards that are already on top of a parent to a different parent */

    for (stack=0;stack<state_stacks_num;stack++)
    {
        cards_num = fcs_stack_len(state, stack);

        for (c=0 ; c<cards_num ; c++)
        {
            /* Check if there is a sequence here. */
            is_seq_in_src = 1;
            for(a=c+1 ; a<cards_num ; a++)
            {
                this_card = fcs_stack_card(state, stack, a);
                prev_card = fcs_stack_card(state, stack, a-1);

                if (fcs_is_parent_card(this_card,prev_card))
                {
                }
                else
                {
                    is_seq_in_src = 0;
                    break;
                }
            }

            /* Find a card which this card can be put on; */

            card = fcs_stack_card(state, stack, c);


            /* Do not move cards that are already found above a suitable parent */
            a = 1;
            if (c != 0)
            {
                prev_card = fcs_stack_card(state, stack, c-1);
                if (fcs_is_parent_card(card,prev_card))
                {
                   a = 0;
                }
            }
            /* And do not move cards that are flipped */
            if (!a)
            {
                this_card = fcs_stack_card(state,stack,c);
                if (fcs_card_get_flipped(this_card))
                {
                    a = 0;
                }
            }
            if (!a)
            {
                for(ds=0 ; ds<state_stacks_num; ds++)
                {
                    if (ds != stack)
                    {
                        dest_cards_num = fcs_stack_len(state, ds);
                        for(dc=0;dc<dest_cards_num;dc++)
                        {
                            dest_card = fcs_stack_card(state, ds, dc);

                            if (fcs_is_parent_card(card,dest_card))
                            {
                                /* Corresponding cards - see if it is feasible to move
                                   the source to the destination. */

                                is_seq_in_dest = 0;
                                if (dest_cards_num - 1 > dc)
                                {
                                    dest_below_card = fcs_stack_card(state, ds, dc+1);
                                    if (fcs_is_parent_card(dest_below_card,dest_card))
                                    {
                                        is_seq_in_dest = 1;
                                    }
                                }

                                if (! is_seq_in_dest)
                                {
                                    if (is_seq_in_src)
                                    {
                                        num_cards_to_relocate = dest_cards_num - dc - 1;

                                        freecells_to_fill = min(num_cards_to_relocate, num_freecells);

                                        num_cards_to_relocate -= freecells_to_fill;

                                        if (instance->empty_stacks_fill == FCS_ES_FILLED_BY_ANY_CARD)
                                        {
                                            freestacks_to_fill = min(num_cards_to_relocate, num_freestacks);

                                            num_cards_to_relocate -= freestacks_to_fill;
                                        }
                                        else
                                        {
                                            freestacks_to_fill = 0;
                                        }

                                        if ((num_cards_to_relocate == 0) &&
                                           (calc_max_sequence_move(num_freecells-freecells_to_fill, num_freestacks-freestacks_to_fill) >=
                                            cards_num - c))
                                        {
                                            /* We can move it */

                                            sfs_check_state_begin()


                                            /* Fill the freecells with the top cards */

                                            my_copy_stack(ds);
                                            for(a=0 ; a<freecells_to_fill ; a++)
                                            {
                                                /* Find a vacant freecell */
                                                for(b=0;b<state_freecells_num;b++)
                                                {
                                                    if (fcs_freecell_card_num(new_state, b) == 0)
                                                    {
                                                        break;
                                                    }
                                                }
                                                
                                                fcs_pop_stack_card(new_state, ds, temp_card);

                                                fcs_put_card_in_freecell(new_state, b, temp_card);

                                                fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_FREECELL);
                                                fcs_move_set_src_stack(temp_move,ds);
                                                fcs_move_set_dest_freecell(temp_move,b);
                                                fcs_move_stack_push(moves, temp_move);
                                            }

                                            /* Fill the free stacks with the cards below them */
                                            for(a=0; a < freestacks_to_fill ; a++)
                                            {
                                                /*  Find a vacant stack */
                                                for(b=0;b<state_stacks_num;b++)
                                                {
                                                    if (fcs_stack_len(new_state, b) == 0)
                                                    {
                                                        break;
                                                    }
                                                }

                                                my_copy_stack(b);

                                                fcs_pop_stack_card(new_state, ds, temp_card);
                                                fcs_push_card_into_stack(new_state, b, temp_card);

                                                fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_STACK);
                                                fcs_move_set_src_stack(temp_move,ds);
                                                fcs_move_set_dest_stack(temp_move,b);
                                                fcs_move_set_num_cards_in_seq(temp_move,1);
                                                fcs_move_stack_push(moves, temp_move);
                                            }

                                            my_copy_stack(stack);

                                            for(a=c ; a <= cards_num-1 ; a++)
                                            {
                                                fcs_push_stack_card_into_stack(new_state, ds, stack, a);
                                            }

                                            for(a=0;a<cards_num-c;a++)
                                            {
                                                fcs_pop_stack_card(new_state, stack, temp_card);
                                            }

                                            fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_STACK);
                                            fcs_move_set_src_stack(temp_move,stack);
                                            fcs_move_set_dest_stack(temp_move,ds);
                                            fcs_move_set_num_cards_in_seq(temp_move,cards_num-c);
                                            fcs_move_stack_push(moves, temp_move);

                                            sfs_check_state_end()
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}




int freecell_solver_sfs_empty_stack_into_freecells(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();

    int check;

    int stack, cards_num, c, b;
    fcs_card_t temp_card;
    int state_stacks_num;
    int state_freecells_num;

    fcs_move_t temp_move;

    tests_define_accessors();

    if (instance->empty_stacks_fill == FCS_ES_FILLED_BY_NONE)
    {
        return FCS_STATE_IS_NOT_SOLVEABLE;
    }

    state_stacks_num = instance->stacks_num;
    state_freecells_num = instance->freecells_num;


    /* Now, let's try to empty an entire stack into the freecells, so other cards can
     * inhabit it */

    if (num_freestacks == 0)
    {
        for(stack=0;stack<state_stacks_num;stack++)
        {
            cards_num = fcs_stack_len(state, stack);
            if (cards_num <= num_freecells)
            {
                /* We can empty it */

                sfs_check_state_begin()
                
                my_copy_stack(stack);

                for(c=0;c<cards_num;c++)
                {
                    /* Find a vacant freecell */
                    for(b=0; b<state_freecells_num; b++)
                    {
                        if (fcs_freecell_card_num(new_state, b) == 0)
                        {
                            break;
                        }
                    }
                    fcs_pop_stack_card(new_state, stack, temp_card);

                    fcs_put_card_in_freecell(new_state, b, temp_card);

		    fcs_move_init(temp_move);
                    fcs_move_set_type(temp_move,FCS_MOVE_TYPE_STACK_TO_FREECELL);
                    fcs_move_set_src_stack(temp_move,stack);
                    fcs_move_set_dest_freecell(temp_move,b);
                    fcs_move_stack_push(moves, temp_move);
                }

                sfs_check_state_end()
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;

}

int freecell_solver_sfs_yukon_do_nothing(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    return FCS_STATE_IS_NOT_SOLVEABLE;
}

int freecell_solver_sfs_yukon_move_card_to_parent(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();

    int check;

    int stack, cards_num, c, a, ds;
    int dest_cards_num;
    fcs_card_t card, temp_card;
    fcs_card_t dest_card;

    int state_stacks_num;
    int sequences_are_built_by;

    fcs_move_t temp_move;

    tests_define_accessors();

    state_stacks_num = instance->stacks_num;
    sequences_are_built_by = instance->sequences_are_built_by;

    for( ds=0 ; ds < state_stacks_num ; ds++ )
    {
        dest_cards_num = fcs_stack_len(state, ds);
        if (dest_cards_num > 0)
        {
            dest_card = fcs_stack_card(state, ds, dest_cards_num-1);
            for( stack=0 ; stack < state_stacks_num ; stack++)
            {
                if (stack == ds)
                {
                    continue;
                }
                cards_num = fcs_stack_len(state, stack);
                for( c=cards_num-1 ; c >= 0 ; c--)
                {
                    card = fcs_stack_card(state, stack, c);
                    if (fcs_card_get_flipped(card))
                    {
                        break;
                    }
                    if (fcs_is_parent_card(card, dest_card))
                    {
                        /* We can move it there - now let's check to see
                         * if it is already above a suitable parent. */
                        if ((c == 0) ||
                            (! fcs_is_parent_card(card, fcs_stack_card(state, stack, c-1))))
                        {
                            /* Let's move it */
                            sfs_check_state_begin();

                            my_copy_stack(stack);
                            my_copy_stack(ds);

                            fcs_move_sequence(ds, stack, c, cards_num-1, a);

                            fcs_flip_top_card(stack);

                            sfs_check_state_end();
                        }

                    }
                }
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}

int freecell_solver_sfs_yukon_move_kings_to_empty_stack(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();

    int check;

    int stack, cards_num, c, a, ds;
    fcs_card_t card, temp_card;

    int state_stacks_num;

    fcs_move_t temp_move;

    tests_define_accessors();

    if (num_freestacks == 0)
    {
        return FCS_STATE_IS_NOT_SOLVEABLE;
    }

    state_stacks_num = instance->stacks_num;

    for( stack=0 ; stack < state_stacks_num ; stack++)
    {
        cards_num = fcs_stack_len(state, stack);
        for( c=cards_num-1 ; c >= 1 ; c--)
        {
            card = fcs_stack_card(state, stack, c);
            if (fcs_card_get_flipped(card))
            {
                break;
            }
            if (fcs_card_card_num(card) == 13)
            {
                /* It's a King - so let's move it */
                sfs_check_state_begin();


                for( ds=0 ; ds < state_stacks_num ; ds++)
                {
                    if (fcs_stack_len(state, ds) == 0)
                    {
                        break;
                    }
                }
                my_copy_stack(stack);
                my_copy_stack(ds);
                fcs_move_sequence(ds, stack, c, cards_num-1, a);


                fcs_flip_top_card(stack);

                sfs_check_state_end();
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}



#ifdef FCS_WITH_TALONS
/*
    Let's try to deal the Gypsy-type Talon.

  */
int freecell_solver_sfs_deal_gypsy_talon(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();

    int check;

    fcs_card_t temp_card;
    int a;

    fcs_move_t temp_move;

    tests_define_accessors();

    if (instance->talon_type != FCS_TALON_GYPSY)
    {
        return FCS_STATE_IS_NOT_SOLVEABLE;
    }

    moves = hard_thread->reusable_move_stack;
    indirect_stacks_buffer = hard_thread->indirect_stacks_buffer;

    if (fcs_talon_pos(state) < fcs_talon_len(state))
    {
        sfs_check_state_begin()
        for(a=0;a<state_stacks_num;a++)
        {
            temp_card = fcs_get_talon_card(new_state, fcs_talon_pos(new_state)+a);
            fcs_push_card_into_stack(new_state,a,temp_card);
        }
        fcs_talon_pos(new_state) += state_stacks_num;
        fcs_move_set_type(temp_move, FCS_MOVE_TYPE_DEAL_GYPSY_TALON);
        fcs_move_stack_push(moves, temp_move);

        sfs_check_state_end()
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}


int freecell_solver_sfs_get_card_from_klondike_talon(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();


    fcs_state_with_locations_t * talon_temp;

    fcs_move_t temp_move;

    int check;
    int num_redeals_left, num_redeals_done, num_cards_moved[2];
    int first_iter;
    fcs_card_t card_to_check, top_card;
    int s;
    int cards_num;
    int a;

    tests_define_accessors();

    if (instance->talon_type != FCS_TALON_KLONDIKE)
    {
        return FCS_STATE_IS_NOT_SOLVEABLE;
    }

    /* Duplicate the talon and its parameters into talon_temp */
    talon_temp = malloc(sizeof(fcs_state_with_locations_t));
    talon_temp->s.talon = malloc(fcs_klondike_talon_len(state)+1);
    memcpy(
        talon_temp->s.talon,
        ptr_state_with_locations->s.talon,
        fcs_klondike_talon_len(state)+1
        );
    memcpy(
        talon_temp->s.talon_params,
        ptr_state_with_locations->s.talon_params,
        sizeof(ptr_state_with_locations->s.talon_params)
        );

    /* Make sure we redeal the talon only once */
    num_redeals_left = fcs_klondike_talon_num_redeals_left(state);
    if ((num_redeals_left > 0) || (num_redeals_left < 0))
    {
        num_redeals_left = 1;
    }
    num_redeals_done = 0;
    num_cards_moved[0] = 0;
    num_cards_moved[1] = 0;

    first_iter = 1;
    while (num_redeals_left >= 0)
    {
        if ((fcs_klondike_talon_stack_pos(talon_temp->s) == -1) &&
            (fcs_klondike_talon_queue_pos(talon_temp->s) == fcs_klondike_talon_len(talon_temp->s)))
        {
            break;
        }
        if ((!first_iter) || (fcs_klondike_talon_stack_pos(talon_temp->s) == -1))
        {
            if (fcs_klondike_talon_queue_pos(talon_temp->s) == fcs_klondike_talon_len(talon_temp->s))
            {
                if (num_redeals_left > 0)
                {
                    fcs_klondike_talon_len(talon_temp->s) = fcs_klondike_talon_stack_pos(talon_temp->s);
                    fcs_klondike_talon_redeal_bare(talon_temp->s);

                    num_redeals_left--;
                    num_redeals_done++;
                }
                else
                {
                    break;
                }
            }
            fcs_klondike_talon_queue_to_stack(talon_temp->s);
            num_cards_moved[num_redeals_done]++;
        }
        first_iter = 0;

        card_to_check = fcs_klondike_talon_get_top_card(talon_temp->s);
        for(s=0 ; s<state_stacks_num ; s++)
        {
            cards_num = fcs_stack_len(state,s);
            top_card = fcs_stack_card(state,s,cards_num-1);
            if (fcs_is_parent_card(card_to_check, top_card))
            {
                /* We have a card in the talon that we can move
                to the stack, so let's move it */
                sfs_check_state_begin()

                new_state.talon = malloc(fcs_klondike_talon_len(talon_temp->s)+1);
                memcpy(
                    new_state.talon,
                    talon_temp->s.talon,
                    fcs_klondike_talon_len(talon_temp->s)+1
                    );

                memcpy(
                    ptr_new_state_with_locations->s.talon_params,
                    talon_temp->s.talon_params,
                    sizeof(ptr_state_with_locations->s.talon_params)
                );

                for(a=0;a<=num_redeals_done;a++)
                {
                    fcs_move_set_type(temp_move, FCS_MOVE_TYPE_KLONDIKE_FLIP_TALON);
                    fcs_move_set_num_cards_flipped(temp_move, num_cards_moved[a]);
                    fcs_move_stack_push(moves, temp_move);
                    if (a != num_redeals_done)
                    {
                        fcs_move_set_type(temp_move, FCS_MOVE_TYPE_KLONDIKE_REDEAL_TALON);
                        fcs_move_stack_push(moves,temp_move);
                    }
                }
                fcs_push_card_into_stack(new_state, s, fcs_klondike_talon_get_top_card(new_state));
                fcs_move_set_type(temp_move, FCS_MOVE_TYPE_KLONDIKE_TALON_TO_STACK);
                fcs_move_set_dest_stack(temp_move, s);
                fcs_klondike_talon_decrement_stack(new_state);

                sfs_check_state_end()
            }
        }
    }



#if 0
 cleanup:
#endif
    free(talon_temp->s.talon);
    free(talon_temp);

    return FCS_STATE_IS_NOT_SOLVEABLE;

}
       
#endif

int freecell_solver_sfs_atomic_move_card_to_empty_stack(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();
    int empty_stacks_filled_by, state_stacks_num;
    int stack, cards_num;
    fcs_card_t card, temp_card;
    fcs_move_t temp_move;
    int check;
    int empty_stack_idx;

    tests_define_accessors();

    if (num_freestacks == 0)
    {
        return FCS_STATE_IS_NOT_SOLVEABLE;
    }

    state_stacks_num = instance->stacks_num;

    for(empty_stack_idx=0;empty_stack_idx<state_stacks_num;empty_stack_idx++)
    {
        if (fcs_stack_len(state, empty_stack_idx) == 0)
        {
            break;
        }
    }

    empty_stacks_filled_by = instance->empty_stacks_fill;

    if (empty_stacks_filled_by == FCS_ES_FILLED_BY_NONE)
    {
        return FCS_STATE_IS_NOT_SOLVEABLE;
    }

    

    for(stack=0;stack<state_stacks_num;stack++)
    {
        cards_num = fcs_stack_len(state, stack);
        if (cards_num > 0)
        {
            card = fcs_stack_card(state, stack, cards_num-1);
            if ((empty_stacks_filled_by == FCS_ES_FILLED_BY_KINGS_ONLY) &&
                (fcs_card_card_num(card) != 13))
            {
                continue;
            }
            /* Let's move it */
            {
                sfs_check_state_begin();

                my_copy_stack(stack);

                fcs_pop_stack_card(new_state, stack, temp_card);
                

                my_copy_stack(empty_stack_idx);

                fcs_push_card_into_stack(new_state, empty_stack_idx, card);

                fcs_move_set_type(temp_move, FCS_MOVE_TYPE_STACK_TO_STACK);
                fcs_move_set_src_stack(temp_move, stack);
                fcs_move_set_dest_stack(temp_move, empty_stack_idx);
                fcs_move_set_num_cards_in_seq(temp_move, 1);

                fcs_move_stack_push(moves, temp_move);

                fcs_move_set_type(temp_move,FCS_MOVE_TYPE_CANONIZE);
                fcs_move_stack_push(moves, temp_move);
                
                sfs_check_state_end()                
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}

int freecell_solver_sfs_atomic_move_card_to_parent(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();
    int state_stacks_num;
    int stack, cards_num, ds, ds_cards_num;
    fcs_card_t card, dest_card, temp_card;
    fcs_move_t temp_move;
    int check;
    int sequences_are_built_by;

    tests_define_accessors();

    state_stacks_num = instance->stacks_num;

    sequences_are_built_by = instance->sequences_are_built_by;
    

    for(stack=0;stack<state_stacks_num;stack++)
    {
        cards_num = fcs_stack_len(state, stack);
        if (cards_num > 0)
        {
            card = fcs_stack_card(state, stack, cards_num-1);
            
            for(ds=0;ds<state_stacks_num;ds++)
            {
                if (ds == stack)
                {
                    continue;
                }

                ds_cards_num = fcs_stack_len(state, ds);
                if (ds_cards_num > 0)
                {
                    dest_card = fcs_stack_card(state, ds, ds_cards_num-1);
                    if (fcs_is_parent_card(card, dest_card))
                    {
                        /* Let's move it */
                        {
                            sfs_check_state_begin();

                            my_copy_stack(stack);
                            my_copy_stack(ds);

                            fcs_pop_stack_card(new_state, stack, temp_card);
                            
                            fcs_push_card_into_stack(new_state, ds, card);

                            fcs_move_set_type(temp_move, FCS_MOVE_TYPE_STACK_TO_STACK);
                            fcs_move_set_src_stack(temp_move, stack);
                            fcs_move_set_dest_stack(temp_move, ds);
                            fcs_move_set_num_cards_in_seq(temp_move, 1);

                            fcs_move_stack_push(moves, temp_move);

                            fcs_move_set_type(temp_move,FCS_MOVE_TYPE_CANONIZE);
                            fcs_move_stack_push(moves, temp_move);
                            
                            sfs_check_state_end()                
                        }
                    }
                }
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}

int freecell_solver_sfs_atomic_move_card_to_freecell(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();
    int state_stacks_num;
    int state_freecells_num;
    int stack, cards_num, ds;
    fcs_card_t card, temp_card;
    fcs_move_t temp_move;
    int check;
    int sequences_are_built_by;

    tests_define_accessors();

    state_stacks_num = instance->stacks_num;
    state_freecells_num = instance->freecells_num;

    sequences_are_built_by = instance->sequences_are_built_by;

    if (num_freecells == 0)
    {
        return FCS_STATE_IS_NOT_SOLVEABLE;
    }

    for(ds=0;ds<state_freecells_num;ds++)
    {
        if (fcs_freecell_card_num(state, ds) == 0)
        {
            break;
        }
    }
    
    

    for(stack=0;stack<state_stacks_num;stack++)
    {
        cards_num = fcs_stack_len(state, stack);
        if (cards_num > 0)
        {
            card = fcs_stack_card(state, stack, cards_num-1);

            /* Let's move it */
            {
                sfs_check_state_begin();

                my_copy_stack(stack);

                fcs_pop_stack_card(new_state, stack, temp_card);
                
                fcs_put_card_in_freecell(new_state, ds, card);

		fcs_move_init(temp_move);
                fcs_move_set_type(temp_move, FCS_MOVE_TYPE_STACK_TO_FREECELL);
                fcs_move_set_src_stack(temp_move, stack);
                fcs_move_set_dest_freecell(temp_move, ds);

                fcs_move_stack_push(moves, temp_move);

                fcs_move_set_type(temp_move,FCS_MOVE_TYPE_CANONIZE);
                fcs_move_stack_push(moves, temp_move);
                
                sfs_check_state_end()                
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}

int freecell_solver_sfs_atomic_move_freecell_card_to_parent(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();
    int state_stacks_num, state_freecells_num;
    int fc, ds, ds_cards_num;
    fcs_card_t card, dest_card;
    fcs_move_t temp_move;
    int check;
    int sequences_are_built_by;

    tests_define_accessors();

    state_stacks_num = instance->stacks_num;
    state_freecells_num = instance->freecells_num;

    sequences_are_built_by = instance->sequences_are_built_by;

    
    

    for(fc=0;fc<state_freecells_num;fc++)
    {
        card = fcs_freecell_card(state, fc);
        if (fcs_card_card_num(card) == 0)
        {
            continue;
        }
        
        for(ds=0;ds<state_stacks_num;ds++)
        {
            ds_cards_num = fcs_stack_len(state, ds);
            if (ds_cards_num > 0)
            {
                dest_card = fcs_stack_card(state, ds, ds_cards_num-1);
                if (fcs_is_parent_card(card, dest_card))
                {
                    /* Let's move it */
                    {
                        sfs_check_state_begin();

                        my_copy_stack(ds);

                        fcs_empty_freecell(new_state, fc);
                        
                        fcs_push_card_into_stack(new_state, ds, card);

                        fcs_move_set_type(temp_move, FCS_MOVE_TYPE_FREECELL_TO_STACK);
                        fcs_move_set_src_freecell(temp_move, fc);
                        fcs_move_set_dest_stack(temp_move, ds);
                        fcs_move_set_num_cards_in_seq(temp_move, 1);

                        fcs_move_stack_push(moves, temp_move);

                        fcs_move_set_type(temp_move,FCS_MOVE_TYPE_CANONIZE);
                        fcs_move_stack_push(moves, temp_move);
                        
                        sfs_check_state_end()                
                    }
                }
            }
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}

int freecell_solver_sfs_atomic_move_freecell_card_to_empty_stack(
        freecell_solver_soft_thread_t * soft_thread,
        fcs_state_with_locations_t * ptr_state_with_locations,
        int num_freestacks,
        int num_freecells,
        fcs_derived_states_list_t * derived_states_list,
        int reparent
        )
{
    tests_declare_accessors();
    int state_stacks_num, state_freecells_num;
    int fc, ds;
    fcs_card_t card;
    fcs_move_t temp_move;
    int check;
    int sequences_are_built_by, empty_stacks_filled_by;

    tests_define_accessors();

    moves = hard_thread->reusable_move_stack;
    indirect_stacks_buffer = hard_thread->indirect_stacks_buffer;

    state_stacks_num = instance->stacks_num;
    state_freecells_num = instance->freecells_num;

    sequences_are_built_by = instance->sequences_are_built_by;

    if (num_freestacks == 0)
    {
        return FCS_STATE_IS_NOT_SOLVEABLE;
    }

    empty_stacks_filled_by = instance->empty_stacks_fill;

    if (empty_stacks_filled_by == FCS_ES_FILLED_BY_NONE)
    {
        return FCS_STATE_IS_NOT_SOLVEABLE;
    }
    
    for(ds=0;ds<state_stacks_num;ds++)
    {
        if (fcs_stack_len(state, ds) == 0)
        {
            break;
        }
    }

    for(fc=0;fc<state_freecells_num;fc++)
    {
        card = fcs_freecell_card(state, fc);
        if (fcs_card_card_num(card) == 0)
        {
            continue;
        }

        if ((empty_stacks_filled_by == FCS_ES_FILLED_BY_KINGS_ONLY) &&
            (fcs_card_card_num(card) != 13))
        {
            continue;
        }        

        {
            sfs_check_state_begin();

            my_copy_stack(ds);

            fcs_empty_freecell(new_state, fc);
            
            fcs_push_card_into_stack(new_state, ds, card);

            fcs_move_set_type(temp_move, FCS_MOVE_TYPE_FREECELL_TO_STACK);
            fcs_move_set_src_freecell(temp_move, fc);
            fcs_move_set_dest_stack(temp_move, ds);
            fcs_move_set_num_cards_in_seq(temp_move, 1);

            fcs_move_stack_push(moves, temp_move);

            fcs_move_set_type(temp_move,FCS_MOVE_TYPE_CANONIZE);
            fcs_move_stack_push(moves, temp_move);
            
            sfs_check_state_end()                
        }
    }

    return FCS_STATE_IS_NOT_SOLVEABLE;
}


#undef state_with_locations
#undef state
#undef new_state_with_locations
#undef new_state


freecell_solver_solve_for_state_test_t freecell_solver_sfs_tests[FCS_TESTS_NUM] =
{
    freecell_solver_sfs_move_top_stack_cards_to_founds,
    freecell_solver_sfs_move_freecell_cards_to_founds,
    freecell_solver_sfs_move_freecell_cards_on_top_of_stacks,
    freecell_solver_sfs_move_non_top_stack_cards_to_founds,
    freecell_solver_sfs_move_stack_cards_to_different_stacks,
    freecell_solver_sfs_move_stack_cards_to_a_parent_on_the_same_stack,
    freecell_solver_sfs_move_sequences_to_free_stacks,
    freecell_solver_sfs_move_freecell_cards_to_empty_stack,
    freecell_solver_sfs_move_cards_to_a_different_parent,
    freecell_solver_sfs_empty_stack_into_freecells,
    freecell_solver_sfs_simple_simon_move_sequence_to_founds,
    freecell_solver_sfs_simple_simon_move_sequence_to_true_parent,
    freecell_solver_sfs_simple_simon_move_whole_stack_sequence_to_false_parent,
    freecell_solver_sfs_simple_simon_move_sequence_to_true_parent_with_some_cards_above,
    freecell_solver_sfs_simple_simon_move_sequence_with_some_cards_above_to_true_parent,
    freecell_solver_sfs_simple_simon_move_sequence_with_junk_seq_above_to_true_parent_with_some_cards_above,
    freecell_solver_sfs_simple_simon_move_whole_stack_sequence_to_false_parent_with_some_cards_above,
    freecell_solver_sfs_simple_simon_move_sequence_to_parent_on_the_same_stack,
    freecell_solver_sfs_atomic_move_card_to_empty_stack,
    freecell_solver_sfs_atomic_move_card_to_parent,
    freecell_solver_sfs_atomic_move_card_to_freecell,
    freecell_solver_sfs_atomic_move_freecell_card_to_parent,
    freecell_solver_sfs_atomic_move_freecell_card_to_empty_stack,
#if 0
    freecell_solver_sfs_move_top_stack_cards_to_founds,
    freecell_solver_sfs_yukon_move_card_to_parent,
    freecell_solver_sfs_yukon_move_kings_to_empty_stack,
    freecell_solver_sfs_yukon_do_nothing,
    freecell_solver_sfs_yukon_do_nothing,
#endif
    freecell_solver_sfs_yukon_do_nothing,
    freecell_solver_sfs_yukon_do_nothing
#ifdef FCS_WITH_TALONS
        ,
    freecell_solver_sfs_deal_gypsy_talon,
    freecell_solver_sfs_get_card_from_klondike_talon
#endif
};