媳妇给娃买的玩具（个人觉得商标不算广告，如需打码，我再改），媳妇不会玩，我就想写段代码辅助一下。
​一开始我觉得这代码很简单呀，递归一下，算就完了，花了半天撸出一版代码，跑起来发现是我肤浅了，代码跑完怕是得以年计，那我要他做甚，陪我女儿慢慢长大吗。于是怒改代码，少许剪枝后，3*5的格子一分钟就算出一组解。我想了想，要他做甚，和我比赛谁拼的快吗。于是大改代码，先列出所有组合，对每种组合计算，这样必要时可以开线程。结果单线程时3*5用时1秒不到得28组解（多为镜像），4*5用时2秒多得193解（这个有点奇怪），5*5用时近一分钟得796解，6*5用时近21分钟得1985解，所以很显然，这算法还是失败的。
​由于我基础确实很差，大学好像是学过算法课，但早忘光了，重新学习进度极为缓慢，在此恳请大佬指导下复杂度较低的算法，最好能在1小时内遍历完12*5的所有解。如有大佬指导，不胜感激。
我的主要思路：
1.用二维数组表示积木方块，类似int[2, 4] {
{3,3,3,3 },
{0,0,3,0 } };
2.旋转或翻转后重复（对称）的方块提前建立数组，记录需要翻转或旋转的次数；
3.棋盘为二维数组，放置积木是将积木数组与棋盘数组相加，放完会判断下重叠，即积木数组区域是否出现大于积木数值的值
[C#] 纯文本查看 复制代码 private int[,] Addarray(int[,] nx, int[,] na, int r, int c,int nn,ref bool ol)
{
int[,] temp = new int[nx.GetLength(0), nx.GetLength(1)];
Array.Copy(nx,temp, nx.Length);
checked
{
try
{
for (int i = r; i < (na.GetLength(0) + r); i++)
{
for (int j = c; j < (na.GetLength(1) + c); j++)
{
temp[i, j] += na[i - r, j - c];
if (temp[i, j] > (nn + 1))//检查是否重叠
{
ol = true;
return nx;
}
}
}
ol = false;
return temp;
}
catch (Exception e)
{
textBox1.Text += "故障：" + e + "\n\r";
ol = true;
return nx;
}
}
}
4. 3-11块的需生成所有积木组合
[C#] 纯文本查看 复制代码 private void generateTask(int n)//遍历积木组合
{
prog_task.Clear();
int[] set= new int[n];
for (int i = 0; i < n; i++) set[i] = i;//初始化，第一个集合
prog_task.Add(set.ToArray());
if (n < 12)
{
int position = n - 1;
while (true)
{
if (set[n - 1] == 11) position--;//最右数到上限，指针左移一位
else position = n - 1;//否则指针至最右
set[position]++;
// 调整右边元素
for (int i = position + 1; i < n; i++)
set[i] = set[i - 1] + 1;
prog_task.Add(set.ToArray());
if (set[0] >= (12 - n))
break;
}
}
}
5.求解过程用递归，必须积木全部放完，则进行记录，并额外回退一个，否则为失败，下一个；
[C#] 纯文本查看 复制代码 private void docal(int[,] sqr, int[] task, int nu)
{
if (nu == num) //积木放完，输出结果
{
ans.Add(Recordans(sqr));
//textBox1.Text += DateTime.Now.ToString() + "获得一组解\r\n";
flag2 = 1;
}
else
{
int n = task[nu];
int[,] ntemp = nl[n];
for (int k = 0; k < sn[n, 0]; k++)//翻转
{
for (int l = 0; l < sn[n, 1]; l++)//旋转90度×4
{
for (int i = 0; i < 6 - ntemp.GetLength(0); i++)
{
for (int j = 0; j < num + 1 - ntemp.GetLength(1); j++)
{
if ((sqr[i, j] * ntemp[0, 0]) != 0) //格子已放则下一格
{
continue;
}
bool ol = false;
int[,] temp = Addarray(sqr, ntemp, i, j, n, ref ol);
//如果能放下，按放下后的棋盘放下一块，放不下则下一位置
if (!ol)
{
docal(temp, task, nu + 1);
if (flag2 > 0)
{
flag2--;
return;
}
}
}
}
ntemp = Roll(ntemp);
}
ntemp = Overturn(ntemp);
}
}
}
6.其他，旋转和翻转，大致能用，没追求效率；
[C#] 纯文本查看 复制代码 private int[,] Roll(int[,] nx)
{
int[,] nr = new int[nx.GetLength(1), nx.GetLength(0)];
for (int i = 0; i < nx.GetLength(1); i++)
{
for (int j = 0; j < nx.GetLength(0); j++)
{
nr[i, j] = nx[j, i];
}
}
nr = Overturn(nr);
return nr;
}
private int[,] Overturn(int[,] nx)
{
int[,] no = new int[nx.GetLength(0), nx.GetLength(1)];
for (int i = 0; i < nx.GetLength(0); i++)
{
for (int j = 0; j < nx.GetLength(1); j++)
{
no[i, j] = nx[nx.GetLength(0) - i - 1, j];
}
}
return no;
}
非专业人员，起名和代码非主流，我也有考虑学习学习，这个文件的不便还请见谅。
源码：
链接：https://pan.baidu.com/s/1NC_wNfXhvQS6tKa57hOhCQ
提取码：cd0w | 
[复制链接]
发表于 2024-8-27 20:45
|
发表于 2024-8-27 22:27
