华容道游戏c#最简破解

2023-10-11 00:58
文章标签 c# 破解 游戏 .net 华容道 最简

本文主要是介绍华容道游戏c#最简破解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

华容道游戏的暴力破解是少年时候的梦想，那时候刚学电脑basic，也刚知道华容道这个游戏，就想拿电脑去破解这个游戏。很可惜那时候太年轻，basic也太弱，没有能成功。
前几天做网页爬虫，用到广度搜索，突然想到儿时的梦想，于是花了2天时间来实现。

在现代语言面前，要实现这个只需要1百多行代码，不需要递归，只需要简单的迭代
要点
1.需要采用广度搜索
2.需要去重复（剪枝）
3.穷举下一步的各种可能性
4.迭代

主要代码很简单，解题只有3个函数，可以说是目前最简单的破解程序了。

Scan主函数。终点判断，穷举移动棋子，迭代
Move

移动棋子，这个效率或许不高，但应该是最简洁的。不用考虑棋子的形状，所有棋子一视同仁，按照位图的方式来移动，这样大大简化了移动判断，不管是曹操，还是横将竖将小兵，移动的方式是一样的，一个点一个点移动。

IsDuplicate

判重，包含去掉相似布局和镜像布局。使用HashSet类，大大简化代码。在Move里面调用可以少产生无用数据

Print回溯解题过程，打印解题结果的每一步棋盘

破解时间在I7上只要70毫秒，进一步优化已经没有意义。 并且不想过度优化而降低可读性，方便移植到各种语言。
棋盘用长度20的字符串来表示，处理起来很简单。
  1.             string initMap =  
  2.                  "1223" +  
  3.                  "1223" +  
  4.                  "4556" +  
  5.                  "4786" +  
  6.                  "9  0";  
你也许没有想到大名鼎鼎的华容道用100多行代码就写出来了，如此简单。虽然代码简单，但里面包含的道理却不少。只是.net的List类和HashSet类帮我们完成了大部分的工作。
只要实现List类和HashSet类就可以移植到各种语言，在javascript等动态语言里，用数组就可以实现

运行时间



