算法求助：小游戏方块之谜遍历解
媳妇给娃买的玩具（个人觉得商标不算广告，如需打码，我再改），媳妇不会玩，我就想写段代码辅助一下。一开始我觉得这代码很简单呀，递归一下，算就完了，花了半天撸出一版代码，跑起来发现是我肤浅了，代码跑完怕是得以年计，那我要他做甚，陪我女儿慢慢长大吗。于是怒改代码，少许剪枝后，3*5的格子一分钟就算出一组解。我想了想，要他做甚，和我比赛谁拼的快吗。于是大改代码，先列出所有组合，对每种组合计算，这样必要时可以开线程。结果单线程时3*5用时1秒不到得28组解（多为镜像），4*5用时2秒多得193解（这个有点奇怪），5*5用时近一分钟得796解，6*5用时近21分钟得1985解，所以很显然，这算法还是失败的。
由于我基础确实很差，大学好像是学过算法课，但早忘光了，重新学习进度极为缓慢，在此恳请大佬指导下复杂度较低的算法，最好能在1小时内遍历完12*5的所有解。如有大佬指导，不胜感激。
我的主要思路：
1.用二维数组表示积木方块，类似int {
{3,3,3,3 },
{0,0,3,0 } };
2.旋转或翻转后重复（对称）的方块提前建立数组，记录需要翻转或旋转的次数；
3.棋盘为二维数组，放置积木是将积木数组与棋盘数组相加，放完会判断下重叠，即积木数组区域是否出现大于积木数值的值
private int[,] Addarray(int[,] nx, int[,] na, int r, int c,int nn,ref bool ol)
{
int[,] temp = new int;
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 += na;
if (temp > (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块的需生成所有积木组合
private void generateTask(int n)//遍历积木组合
{
prog_task.Clear();
int[] set= new int;
for (int i = 0; i < n; i++) set = i;//初始化，第一个集合
prog_task.Add(set.ToArray());
if (n < 12)
{
int position = n - 1;
while (true)
{
if (set == 11) position--;//最右数到上限，指针左移一位
else position = n - 1;//否则指针至最右
set++;
// 调整右边元素
for (int i = position + 1; i < n; i++)
set = set + 1;
prog_task.Add(set.ToArray());
if (set >= (12 - n))
break;
}
}
}
5.求解过程用递归，必须积木全部放完，则进行记录，并额外回退一个，否则为失败，下一个；
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;
int[,] ntemp = nl;
for (int k = 0; k < sn; k++)//翻转
{
for (int l = 0; l < sn; 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 * ntemp) != 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.其他，旋转和翻转，大致能用，没追求效率；
private int[,] Roll(int[,] nx)
{
int[,] nr = new int;
for (int i = 0; i < nx.GetLength(1); i++)
{
for (int j = 0; j < nx.GetLength(0); j++)
{
nr = nx;
}
}
nr = Overturn(nr);
return nr;
}
private int[,] Overturn(int[,] nx)
{
int[,] no = new int;
for (int i = 0; i < nx.GetLength(0); i++)
{
for (int j = 0; j < nx.GetLength(1); j++)
{
no = nx;
}
}
return no;
}
非专业人员，起名和代码非主流，我也有考虑学习学习，这个文件的不便还请见谅。
源码：
链接：https://pan.baidu.com/s/1NC_wNfXhvQS6tKa57hOhCQ
提取码：cd0w 不能套用现成的吗 justwz 发表于 2024-8-27 21:52
不能套用现成的吗
哪里有现成的，现成的是什么，算法还是软件，或者遍历完成的解法，大佬请细说 可以看一下这个网站：
https://isomerdesign.com/Pentomino/ 这个玩具怎么个玩法啊，没看懂 nob 发表于 2024-8-28 07:06
可以看一下这个网站：
https://isomerdesign.com/Pentomino/
虽然网站没看到源码，但让我知道了这游戏叫pentominos，这非常有用，以此为关键字，可以搜到一些内容，具体包括：
https://math.hws.edu/xJava/PentominosSolver/source/ 8x8 with 4 holes解法源码
https://benhoyt.com/writings/python-pentomino/ Fast pentomino puzzle solver ported from Forth to Python
https://github.com/brunotag/pentomino 某种限制打不开GitHub，暂时不知道这是啥
https://rosettacode.org/wiki/Pentomino_tiling# 不同语言的8x8 with 4 holes解法源码
以上可以算是现成的。虽然没细看，但其中有些不是遍历解，效率不一定高，但也够我学习好一阵了
页:
[1]