华容道游戏c#最简破解

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

华容道游戏的暴力破解是少年时候的梦想，那时候刚学电脑basic，也刚知道华容道这个游戏，就想拿电脑去破解这个游戏。很可惜那时候太年轻，basic也太弱，没有能成功。

前几天做网页爬虫，用到广度搜索，突然想到儿时的梦想，于是花了2天时间来实现。

在现代语言面前，要实现这个只需要1百多行代码，不需要递归，只需要简单的迭代

要点

1.需要采用广度搜索

2.需要去重复（剪枝）

3.穷举下一步的各种可能性

4.迭代

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

Scan	主函数。终点判断，穷举移动棋子，迭代
Move	移动棋子，这个效率或许不高，但应该是最简洁的。不用考虑棋子的形状，所有棋子一视同仁，按照位图的方式来移动，这样大大简化了移动判断，不管是曹操，还是横将竖将小兵，移动的方式是一样的，一个点一个点移动。
IsDuplicate	判重，包含去掉相似布局和镜像布局。使用HashSet类，大大简化代码。在Move里面调用可以少产生无用数据
Print	回溯解题过程，打印解题结果的每一步棋盘

破解时间在I7上只要70毫秒，进一步优化已经没有意义。并且不想过度优化而降低可读性，方便移植到各种语言。

棋盘用长度20的字符串来表示，处理起来很简单。

string initMap =
"1223" +
"1223" +
"4556" +
"4786" +
"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#最简破解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！