project name: solvecf
solve Coinflip game's levels

翻金币游戏关卡求解

1. 从 coinfilp 游戏项目拷出的文件
Levels.lua      关卡配置
functions.lua   辅助实用函数

2. 标准配置关卡与数学基础
stdLevel.lua

转为方便数学分析的关卡配置
棋盘布局矩阵中，正面朝上的1表示，反面朝上的-1表示，空洞用0表示
翻转操作则用一个同维矩阵表示，要翻转处用-1表示，其余用1表示
如此，翻转结果是两个矩阵的数组乘法结果

常规十字形操作矩阵类似如下：
[1  1  1  1  1；
 1  1 -1  1  1；
 1 -1 -1 -1  1；
 1  1 -1  1  1；
 1  1  1  1  1]

如果触点在角落上，当然就没有5个-1了。

这个的矩阵数组乘法满足可逆与交换律
即如果点击不同两处翻转，与顺序无关，均得到相同结果
如果在同一处点击两次翻转，则结果返回原来的布局

3. 实现处理类
ChessBorad.lua

算法思路：
1) 最开始的思路
将棋盘布局想象为二进制状态，转为一个整数表示布局
从最终结果（全正面朝上）当作根结点，开始向下搜索
扩展子结点，另用一个 hash 表保存已达到过的结点，避免添加重复的结点（局面）
搜索到关卡局面后，由父指针回溯，得到路径
路径用点击位置表示，扩展树过程中也将点坐标转为单索引坐标

主要方法包括：
整数 <--> 矩阵布局转换
位置 <--> 单索引转换
翻转即矩阵数组乘法
扩展树

这个算法的主要问题是要保存中间状态，在棋盘增大时，可能保存相当大的结点状态
最坏情况是 2^N (N=row*col) 种状态
在 5*5 棋盘中，用 lua 解释器就报告内存不足错误

2) 改进算法
不保存中间状态
而是生成组合状态
假设1层（1步），有 C(N,1) = N 种不同操作，2步有 C(N,2) 种操作……
直到N步，只有一种操作，即每个位置都翻一下
超过N步无意义，因为翻转可逆
将每种操作组合模拟翻转一遍，测试是否达到目标结果

这种思路没有保存棋盘的中间结点状态，不过在计算多步操作时，可能重复计算了一些翻
转操作，典型的时间换空间

不过在生成组合列表时，仍然出现内存不足的错误
比如5*5棋盘时，将 C(25,11) 种组合情况先保存在一个列表中，就有问题

3) 用迭代器一个个产出组合情况
后来想到没必要先将所有组合状态计算出来，保存在一个列表中
而用迭代器，一个个取出，按此组合模拟翻转，即可完成工作
一些关卡需要计算半小时到一个小时左右，但总算可工作了


4. 计算结果保存
由 solveLevels.lua 驱动，结果保存于 solved.lua 中
每关的结果是形如 {row=y, col=x} 的点坐标列表，表示点击翻顺序
发现三个无解的关卡：{70 82 87}

因而重新设计这三关的布局，使之可解

5. 难度分析 hardanaly.lua
将求解组合数（对数熵）作为难度指数
获取所有关卡的基本信息，计算难度指数，保存结果数据于 csv（文本格式）
csv 可用 Excel 打开，或导出 .xlsx 作进一步分析

6. 总结
以后或可重用的实用函数工具：

计算组合数：combine.lua
罗列组合状态的迭代器：combit.lua
将 lua table 数据导出为 Excel 可读的 csv 格式：（参考 hardanaly.lua ）
将数组随机乱序：（参考 solved.lua ）