研究扫雷和空当接龙 freecell

(资料图片)

搜到几个代码, 总是没有源代码, 不爽

就写了个

本来用a* 算法, 好像出不来

然后使用深度优先, 有些可以快速得到结果.

最大移动张数计算方式：（可用单元+1）×（闲置列+1）

代码放到

https://bird-self-lib.googlecode.com/svn/branches/FreeCellCalculate

下载应该不需要权限

一张牌

Card

内部2种表达方式

1. 从0-52的序列, 把4套牌都排序了. 梅花的0-12, 方块的...这个占字节少,快速.

2. 用type和number,  花色是type, 1-10,jqk 这些是number, 这个方便调试.

class CCard    {        #if CARD_1_BYTE        UINT8       m_num;#else        eType       m_type;        eNumber     m_number;  //0-9(1-10), 11- J, 11- Q, 12- K#endif    };

一个状态 叫一个State, 如图

左上角是bench, 右上角是拍好序的sorted

下面就是牌. 每竖是一个list

每竖行是一个column,

class CState{public:        UINT                    m_id;    UINT                    m_idxFather;    bool                    m_hasGenSon;    ListInt                 m_idxSon;    UINT16                  m_value;    UINT8                   m_step;    UINT                    m_hash;    //std::string             m_str;    VecCard                 m_vecIdxSorted;   //4 vec, save show card    VecCard                 m_vecBench;       //4 card     typedef std::vectorVecListCard;    VecListCardm_vecVecIdx;};

算法,深度优先

从开局的state开始

生成他的所有子步骤, 每个都是一个son state

每个都算出一个value

然后把最低value的当作当前节点,

再次遍历

找到完成的状态.

如果找不到就依次退回到父节点.