华容道游戏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#集成DeepSeek模型实现AI私有化的流程步骤(本地部署与API调用教程)
                                    
                                

                            

                            

                                

                                    C#集成DeepSeek模型实现AI私有化的流程步骤(本地部署与API调用教程)
                                

                                

                                    《C#集成DeepSeek模型实现AI私有化的流程步骤(本地部署与API调用教程)》本文主要介绍了C#集成DeepSeek模型实现AI私有化的方法,包括搭建基础环境,如安装Ollama和下载DeepS...																									目录前言搭建基础环境1、安装 Ollama2、下载 DeepSeek R1 模型客户端 ChatBo
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C# string转unicode字符的实现
                                    
                                

                            

                            

                                

                                    C# string转unicode字符的实现
                                

                                

                                    《C#string转unicode字符的实现》本文主要介绍了C#string转unicode字符的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随...																									目录1. 获取字符串中每个字符的 Unicode 值示例代码：输出：2. 将 Unicode 值格式化
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#中读取XML文件的四种常用方法
                                    
                                

                            

                            

                                

                                    C#中读取XML文件的四种常用方法
                                

                                

                                    《C#中读取XML文件的四种常用方法》Xml是Internet环境中跨平台的,依赖于内容的技术,是当前处理结构化文档信息的有力工具,下面我们就来看看C#中读取XML文件的方法都有哪些吧...																									目录XML简介格式C#读取XML文件方法使用XmlDocument使用XmlTextReader/XmlTextWr
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#比较两个List集合内容是否相同的几种方法
                                    
                                

                            

                            

                                

                                    C#比较两个List集合内容是否相同的几种方法
                                

                                

                                    《C#比较两个List集合内容是否相同的几种方法》本文详细介绍了在C#中比较两个List集合内容是否相同的方法,包括非自定义类和自定义类的元素比较,对于非自定义类,可以使用SequenceEqual、...																									目录 一、非自定义类的元素比较1. 使用 SequenceEqual 方法（顺序和内容都相等）2.
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#使用DeepSeek API实现自然语言处理,文本分类和情感分析
                                    
                                

                            

                            

                                

                                    C#使用DeepSeek API实现自然语言处理,文本分类和情感分析
                                

                                

                                    《C#使用DeepSeekAPI实现自然语言处理,文本分类和情感分析》在C#中使用DeepSeekAPI可以实现多种功能,例如自然语言处理、文本分类、情感分析等,本文主要为大家介绍了具体实现步骤,...																									目录准备工作文本生成文本分类问答系统代码生成翻译功能文本摘要文本校对图像描述生成总结在C#中使用Deep
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#从XmlDocument提取完整字符串的方法
                                    
                                

                            

                            

                                

                                    C#从XmlDocument提取完整字符串的方法
                                

                                

                                    《C#从XmlDocument提取完整字符串的方法》文章介绍了两种生成格式化XML字符串的方法,方法一使用`XmlDocument`的`OuterXml`属性,但输出的XML字符串不带格式,可读性差,...																									方法1：通过XMLDocument的OuterXml属性，见XmlDocument类该方法获得的xm
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#多线程编程中导致死锁的常见陷阱和避免方法
                                    
                                

                            

                            

                                

                                    C#多线程编程中导致死锁的常见陷阱和避免方法
                                

                                

                                    《C#多线程编程中导致死锁的常见陷阱和避免方法》在C#多线程编程中,死锁（Deadlock）是一种常见的、令人头疼的错误,死锁通常发生在多个线程试图获取多个资源的锁时,导致相互等待对方释放资源,最终形...																									目录引言1. 什么是死锁？死锁的典型条件：2. 导致死锁的常见原因2.1 锁的顺序问题错误示例：不同
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#提取PDF表单数据的实现流程
                                    
                                

                            

                            

                                

                                    C#提取PDF表单数据的实现流程
                                

                                

                                    《C#提取PDF表单数据的实现流程》PDF表单是一种常见的数据收集工具,广泛应用于调查问卷、业务合同等场景,凭借出色的跨平台兼容性和标准化特点,PDF表单在各行各业中得到了广泛应用,本文将探讨如何使用...																									目录引言使用工具C# 提取多个PDF表单域的数据C# 提取特定PDF表单域的数据引言PDF表单是一
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#实现添加/替换/提取或删除Excel中的图片
                                    
                                

                            

                            

                                

                                    C#实现添加/替换/提取或删除Excel中的图片
                                

                                

                                    《C#实现添加/替换/提取或删除Excel中的图片》在Excel中插入与数据相关的图片,能将关键数据或信息以更直观的方式呈现出来,使文档更加美观,下面我们来看看如何在C#中实现添加/替换/提取或删除E...																									在Excandroidel中插入与数据相关的图片，能将关键数据或信息以更直观的方式呈现出来，使文档更
                                

                                

                                    阅读更多...
                                

                            

                        

                    

                    

                        

                            

                                

                                    
                                        C#实现系统信息监控与获取功能
                                    
                                

                            

                            

                                

                                    C#实现系统信息监控与获取功能
                                

                                

                                    《C#实现系统信息监控与获取功能》在C#开发的众多应用场景中,获取系统信息以及监控用户操作有着广泛的用途,比如在系统性能优化工具中,需要实时读取CPU、GPU资源信息,本文将详细介绍如何使用C#来实现...																									目录前言一、C# 监控键盘1. 原理与实现思路2. 代码实现二、读取 CPU、GPU 资源信息1.
                                

                                

                                    阅读更多...
                                

                            

                        

                    

            

        

    


    


    

        

            Copyright China编程   23002807@qq.com
        

        

            沪ICP备2023033072号-2