数织游戏求解⼯具设计及相关算法研究（C#实现）
⼀、数织游戏简介
1，数织游戏的每⾏每列都有提⽰信息，数字代表有多少个连续的⿊格
2，两个数字之间的⿊格不连续，即中间必须有叉叉隔开
3，数织游戏的解可能不唯⼀，满⾜所有的⾏列条件即可
⼆、求解程序
1，程序整体设计
程序分为交互界⾯和求解程序两部分，求解程序使⽤新的线程求解，避免交互界⾯卡死。
本⽂主要介绍求解程序的设计，基于C#的交互界⾯不做过多赘述
2，程序算法概述
这个问题很像N皇后问题，当⾏列限制条件全部为1时，将变成不考虑对⾓线的N皇后问题，所以基础算法就是深度优先搜索。在算法上，本⽂将讨论以下四个问题：
（1）解决单个⾏列求解问题，⽐较递归法和动态规划算法
（2）解决数织的整体求解问题，利⽤单⾏的解，在列⽅向上进⾏深度优先搜索
（3）在复杂问题上（搜索树超过10^25时）的推导算法
（4）探讨推导算法的优化可能
三，数据结构和⾏列条件读⼊问题
1，交互窗⼝简介
Form_Main类是设计的窗⼝，具体造型如图所⽰，不做过多介绍
主要的功能就是将⾏列限制条件输⼊，然后点击计算结果进⾏计算。有多个解时，可以点击按钮切换。
注：在本程序中，需要上⾊的格⼦⽤1表⽰，叉叉⽤0表⽰。
2，求解类数据结构
private Form_Main main_Form;
private int[][] definiteGird;          //100%确定结果的格⼦
private int[][] dfsGird;                //深度优先遍历所有单⾏的解
private List<int[][]> puzzleResult;    //最终的解集
private int resultIndex;
//地图信息
public int Row, Col;                    //地图⾏列
public List<List<int>> RowLimit;        //⾏限制
public List<List<int>> ColLimit;        //列限制
//解谜信息
private Thread thread = null;
private List<LinkedList<int[]>> EveryRowAllSolve;        //每⾏：只考虑单⾏限制的所有解
private List<LinkedList<int[]>> EveryColAllSolve;        //每列：只考虑单列限制的所有解
⾸先，需要两个⼆维数组，⼀个存储已经确定答案的格⼦，另⼀个⽤于深度优先搜索。
每搜索到⼀个解，都存⼊puzzleResult中。
在地图信息⽅⾯，⾏列限制将会原封不动地读⼊RowLimit和ColLimit。由于单个⾏列的所有解不需要以下标访问，只需要增删和遍历，所以使⽤链表EveryRowAllSolve和EveryColAllSolve保存，便于增删操作。
3，⾏列限制的读⼊
private void button_TryDo_Click(object sender, EventArgs e)
{
//解析⾏列条件
var rowLimit = ReadLimitData(textBox_Row.Text);
var colLimit = ReadLimitData(textBox_Col.Text);
nonoPuzzle?.StopAnalyze();                          //杀死原线程
nonoPuzzle = new NonoPuzzle(rowLimit, colLimit);
//求解
nonoPuzzle.TryDoPuzzle(this);
}
private List<List<int>> ReadLimitData(string data)
{
List<List<int>> limit = new List<List<int>>();
string[] LimitR = data.Split("\r\n");
LimitR = LimitR.Where(s => !string.IsNullOrEmpty(s)).ToArray();
for (int i = 0; i < LimitR.Length; i++)
{
string[] LimitS = LimitR[i].Split("");
List<int> singleLimit = new List<int>();
for (int j = 0; j < LimitS.Length; j++)
{
singleLimit.Add(int.Parse(LimitS[j]));
}
limit.Add(singleLimit);
}
return limit;
}
C#窗⼝的字符串换⾏有⼀个\r，所以是以\r\n分割字符串。⽂本或控制台读⼊的字符串直接\n即可。
每⼀⾏（列）的条件最终都是List<int>，将字符串整体转化成列表List<List<int>>后，再由构造函数传⼊解谜类NonoPuzzle：public NonoPuzzle(List<List<int>> rowLimit, List<List<int>> colLimit)
{
RowLimit = rowLimit;
ColLimit = colLimit;
Row = RowLimit.Count;
Col = ColLimit.Count;
}
///<summary>
///停⽌当前计算
///</summary>
public void StopAnalyze()
{
if (thread != null && thread.IsAlive)
{
thread.IsBackground = true;
thread.Interrupt();
}
}
多说⼀句杀死线程的问题，这⾥使⽤的是 core3.1，并不⽀持Abort，所以只能把原线程扔到后台，让系统⾃⾏回收。
4，结果的输出
计算完成后，默认输出第⼀个解，剩下的需要⼿动切换。
public string PrintResult(int index)
{
if (index < 0 || index >= puzzleResult.Count)
return"";
string res = "";
for (int i = 0; i < Row; i++)
{
for (int j = 0; j < Col; j++)
{
res += puzzleResult[index][i][j];
if (j != Col - 1)
res += "";
}
if (i != Row - 1)
res += "\r\n";
}
return res;
}
public string PrintNextResult()
{
if (resultIndex < puzzleResult.Count - 1)
resultIndex++;
return PrintResult(resultIndex);
}
public string PrintPreResult()
{
if (resultIndex > 0)
resultIndex--;
return PrintResult(resultIndex);
}
四，数据初筛
本步骤的作⽤有两点：
1：限制数据长度初步判定：每⾏每列要能放得下这么多1
2：先根据限制中较⼤的数字，填⼊确定格
public void TryDoPuzzle(Form_Main main_Form)
{
this.main_Form = main_Form;
this.main_Form.ClearConsole();
bool preProceSuccess = PreProcessPuzzle();        //数据初筛
if(preProceSuccess)
{
//TrySavePuzzle();
thread = new Thread(TrySavePuzzle);          //开新线程解谜，防⽌阻塞窗⼝显⽰
thread.Start();
}
}
这⾥由Form_Main主窗⼝进⾏调⽤（不记得的向上翻⾏列限制读⼊那块），所有带“Console”的都是主界⾯的输出，本⽂不再详细介绍。
当数据通过初筛后，才开启新线程进⾏计算（计算时间可能较长，单线程的话，窗⼝会卡死闪退）
那么如何填⼊初始的确定格呢？我们不妨来看五种情况：
（1）15*15的地图，⾏限制是0或15，那么就是全0/全1
（2）15*15的地图，⾏限制是13，那么它就是??111  11111  111??，中间的1是可以确定的格⼦，⽽两头的?是不能确定的格⼦。倘若中间没有这么长，就凑不够13个连续的格⼦了。
（3）还是15*15的地图，⾏限制是6 5，那么它就是11  1?  11。⽅法如下：
先把6填在最左边(⽤x表⽰)，假设是xxxxx  x0???  ?????，有⼀个0是因为6和5中间必须⾄少空⼀格。那么就是剩下8个?中要填⼊⼀个5，即为11，中间两个必为1
所以得到了xxxxx  x0 11，然后再假设最右边5个，求左边的6，⽅法相同
（4）还是15*15的地图，⾏限制是4 4 3，那么它是??11?  ??11?  ??1??
⽅法和上⾯类似，⽐如求中间这个4，先把其余数字的4 3紧密排好，就是xxxx0 ?????  ?0xxx。然后在剩下6个?中要填⼊⼀个4，即为?? 11??
左边的4和右边的3⽅法类似，也是先把剩下的紧密排好，在剩余的?中填⼊数字。
（5）15*15的地图，⾏限制是2 2 1，⽆法确定任何格⼦
总结：对于任意数字，可以将其他数字先在两边顶死，中间空出剩余⽅格，转化为（2）的情况。若剩余⽅格<2*当前数字，则能确定部分格⼦
其中，少的部分即为确定的格⼦数量，例如在6个?中填⼊4，确定格⼦数量=2*4-6=2
依据上述逻辑，我们假设有a b c d这样的限制条件，其中b最⼤，那么就先看b是否可以确定格⼦。先算出⼀共⾄少需要M=a+1+b+1+c+1+d个格⼦
从最⼤的数字开始看，填充格⼦数量=2*b-剩余格⼦=2*b-（总长度-（M-b））=b-总长度+M
如果b满⾜条件，则继续看第⼆⼤的数字。
///<summary>
///重置确定格⼦
///</summary>
private void ResetDefiniteGird()
{
definiteGird = new int[Row][];
for (int i = 0; i < Row; i++)
{
definiteGird[i] = new int[Col];
for (int j = 0; j < Col; j++)
{
definiteGird[i][j] = -1;            //-1代表不能确定的格⼦
}
}
}
///<summary>
///数据初筛///</summary>
private bool PreProcessPuzzle()
{
ResetDefiniteGird();            //初始化固定格
for (int i = 0; i < Row; i++)
{
int minGird = -1;      //最⼩长度第⼀组连续1左边不需要格⼦
int maxNum = -1;        //最⼤数
int maxindex = -1;
for (int j = 0; j < RowLimit[i].Count; j++)
{
minGird += RowLimit[i][j];
minGird++;
if(RowLimit[i][j]>maxNum)
{
maxNum = RowLimit[i][j];
maxindex = j;
}
}
//长度检验，避免下⼀步陷⼊死循环
if (minGird > Col)
{
this.main_Form.SetConsole("初筛错误：第" + i + "⾏数据溢出，请检查条件是否过⼤");
return false;
}
//填⼊确定格
if(maxNum==0)
{
for (int j = 0; j < Col; j++)
{
definiteGird[i][j] = 0;        //填⼊⼀⾏0
}
}
else
{
int canDefiniteGirdNum = maxNum - Col + minGird;
//数字⾜够⼤，可以确定某些格⼦
//例如7,2填⼊12个格⼦，14>12-10+7=9，且14-9=5，则可以填⼊7之前五个格⼦3-7
List<int> doneIndex = new List<int>();          //从⼤到⼩依次处理
while (canDefiniteGirdNum > 0)
{
int tail = -2;      //第⼀组1左边没格⼦，还要去掉后⾯空0的格⼦，所以-2
//计算到可填充末尾格
for (int j = 0; j <= maxindex; j++)
{
tail += RowLimit[i][j];
tail++;
}
//向前填充确定格
for (int j = 0; j < canDefiniteGirdNum; j++)
{
int dfIndex = tail - j;
printformif (dfIndex >= 0 && dfIndex < Col)
{
definiteGird[i][dfIndex] = 1;
}
else
{
this.main_Form.SetConsole("初筛错误：第" + i + "⾏填⼊固定格错误");
return false;
}
}
//看看是否还存在其他确定格
doneIndex.Add(maxindex);
maxNum = -1;        //寻下⼀个最⼤数
maxindex = -1;
for (int j = 0; j < RowLimit[i].Count; j++)
{
if (RowLimit[i][j] > maxNum && !doneIndex.Contains(j))
{
maxNum = RowLimit[i][j];
maxindex = j;
}
canDefiniteGirdNum = maxNum - Col + minGird;
}
}
}
}
for (int j = 0; j < Col; j++)
{
int minGird = -1;      //最⼩长度第⼀组连续1上边不需要格⼦
int maxNum = -1;        //最⼤数
int maxindex = -1;
for (int i = 0; i < ColLimit[j].Count; i++)
{
minGird += ColLimit[j][i];
minGird++;
if (ColLimit[j][i] > maxNum)
{
maxNum = ColLimit[j][i];
maxindex = i;
}
}
if (minGird > Row)
{
this.main_Form.SetConsole("初筛错误：第" + j + "列数据溢出，请检查条件是否过⼤");
return false;
}
//填⼊确定格
if (maxNum == 0)
{
for (int i = 0; i < Row; i++)
{
definiteGird[i][j] = 0;        //填⼊⼀列0
}
}
else
{
int canDefiniteGirdNum = maxNum - Row + minGird;
//数字⾜够⼤，可以确定某些格⼦
//例如7,2填⼊12个格⼦，14>12-10+7=9，且14-9=5，则可以填⼊7之前五个格⼦3-7
List<int> doneIndex = new List<int>();          //从⼤到⼩依次处理
while (canDefiniteGirdNum > 0)
{
int tail = -2;      //第⼀组1上边没格⼦，还要去掉后⾯空0的格⼦，所以-2
/
/计算到可填充末尾格
for (int i = 0; i <= maxindex; i++)
{
tail += ColLimit[j][i];
tail++;
}
//向上填充确定格
for (int i = 0; i < canDefiniteGirdNum; i++)
{
int dfIndex = tail - i;
if (dfIndex >= 0 && dfIndex < Row)
{
definiteGird[dfIndex][j] = 1;
}
else
{
this.main_Form.SetConsole("初筛错误：第" + j + "列填⼊固定格错误");
return false;
}
}
//看看是否还存在其他确定格
doneIndex.Add(maxindex);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。