华容道游戏c#最简破解

2023-10-11 00:58

本文主要是介绍华容道游戏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#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

C#中的 StreamReader/StreamWriter 使用示例详解

《C#中的StreamReader/StreamWriter使用示例详解》在C#开发中,StreamReader和StreamWriter是处理文本文件的核心类,属于System.IO命名空间,本... 目录前言一、什么是 StreamReader 和 StreamWriter?1. 定义2. 特点3. 用

如何使用C#串口通讯实现数据的发送和接收

《如何使用C#串口通讯实现数据的发送和接收》本文详细介绍了如何使用C#实现基于串口通讯的数据发送和接收,通过SerialPort类,我们可以轻松实现串口通讯,并结合事件机制实现数据的传递和处理,感兴趣... 目录1. 概述2. 关键技术点2.1 SerialPort类2.2 异步接收数据2.3 数据解析2.

C#原型模式之如何通过克隆对象来优化创建过程

《C#原型模式之如何通过克隆对象来优化创建过程》原型模式是一种创建型设计模式,通过克隆现有对象来创建新对象,避免重复的创建成本和复杂的初始化过程,它适用于对象创建过程复杂、需要大量相似对象或避免重复初... 目录什么是原型模式?原型模式的工作原理C#中如何实现原型模式?1. 定义原型接口2. 实现原型接口3

C# 委托中 Invoke/BeginInvoke/EndInvoke和DynamicInvoke 方法的区别和联系

《C#委托中Invoke/BeginInvoke/EndInvoke和DynamicInvoke方法的区别和联系》在C#中,委托(Delegate)提供了多种调用方式,包括Invoke、Begi... 目录前言一、 Invoke方法1. 定义2. 特点3. 示例代码二、 BeginInvoke 和 EndI

C#中的 Dictionary常用操作

《C#中的Dictionary常用操作》C#中的DictionaryTKey,TValue是用于存储键值对集合的泛型类,允许通过键快速检索值,并且具有唯一键、动态大小和无序集合的特性,常用操作包括添... 目录基本概念Dictionary的基本结构Dictionary的主要特性Dictionary的常用操作