using System;
using System.Collections.Generic;
using System.Text;namespace Hrd
{class Node{public string map;public int parent;public Node(string map,int parent){this.map = map;this.parent = parent;}}class Huarongdao{//已经走过地图类型（去重复用）HashSet<string> history = new HashSet<string>();//每一步的所有走法（走到终点回溯上一步用，如果只求步数则可以不要）List<List<Node>> allNodes = new List<List<Node>>();//下一步各种走法节点List<Node> nextList;int index;enum Direct{Left = -1,Right = 1,Up = -4,Down =4}public Huarongdao(){}void Move(Direct dir,string map, char ch, bool first = true) {StringBuilder work= new StringBuilder(map);work.Replace(ch, ' ');for (int i = 0; i < 20; i++){if (map[i] == ch){int pos = i + (int)dir;int x = i % 4;if (dir == Direct.Left  && x == 0 ||dir == Direct.Right && x == 3 ||pos < 0 || pos >= 20) return;if (work[pos] != ' ') return;work[pos] = ch;}}string _work = work.ToString();//重复检查if (IsDuplicate(_work)) return;//加入下一步,记录父节点nextList.Add(new Node(_work, index));if (first){//试着走第二步，但不能退回if (dir != Direct.Right) Move(Direct.Left, _work, ch, false);if (dir != Direct.Left) Move(Direct.Right, _work, ch, false);if (dir != Direct.Down) Move(Direct.Up, _work, ch, false);if (dir != Direct.Up) Move(Direct.Down, _work, ch, false);}}bool IsDuplicate(string map){StringBuilder layout = new StringBuilder(map);//相似的形状统一成一种，去重复layout.Replace('3', '1').Replace('4', '1').Replace('6', '1').Replace('7', '0').Replace('8', '0').Replace('9', '0');if (!history.Add(layout.ToString())) return true;//左右镜像（大约节约1/2时间），去重复StringBuilder reverse = new StringBuilder(layout.ToString());for (int k = 0; k < 20; k++){int x = 3 - (k % 4);int y = k / 4;reverse[y * 4 + x] = layout[k];}if (history.Contains(reverse.ToString())) return true;return false;}void Print(int index){List<string> outList = new List<string>();int parent = index;for (int level = allNodes.Count-1; level >= 0; level--){string outMap = allNodes[level][parent].map;parent = allNodes[level][parent].parent;outList.Add(outMap);}int cnt = 0;for (int j = outList.Count - 1; j >= 0; j--){Console.WriteLine("--------------------------" + cnt++);for (int y = 0; y < 5; y++){Console.WriteLine(outList[j].Substring(y * 4, 4));}}}public void Scan(){string initMap ="1223" +"1223" +"4556" +"4786" +"9  0";List<Node> curList = new List<Node> { new Node(initMap, 0) };DateTime begin = DateTime.Now;//迭代直到无路可走while (curList.Count>0){//记录每一步allNodes.Add(curList);nextList = new List<Node>();for(index = 0; index < curList.Count; index++){string map = curList[index].map;//到达终点的判断if (map[4 * 4 + 1] == '2' && map[4 * 4 + 2] == '2'){Console.WriteLine("time:"+ (DateTime.Now - begin));Print(index);return;}//穷举各种可能性,去重复，加入到下一步的节点for (char ch = '0'; ch <= '9'; ch++){Move(Direct.Left,map, ch);Move(Direct.Right, map, ch);Move(Direct.Up, map, ch);Move(Direct.Down, map, ch);}}//迭代curList = nextList;}Console.WriteLine("无解");}}
}
下面是运行结果--------------------------0
1223
1223
4556
4786
9  0
--------------------------1
1223
1223
4556
4786
9 0 
--------------------------2
1223
1223
455 
4786
9 06
--------------------------3
1223
1223
4 55
4786
9 06
--------------------------4
1223
1223
4 55
4 86
9706
--------------------------5
1223
1223455486
9706
--------------------------6
1223
1223455
9486706
--------------------------7
1223
1223455
9486
7 06
--------------------------8
1223
122355
9486
7406
--------------------------9
1223
1223
55  
9486
7406
--------------------------10
1223
1223
55 8
94 6
7406
--------------------------11
1223
1223
5508
94 6
74 6
--------------------------12
1223
1223
5508
9 46
7 46
--------------------------13
1223
1223
550846
7946
--------------------------14
1223
122308
5546
7946
--------------------------15
1223
1223
0  8
5546
7946
--------------------------16
1223
1223
08  
5546
7946
--------------------------17
1223
1223
084 
5546
79 6
--------------------------18
1223
1223
0846
5546
79  
--------------------------19
1223
1223
0846
5546
7  9
--------------------------20
1223
1223
0846
554679
--------------------------21
1223
1223
084646
5579
--------------------------22
1223
1223
0 46
8 46
5579
--------------------------23
1223
1223
04 6
84 6
5579
--------------------------24
1223
1223
046 
846 
5579
--------------------------25
122 
122 
0463
8463
5579
--------------------------26
1 22
1 22
0463
8463
5579
--------------------------27122122
0463
8463
5579
--------------------------28
0122122463
8463
5579
--------------------------29
0122
8122463463
5579
--------------------------30
0122
8122
4 63
4 63
5579
--------------------------31
0 22
8 22
4163
4163
5579
--------------------------32
022 
822 
4163
4163
5579
--------------------------33
0223
8223
416 
416 
5579
--------------------------34
0223
8223
41 6
41 6
5579
--------------------------35
0223
8223
4176
41 6
55 9
--------------------------36
0223
8223
4176
4196
55  
--------------------------37
0223
8223
4176
419655
--------------------------38
0223
8223
4 76
4196155
--------------------------39
0223
822376
4196
4155
--------------------------40
0223
8223
7  6
4196
4155
--------------------------41
0  3
8223
7226
4196
4155
--------------------------4203
8223
7226
4196
4155
--------------------------43803223
7226
4196
4155
--------------------------44
7803223226
4196
4155
--------------------------45
7803
4223
4226196155
--------------------------46
7803
4223
4226
1 96
1 55
--------------------------47
7803
4223
4226
1  6
1955
--------------------------48
7803
4  3
4226
1226
1955
--------------------------49
78 3
40 3
4226
1226
1955
--------------------------50
783 
403 
4226
1226
1955
--------------------------51
7836
4036
422 
122 
1955
--------------------------52
7836
4036
4 22
1 22
1955
--------------------------53
7836
4 36
4022
1 22
1955
--------------------------54
7 36
4836
4022
1 22
1955
--------------------------55736
4836
4022
1 22
1955
--------------------------56
4736
4836022
1 22
1955
--------------------------57
4736
4836
1022
1 22955
--------------------------58
4736
4836
1022
1 22
9 55
--------------------------59
4736
4836
1 22
1 22
9055
--------------------------60
4736
4836
122 
122 
9055
--------------------------61
473 
483 
1226
1226
9055
--------------------------62
47 3
48 3
1226
1226
9055
--------------------------63
4 73
48 3
1226
1226
9055
--------------------------64
4 73
4 83
1226
1226
9055
--------------------------65473483
1226
1226
9055
--------------------------66
1473
1483226226
9055
--------------------------67
1473
1483
22 6
22 6
9055
--------------------------68
1473
14 3
22 6
2286
9055
--------------------------69
14 3
14 3
2276
2286
9055
--------------------------70
143 
143 
2276
2286
9055
--------------------------71
1436
1436
227 
228 
9055
--------------------------72
1436
1436
2278
22  
9055
--------------------------73
1436
1436
2278
2255
90  
--------------------------74
1436
1436
2278
2255
9  0
--------------------------75
1436
1436
2278
225590
--------------------------76
1436
143678
2255
2290
--------------------------77
1436
1436
7  8
2255
2290
--------------------------78
1436
1436
78  
2255
2290
--------------------------79
1436
1436
7855
22  
2290
--------------------------80
1436
1436
7855
22 9
22 0
--------------------------81
1436
1436
7855229220


                                    

                                        这篇关于华容道游戏c#最简破解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
                                    

                                    

                                

                            

                            

                        

                    

                    

                        

                            

                            http://www.chinasem.cn/article/184359。
                            
                        

                    

                    
                    

                        
                            
                        
                    

                

                

                    相关文章
                

                    

                        

                            

                                

                                    
                                        在C#中获取端口号与系统信息的高效实践
                                    
                                

                            

                            

                                

                                    在C#中获取端口号与系统信息的高效实践
                                

                                

                                    《在C#中获取端口号与系统信息的高效实践》在现代软件开发中,尤其是系统管理、运维、监控和性能优化等场景中,了解计算机硬件和网络的状态至关重要,C#作为一种广泛应用的编程语言,提供了丰富的API来帮助开...																									目录引言1. 获取端口号信息1.1 获取活动的 TCP 和 UDP 连接说明：应用场景：2. 获取硬
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#使用HttpClient进行Post请求出现超时问题的解决及优化
                                    
                                

                            

                            

                                

                                    C#使用HttpClient进行Post请求出现超时问题的解决及优化
                                

                                

                                    《C#使用HttpClient进行Post请求出现超时问题的解决及优化》最近我的控制台程序发现有时候总是出现请求超时等问题,通常好几分钟最多只有3-4个请求,在使用apipost发现并发10个5分钟也...																									目录优化结论单例HttpClient连接池耗尽和并发并发异步最终优化后优化结论我直接上优化结论吧，
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#使用yield关键字实现提升迭代性能与效率
                                    
                                

                            

                            

                                

                                    C#使用yield关键字实现提升迭代性能与效率
                                

                                

                                    《C#使用yield关键字实现提升迭代性能与效率》yield关键字在C#中简化了数据迭代的方式,实现了按需生成数据,自动维护迭代状态,本文主要来聊聊如何使用yield关键字实现提升迭代性能与效率,感兴...																									目录前言传统迭代和yield迭代方式对比yield延迟加载按需获取数据yield break显式示迭
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        c# checked和unchecked关键字的使用
                                    
                                

                            

                            

                                

                                    c# checked和unchecked关键字的使用
                                

                                

                                    《c#checked和unchecked关键字的使用》C#中的checked关键字用于启用整数运算的溢出检查,可以捕获并抛出System.OverflowException异常,而unchecked...																									目录在 C# 中，checked 关键字用于启用整数运算的溢出检查。默认情况下，C# 的整数运算不会自
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#实现获得某个枚举的所有名称
                                    
                                

                            

                            

                                

                                    C#实现获得某个枚举的所有名称
                                

                                

                                    《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下...																									C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C# 读写ini文件操作实现
                                    
                                

                            

                            

                                

                                    C# 读写ini文件操作实现
                                

                                

                                    《C#读写ini文件操作实现》本文主要介绍了C#读写ini文件操作实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...																									目录一、INI文件结构二、读取INI文件中的数据在C#应用程序中，常将INI文件作为配置文件，用于存储应用程序的
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#实现获取电脑中的端口号和硬件信息
                                    
                                

                            

                            

                                

                                    C#实现获取电脑中的端口号和硬件信息
                                

                                

                                    《C#实现获取电脑中的端口号和硬件信息》这篇文章主要为大家详细介绍了C#实现获取电脑中的端口号和硬件信息的相关方法,文中的示例代码讲解详细,有需要的小伙伴可以参考一下...																									我们经常在使用一个串口软件的时候，发现软件中的端口号并不是普通的COM1，而是带有硬件信息的。那么如果我们使用C#编写软件时候，如
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#中图片如何自适应pictureBox大小
                                    
                                

                            

                            

                                

                                    C#中图片如何自适应pictureBox大小
                                

                                

                                    《C#中图片如何自适应pictureBox大小》文章描述了如何在C#中实现图片自适应pictureBox大小,并展示修改前后的效果,修改步骤包括两步,作者分享了个人经验,希望对大家有所帮助...																									目录C#图片自适应pictureBox大小编程修改步骤总结C#图片自适应pictureBox大小上图中“z轴
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        使用C#代码计算数学表达式实例
                                    
                                

                            

                            

                                

                                    使用C#代码计算数学表达式实例
                                

                                

                                    《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来...																									目录C#代码计算数学表达式该方法很长，因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#实现WinForm控件焦点的获取与失去
                                    
                                

                            

                            

                                

                                    C#实现WinForm控件焦点的获取与失去
                                

                                

                                    《C#实现WinForm控件焦点的获取与失去》在一个数据输入表单中,当用户从一个文本框切换到另一个文本框时,需要准确地判断焦点的转移,以便进行数据验证、提示信息显示等操作,本文将探讨Winform控件...																									目录前言获取焦点改变TabIndex属性值调用Focus方法失去焦点总结最后前言在一个数据输入表单
                                

                                

                                    阅读更多...
                                

                            

                        

                    

            

        

    


    


    

        

            Copyright China编程   23002807@qq.com
        

        

            沪ICP备2023033072号-2