华容道游戏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# 比较两个list 之间元素差异的常用方法
                                    
                                

                            

                            

                                

                                    C# 比较两个list 之间元素差异的常用方法
                                

                                

                                    《C#比较两个list之间元素差异的常用方法》：本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧...																									目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        Python实例题之pygame开发打飞机游戏实例代码
                                    
                                

                            

                            

                                

                                    Python实例题之pygame开发打飞机游戏实例代码
                                

                                

                                    《Python实例题之pygame开发打飞机游戏实例代码》对于python的学习者,能够写出一个飞机大战的程序代码,是不是感觉到非常的开心,：本文主要介绍Python实例题之pygame开发打飞机...																									目录题目pygame-aircraft-game使用 Pygame 开发的打飞机游戏脚本代码解释初始化部
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#如何去掉文件夹或文件名非法字符
                                    
                                

                            

                            

                                

                                    C#如何去掉文件夹或文件名非法字符
                                

                                

                                    《C#如何去掉文件夹或文件名非法字符》：本文主要介绍C#如何去掉文件夹或文件名非法字符的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教...																									目录C#去掉文件夹或文件名非法字符net类库提供了非法字符的数组这里还有个小窍门总结C#去掉文件夹或文件名非法字符实现有输入字
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#之List集合去重复对象的实现方法
                                    
                                

                            

                            

                                

                                    C#之List集合去重复对象的实现方法
                                

                                

                                    《C#之List集合去重复对象的实现方法》：本文主要介绍C#之List集合去重复对象的实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教...																									目录C# List集合去重复对象方法1、测试数据2、测试数据3、知识点补充总结C# List集合去重复对象方法1、测试数据
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#实现将Office文档(Word/Excel/PDF/PPT)转为Markdown格式
                                    
                                

                            

                            

                                

                                    C#实现将Office文档(Word/Excel/PDF/PPT)转为Markdown格式
                                

                                

                                    《C#实现将Office文档(Word/Excel/PDF/PPT)转为Markdown格式》Markdown凭借简洁的语法、优良的可读性,以及对版本控制系统的高度兼容性,逐渐成为最受欢迎的文档格式...																									目录为什么要将文档转换为 Markdown 格式使用工具将 Word 文档转换为 Markdown（.
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        Java调用C#动态库的三种方法详解
                                    
                                

                            

                            

                                

                                    Java调用C#动态库的三种方法详解
                                

                                

                                    《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢？今天,我们...																									目录方法1：C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1：创建C#类库（.NET
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#代码实现解析WTGPS和BD数据
                                    
                                

                            

                            

                                

                                    C#代码实现解析WTGPS和BD数据
                                

                                

                                    《C#代码实现解析WTGPS和BD数据》在现代的导航与定位应用中,准确解析GPS和北斗（BD）等卫星定位数据至关重要,本文将使用C#语言实现解析WTGPS和BD数据,需要的可以了解下...																									目录一、代码结构概览1. 核心解析方法2. 位置信息解析3. 经纬度转换方法4. 日期和时间戳解析5. 辅助方法二、L
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        使用C#删除Excel表格中的重复行数据的代码详解
                                    
                                

                            

                            

                                

                                    使用C#删除Excel表格中的重复行数据的代码详解
                                

                                

                                    《使用C#删除Excel表格中的重复行数据的代码详解》重复行是指在Excel表格中完全相同的多行数据,删除这些重复行至关重要,因为它们不仅会干扰数据分析,还可能导致错误的决策和结论,所以本文给大家介绍...																									目录简介使用工具C# 删除Excel工作表中的重复行语法工作原理实现代码C# 删除指定Excel单元
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#使用MQTTnet实现服务端与客户端的通讯的示例
                                    
                                

                            

                            

                                

                                    C#使用MQTTnet实现服务端与客户端的通讯的示例
                                

                                

                                    《C#使用MQTTnet实现服务端与客户端的通讯的示例》本文主要介绍了C#使用MQTTnet实现服务端与客户端的通讯的示例,包括协议特性、连接管理、QoS机制和安全策略,具有一定的参考价值,感兴趣的可...																									目录一、MQTT 协议简介二、MQTT 协议核心特性三、MQTTNET 库的核心功能四、服务端（BR
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#继承之里氏替换原则分析
                                    
                                

                            

                            

                                

                                    C#继承之里氏替换原则分析
                                

                                

                                    《C#继承之里氏替换原则分析》：本文主要介绍C#继承之里氏替换原则,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教...																									目录C#里氏替换原则一.概念二.语法表现三.类型检查与转换总结C#里氏替换原则一.概念里氏替换原则是面向对象设计的基本原则之一：核心思想：所有引py
                                

                                

                                    阅读更多...
                                

                            

                        

                    

            

        

    


    


    

        

            Copyright China编程   23002807@qq.com
        

        

            沪ICP备2023033072号-2