华容道再研究
这次我又给自己挖了一个更大的坑，已经确定华容道一共可分为六个领域，或者叫森林。分别为0到5 横式，比如0横式，表示布局为一个曹操，0个横将，5个竖将，4个兵； 2横式，表示布局为一个曹操，2个横将，3个竖将，4个兵；
六个森林，一定是没有任何关系的，独立的，因为对于滑块类游戏的规则，横将不可能变化为竖将，只有位置可以变化。
1) 现在我想找出每个森林共有多少个布局？
2) 每个森林又有多少颗相互独立的树？
相互独立的树是什么？假设一横式的森林有树A 和 树B，那么树A的任何节点都不会出现在树B中，即树A 和 树B的交集一定是空集，树A中的任意布局通过滑块游戏的规则可以演化为树A所有的其他布局，但不可能演化为树B中的任意布局。
那么，首先就需要一个枚举类，能够一个不漏地，并且也一个不多地枚举出华容道的所有布局，这样一个枚举类是最难以编写的，几乎没有人能一次性写对，而花多长时间实现这样一个无bug的枚举类，可以反映出思维的敏锐度，类似于头脑的转速。我比较差，大概花了三天，先开始我以为只要一天时间就够了，结果错的离谱，因为后来我发现，我想得还不是很清楚，就已经开始编码了，结果编写都一半时，发现一个难题，”怎么样才能比较优雅地从当前布局推出下一个布局呢？”
写到一半又发现，靠，之前的处理办法是错误的，又要推倒重来，
嗯，这种情况当时没有考虑到…
一旦正确地枚举出了所有的布局，问题就简单了，首先问题1有了答案，已经有华容道自动求解的现成代码，只要稍作修改，就能根据一个布局，得到包含这个布局的一颗树。有了从一个布局得到一颗树的方法，问题2也解决了，还可以判断一个森林，其中有多少颗树是有曹出布局的。
怎么枚举？用字典序来枚举，就是定义一个枚举规则，然后给计算机任意一个有效布局（可以放置1个大王，5个横将或者竖将，4个兵），计算机都能推出其下一个或者上一个布局，根据这个枚举规则，每个布局都有了一个唯一地，一一对应地序列号。
我是这样定义枚举规则的，首先放置大王，然后放置横将，然后放置竖将，最后放置4个兵，然后给4列5行的棋盘就行编号，
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
16 17 18 19
对于 一横式，第一个布局是：
// 5 5 4 4 | 0 1 2 3// 1 1 3 3 | 4 5 6 7// 3 3 1 1 | 8 9 10 11// 1 1 0 0 | 12 13 14 15// 0 0 0 0 | 16 17 18 19最后一个布局是：
// 0 0 0 0 | 0 1 2 3// 0 0 3 3 | 4 5 6 7// 3 3 1 1 | 8 9 10 11// 1 1 5 5 | 12 13 14 15// 4 4 1 1 | 16 17 18 19为了代码更清晰简洁，先不考虑4个兵的放置，因为前面关于华容道自动求解的盘面编码类的代码，已经有了关于4个兵的组合序号表了，直接拿来用。
这个枚举规则，保证两个空格总是逐渐地 从高位移动到低位，
而相应地，大王，横将竖将总是逐渐地 从低位移动到高位。
package game.hrd.game.hrd.refactor;import game.hrd.LocalConst;/*** Created by huangcongjie on 2017/12/24.*/
public class LayoutEnumerator {private int hNum = 0; //横将个数 只能在构造函数初始化private int sNum = 0; //竖将个数 只能在构造函数初始化public int mIndex = -1; //大王的位置private int[] layout;private int[][] movableS, movableH;private int[] sCursors, hCursors;int[] WQ = LocalConst.WQ2;private int[] binCombineArr = new int[15];private int count = 0;public LayoutEnumerator(int hCount) {if (hCount < 0 || hCount > 5) {throw new RuntimeException("invalid horizontal piece number! the hCount should be [0, 5]");}setBinCombineArr();hNum = hCount;sNum = 5 - hCount;sCursors = new int[sNum];hCursors = new int[hNum];movableS = new int[sNum][];movableH = new int[hNum][];mIndex = 0;layout = new int[20];layout[mIndex] = layout[mIndex + 1] = 5;layout[mIndex + 4] = layout[mIndex + 5] = 1;initHorizontalArrs(layout, 0, 0);initVerticalArrs(layout, 0, 0);}public LayoutEnumerator next() {//小兵移不动了，开始移动竖将if (sNext()) {count++;//移动竖将成功return this;}//竖将移不动了，开始移动横将if (hNext()) {boolean moved = true;while ( !initVerticalArrs(layout, 0, 0) ) {//横将的摆放，让竖将没位置了for (int i = 0; i < layout.length; i++) {if (layout[i] == 3) {layout[i] = layout[i + 4] = 0;}}moved = hNext();if (!moved) {//横将移不动了break;}}if (moved) {count++;//移动横将成功return this;}}//横将移不动了，开始移动大王mIndex++;if (LocalConst.COL[mIndex] == 3) {mIndex++;}if (mIndex > 14) {//大王都移不动了，所有布局都按字典序列枚举完毕return null;} else {count++;//移动大王成功，开始初始化 横将，竖将，空格和小兵layout = new int[20];layout[mIndex] = layout[mIndex + 1] = 5;layout[mIndex + 4] = layout[mIndex + 5] = 1;initHorizontalArrs(layout, 0, 0);initVerticalArrs(layout, 0, 0);return this;}}// 3 5 5 3 | 0 1 2 3// 1 1 1 1 | 4 5 6 7// 3 4 4 3 | 8 9 10 11// 1 0 0 1 | 12 13 14 15// 0 0 0 0 | 16 17 18 19//-------------------------// 0 3 4 7 8 11 12 13 14 15 >// 0 3 4 7 8 11 12// 3 4 7 8 11 12 13// 8 11 12 13 14// 11 12 13 14 15private boolean sNext() {int i = sNum - 1;boolean flag = false;for (; i >=0; i--) {int loc = movableS[i][sCursors[i]];layout[loc] = layout[loc + 4] = 0;int a = sCursors[i] + 1;for (int j = a; j < movableS[i].length; j++) {int loc2 = movableS[i][j];if (layout[loc2] == 0 && layout[loc2 + 4] == 0) {sCursors[i] = j;flag = true;break;}}if (flag) {break;}}if (flag) {int loc = movableS[i][sCursors[i]];layout[loc] = 3;layout[loc + 4] = 1;//change movableS[i+] and set sCursors[i+] = 0;initVerticalArrs(layout, loc + 1, i + 1);}return flag;}private boolean hNext() {int i = hNum - 1;boolean flag = false;for (; i >=0; i--) {int loc = movableH[i][hCursors[i]];layout[loc] = layout[loc + 1] = 0;int a = hCursors[i] + 1;for (int j = a; j < movableH[i].length; j++) {int loc2 = movableH[i][j];if (layout[loc2] == 0 && layout[loc2 + 1] == 0) {hCursors[i] = j;flag = true;break;}}if (flag) {break;}}if (flag) {int loc = movableH[i][hCursors[i]];layout[loc] = 4;layout[loc + 1] = 4;initHorizontalArrs(layout, loc + 2, i + 1);}return flag;}private boolean initVerticalArrs(int[] layout, int startLoc, int index) {if (index >= sNum) {return true;}sCursors[index] = 0;int[] movableLst = new int[12];int movableCount = 0;for (int i = startLoc; i < layout.length; i++) {if (LocalConst.ROW[i] < 4 &&layout[i] == 0 && layout[i+4] == 0) {movableLst[movableCount] = i;movableCount++;}}if (movableCount == 0) {//横将的摆放不合法，因为使得有竖将无法摆放return false;}int sCount = sNum - index;int[] temp = HrdUtil.copy(layout);int[] rArr = new int[sCount];int num = 0;for (int i = 15; i >= 0; i--) {if (temp[i] == 0 && temp[i+4] == 0) {rArr[num] = i;num++;if (sCount == num) {break;}temp[i] = 3;}}int[] locs = new int[12];int n = 0;for (int j = 0; j < movableCount; j++) {int max = rArr[sCount - 1];int loc = movableLst[j];if (loc <= max) {locs[n] = loc;n++;}}int[] locations = new int[n];for (int m = 0; m < n; m++) {locations[m] = locs[m];}movableS[index] = locations;int firstLoc = movableLst[0];layout[firstLoc] = 3;layout[firstLoc + 4] = 1;return initVerticalArrs(layout, firstLoc + 1, index + 1);}private void initHorizontalArrs(int[] layout, int startLoc, int index) {if (index >= hNum) {return;}hCursors[index] = 0;int[] movableLst = new int[11];int movableCount = 0;for (int i = startLoc; i < 20; i++) {if (LocalConst.COL[i] < 3 &&layout[i] == 0 && layout[i+1] == 0) {movableLst[movableCount] = i;movableCount++;}}int hCount = hNum - index;int num = 0;int[] rArr = new int[hCount];for (int i = 18; i >= 0; i--) {if (LocalConst.COL[i] < 3 && layout[i] == 0 && layout[i+1] == 0) {rArr[num] = i;num++;if (hCount == num) {break;}i--;}}int[] locs = new int[11];int n = 0;for (int j = 0; j < movableCount; j++) {int max = rArr[hCount - 1];int loc = movableLst[j];if (loc <= max) {locs[n] = loc;n++;}}int[] locations = new int[n];for (int m = 0; m < n; m++) {locations[m] = locs[m];}movableH[index] = locations;int firstLoc = movableLst[0];layout[firstLoc] = layout[firstLoc + 1] = 4;initHorizontalArrs(layout, firstLoc + 2, index + 1);}private void initVerticalArrs3(int[] layout, int startLoc, int sCount) {if (sCount < 1)return;for (int i = 0; i < sCount; i++) {sCursors[sNum - 1 - i] = 0;}int[] movableLst = new int[12];int movableCount = 0;for (int i = startLoc; i < layout.length; i++) {if (LocalConst.ROW[i] < 4 &&layout[i] == 0 && layout[i+4] == 0) {movableLst[movableCount] = i;movableCount++;}}int[] temp = HrdUtil.copy(layout);int[] arr = new int[sCount];int num = 0;for (int i = startLoc; i < temp.length; i++) {if (LocalConst.ROW[i] < 4 &&temp[i] == 0 && temp[i+4] == 0) {arr[num] = i;num++;if (sCount == num) {break;}temp[i+4] = 1;}}temp = HrdUtil.copy(layout);int[] rArr = new int[sCount];num = 0;for (int i = 15; i >= 0; i--) {if (temp[i] == 0 && temp[i+4] == 0) {rArr[num] = i;num++;if (sCount == num) {break;}temp[i] = 3;}}int offset = sNum - sCount;for (int i = 0; i < sCount; i++) {int[] locs = new int[12];int n = 0;for (int j = 0; j < movableCount; j++) {int max = 99;if (i < sCount - 1) {max = rArr[sCount - 1 - i];}int min = -1;if (i > 0) {min = arr[i];}int loc = movableLst[j];if (loc >= min && loc <= max) {locs[n] = loc;n++;}}int[] locations = new int[n];for (int m = 0; m < n; m++) {locations[m] = locs[m];}movableS[offset + i] = locations;}for (int i = 0; i < arr.length; i++) {int loc = arr[i];layout[loc] = 3;layout[loc + 4] = 1;}}// 4 4 4 4 | 0 1 2 3// 5 5 4 4 | 4 5 6 7// 1 1 0 0 | 8 9 10 11// 0 0 0 0 | 12 13 14 15// 0 0 0 0 | 16 17 18 19//--------------------------------// 0 1 2 6 10 12 13 14 16 17 18 >// 0 1 2 6 10 12 13 14// 2 6 10 12 13 14 16// 6 10 12 13 14 16 17 18public int[] getLayout() {return layout;}private void setBinCombineArr() {int m = 0;for (int i = 1; i < 63; i++) {int k = 0;for (int j = 0; j < WQ.length; j++) {if ( (i & WQ[j]) > 0) {k++;}}if (k == 4) {binCombineArr[m] = i;m++;}}}public int[][] getBin15Layouts() {int[] locations = new int[6];int m = 0;for (int i = 0; i < layout.length; i++) {if (layout[i] == 0 || layout[i] == 2) {locations[m] = i;m++;}}int[][] ret = new int[15][];int k1 = -1, k2 = -1;for (int i = 0; i < binCombineArr.length; i++) {int[] bingLayout = HrdUtil.copy(layout);int combo = binCombineArr[i];for (int j = 0; j < 6; j++) {if ( (combo & WQ[j]) > 0) {bingLayout[locations[j]] = 2;} else {k1 = k2;k2 = locations[j];}}bingLayout[k1] = bingLayout[k2] = 0;ret[i] = bingLayout;}return ret;}public static void test() {int sum = 0;for (int i = 0; i < 6; i++) {int hCount = i;LayoutEnumerator enumerator = new LayoutEnumerator(hCount);System.out.print(enumerator.getPrintLayout2());int total = 1;while ((enumerator.next() != null)) {total ++;
// System.out.print(enumerator.getPrintLayout2());}System.out.println(String.format("%d横式共有%d节点", hCount, total));sum += total;}System.out.println(String.format("华容道共有%d节点", sum));}public String getPrintLayout2() {String layoutStr = "";for (int i = 0; i < 20; i++) {layoutStr += layout[i] + "\t";if (i % 4 == 3) {layoutStr += "\n";}}layoutStr = layoutStr.substring(0, layoutStr.length() - 1);layoutStr += "\n---------" + count + "-----------\n\n";return layoutStr;}public static String getPrintLayout(int[] layout, int count) {String layoutStr = "";for (int i = 0; i < 20; i++) {layoutStr += layout[i] + "\t";if (i % 4 == 3) {layoutStr += "\n";}}layoutStr = layoutStr.substring(0, layoutStr.length() - 1);layoutStr += "\n---------" + count + "-----------\n\n";return layoutStr;}public static String getPrintLayout2(int[] layout, int count) {String layoutStr = "";for (int i = 0; i < 20; i++) {layoutStr += layout[i] + ", ";if (i % 4 == 3) {layoutStr += "\n";}}layoutStr = layoutStr.substring(0, layoutStr.length() - 1);layoutStr += "\n---------" + count + "-----------\n\n";return layoutStr;}static public String toLayoutString(int[] layout2) {String layout = "";for (int i = 0; i < 20; i++) {layout += layout2[i];if (i % 4 == 3) {layout += ", ";} else {layout += " ";}}layout = layout.substring(0, layout.length() - 2);return layout;}// 3 5 5 3 | 0 1 2 3// 1 1 1 1 | 4 5 6 7// 3 4 4 3 | 8 9 10 11// 1 0 0 1 | 12 13 14 15// 0 0 0 0 | 16 17 18 19// 0 3 4 7 8 11 12 13 14 15 >// 0 3 4 7 8 11 12// 3 4 7 8 11 12 13// 8 11 12 13 14// 11 12 13 14 15// 3 3 3 3 | 0 1 2 3// 1 1 1 1 | 4 5 6 7// 0 4 4 0 | 8 9 10 11// 5 5 0 0 | 12 13 14 15// 1 1 0 0 | 16 17 18 19// 0 1 2 3 4 7 11 14 15 >// 0 1 2 3 4// 1 2 3 4 7// 2 3 4 7 11 14// 4 7 11 14 15// 4 4 4 4 | 0 1 2 3// 5 5 4 4 | 4 5 6 7// 1 1 0 0 | 8 9 10 11// 0 0 0 0 | 12 13 14 15// 0 0 0 0 | 16 17 18 19// 0 1 2 6 10 12 13 14 16 17 18 >// 0 1 2 6 10 12 13 14// 2 6 10 12 13 14 16// 6 10 12 13 14 16 17 18
}代码讲解：
movableS，movableH是二维数组
最核心的代码方法，
boolean initVerticalArrs() 初始化所有竖将的可行位置数组，movableS, 所有竖将放置成功则返回true
initHorizontalArrs()初始化所有横将的可行位置数组，movableH
initVerticalArrs的功能：
如果给定一个布局的大王位置，横将位置，则所有竖将能放置在哪些位置都要尽可能地确定下来，确定每个竖将最小和最大的可放置位置。
initHorizontalArrs的功能：
如果给定一个布局的大王位置，则所有横将能放置在哪些位置都要尽可能地确定下来。
重要的代码方法
int[] sCursors, hCursors; 分别表示竖将的游标，横将的游标
sNext() 移动竖将，成功则返回true，当所有竖将移动到头时，返回false，负责更新竖将的游标
hNext() 移动横将，返回值同sNext()，负责更新横将的游标
举个例子
// 3 5 5 3 | 0 1 2 3// 1 1 1 1 | 4 5 6 7// 3 4 4 3 | 8 9 10 11// 1 0 0 1 | 12 13 14 15// 0 0 0 0 | 16 17 18 19// 0 3 4 7 8 11 12 13 14 15 >// 0 3 4 7 8 11 12// 3 4 7 8 11 12 13// 8 11 12 13 14// 11 12 13 14 15对于横刀立马布局，已经给定了大王，关羽的位置，那么所有竖将的可选位置是 // 0 3 4 7 8 11 12 13 14 15 >
第一个竖将 0 3 4 7 8 11 12
第二个竖将 3 4 7 8 11 12 13
第三个竖将 8 11 12 13 14
第四个竖将 11 12 13 14 15
initVerticalArrs() 负责把movableS初始化为以上那个二维数组，
不仅要推出所有竖将的可选位置，还要知道针对每个竖将，哪些位置是已经被其他竖将占用了，不能在放置了，如第一个一定不能放置在13 14 15因为已经被后三个占用了
第二个一定不能放0 14 15，第三第四个同理
还有三点要强调，（都是走过的坑）
第一点，initVerticalArrs为什么是递归的，我曾经试图把它改为非递归的，结果几个小时都没有搞定，而且各种错误，非常烦，因为其中的局部变量 rArr， 是动态的，不能在一次循环中，正确地初始化，必须要在前面竖将已经放置好的情况下才能，initVerticalArrs3() 方法中去初始化rArr是不正确的。
比如
// 5 5 0 0 | 0 1 2 3// 1 1 0 0 | 4 5 6 7// 4 4 3 0 | 8 9 10 11// 3 3 1 3 | 12 13 14 15// 1 1 0 1 | 16 17 18 19如果第二个竖将不确定放置在11 还是 12，那么最后两个竖将也不能确定怎么放
第二点，如何更新二维数组movableS ？还是以上面的横刀立马为例，假设
第三个竖将 8 11 12 13 14
第四个竖将 11 12 13 14 15
第四个竖将已经走到15，第三个竖将 需要从8走到11，那么第四个竖将的可放置位置都要改变，并且其对应的游标置0，sCursors[3] = 0, movableS[3]的所有元素都要更新，
如果第一个竖将走到下一个位置，第二三四个竖将所有的可放置数组都要更新，并且相应地游标置0
如果横将走到下一个位置，整个二维数组movableS都要改，sCursors的所有元素置0
第三点，为什么initVerticalArrs() 有时为返回false，因为大王，横将的摆放，有时会使得竖将放不下了，比如如下二横式，怎么放第三个竖将？无解，那么横将必须的进行下一种摆放
// 0 0 0 0 | 0 1 2 3// 5 5 4 4 | 4 5 6 7// 1 1 0 0 | 8 9 10 11// 0 0 4 4 | 12 13 14 15// 0 0 0 0 | 16 17 18 19如果曹操走到下一个位置，整个二维数组movableS和movableH都要改，sCursors和hCursors的所有元素置0
针对哈希布局的盘面编码类
package game.hrd.game.hrd.refactor;import game.hrd.LocalConst;//针对哈希布局的盘面编码类
public class HashLayoutEncoder {//组合序号表short[] Hz; //横将short[] Sz; //竖将short[] Bz; //小兵//权值表int[] Hw;int[] Sw;int[] Mw;public int bmTotal;public HashLayoutEncoder(int[] layout) {Hz = new short[4096 * 3];Sz = new short[4096 * 3];Bz = new short[128];//C12取5=792Hw = new int[792*2];Sw = new int[792];int i,j,k;int Hn=0, Bn=0, Sn=0; //各类子数目,大王默认为1不用计数for(i=0;i<20;i++){ //计算各种棋子的个数if(layout[i] == LocalConst.B) Bn++;if(layout[i] == LocalConst.H) Hn++;if(layout[i] == LocalConst.S) Sn++;}Hn /= 2;int[] WQ2 = LocalConst.WQ2;
// int Hmax=WQ2[11],Smax=WQ2[12-Hn*2],Bmax=WQ2[16-(Hn+Sn)*2]; //各种子的最大二进位数int Hmax=WQ2[11],Smax=WQ2[12],Bmax=WQ2[6]; //各种子的最大二进位数short Hx=0,Sx=0,Bx=0; //各种棋子组合的最大序号//初始化组合序号表for(i=0; i<4096; i++){for(j=0,k=0;j<12;j++) {if((i & WQ2[j]) > 0) {k++; //计算1的个数}}if(k==Hn && iif(k==Sn && iif(k==Bn && iint Sq=Bx,Hq=Bx*Sx,Mq=Bx*Sx*Hx; //竖将位权,横将位权,王位权Mw = new int[12];Hw = new int[Hx];Sw = new int[Sx];for(i=0;i<12;i++) Mw[i]=i*Mq; //初始化大王权值表for(i=0;i//初始化横将权值表for(i=0;i//初始化竖将权值表bmTotal = Mq*12;}//盘面编码public int encode(int[] layout) {int Bb=0,Bd=-1; //空位序号记录器int Sb=0,Sd=-1; //竖条序号记录器int Hb=0,Hd=-1; //横条序号记录器int Mb = 0; //大王序号记录器int c;int[] f = new int[20];for(int i = 0; i < 20; i++){c=layout[i];if(c == LocalConst.K) { //大王定序if(f[i] == 0) {Mb = i - LocalConst.ROW[i];f[i] = f[i + 1] = f[i + 4] = f[i + 5] = 1;}continue;}if (LocalConst.COL[i]<3 && layout[i+1] <= LocalConst.H) {if (LocalConst.ROW[i] < 1) {Hd++; //横条位置序号(编号)} else if (layout[i-4] <= LocalConst.H &&layout[i-3] <= LocalConst.H) {Hd++; //横条位置序号(编号)}}if (c == LocalConst.H) {//横将定序,转为二进制进行询址得Hbif(f[i] == 0) {Hb += LocalConst.WQ2[Hd];f[i] = f[i+1] = 1;}continue;}if (LocalConst.ROW[i]<4 && layout[i+4]<=LocalConst.S) {if (LocalConst.ROW[i] < 1) {Sd++; //竖将位置序号(编号)} else if (layout[i-4] <= LocalConst.H) {Sd++; //竖将位置序号(编号)}}if (c == LocalConst.S) { //竖条定序,转为二进制进行询址得Sbif(f[i] == 0) {Sb += LocalConst.WQ2[Sd];f[i] = f[i+4] = 1;}continue;}if(c == LocalConst.B || c == 0)Bd++; //小兵位置序号(编号)if(c == LocalConst.B)Bb += LocalConst.WQ2[Bd]; //小兵定序,转为二进制进行询址得Bb}//Hb,Sb,Bb为组合序号,"横刀立马"最大值为小兵C(6,4)-1=15-1,竖条C(10,4)-1=210-1Bb=Bz[Bb];Sb=Sz[Sb];Hb=Hz[Hb];//询址后得得Bb,Sb,Hb组合序号return Bb+Sw[Sb]+Hw[Hb]+Mw[Mb]; //用位权编码,其中Bb的位权为1}//按左右对称规则考查棋盘,对其编码public int symmetricEncode(int[] q){char i;int[] q2 = new int[20];for(i=0; i<20; i+=4) {q2[i]=q[i+3];q2[i+1]=q[i+2];q2[i+2]=q[i+1];q2[i+3]=q[i];}return encode(q2);}public static String getPrintLayout(int[] layout) {String layoutStr = "";for (int i = 0; i < 20; i++) {layoutStr += layout[i] + "\t";if (i % 4 == 3) {layoutStr += "\n";}}layoutStr = layoutStr.substring(0, layoutStr.length() - 1);return layoutStr;}
} package game.hrd.game.hrd.refactor;import game.hrd.LocalConst;/*** Created by huangcongjie on 2017/12/20.*/
public class HashLayoutAnalyzer implements IAnalyzer {private int k1 = -1; //空格1位置private int k2 = -1; //空格2位置private int h; //两空格的联合类型, {0:不联合,1:竖联合,2:横联合}@Overridepublic void analyze(HrdNode hrdLayout) {int i=0; //i,列k1 = k2 = -1;h = 0;int[] layout = hrdLayout.layout;for(i=0; i<20; i++){if(layout[i] == 0) {if (k1 == -1) {k1 = i;} else {k2 = i;break;}}}if (k1 + 4 == k2) {h = 1; //空格竖联合}if (k1 + 1 == k2 && LocalConst.COL[k1] < 3) {h = 2; //空格横联合}int col1 = LocalConst.COL[k1];int col2 = LocalConst.COL[k2];if (col1 > 0) {i = k1 - 1;zinb(hrdLayout, i, k1);if (layout[i] == 3) {if (h == 1)hrdLayout.addChoice(i, k1);}if (layout[i] == 5) {if (h == 1)hrdLayout.addChoice(i - 1, k1 - 1);}if (layout[i] == 4) {if (h == 2) {hrdLayout.addChoice(i - 1, k2 - 1);}hrdLayout.addChoice(i - 1, k1 - 1);}}if (col1 < 3) {i = k1 + 1;zinb(hrdLayout, i, k1);if (layout[i] == 3) {if (h == 1)hrdLayout.addChoice(i, k1);}if (layout[i] == 5) {if (h == 1)hrdLayout.addChoice(i, k1);}if (layout[i] == 4) {hrdLayout.addChoice(i, k1); //如果横联合,k1不是第一空,所以不用判断h}}if (k1 > 3) {i = k1 - 4;zinb(hrdLayout, i, k1);if (layout[i] == 4 && layout[i+1] == 4 &&(col1 != 1 || layout[i-1] != 4) ) {if (h == 2)hrdLayout.addChoice(i, k1);}if (layout[i] == 1) {if (layout[i-4] == 3) {if (h == 1) {hrdLayout.addChoice(i - 4, k2 - 4);}hrdLayout.addChoice(i - 4, k1 - 4);}if (layout[i-4] == 5 && layout[i-3] == 5) {if (h == 2)hrdLayout.addChoice(i - 4, k1 - 4);}}}if (k1 < 16) {i = k1 + 4;zinb(hrdLayout, i, k1);if (layout[i] == 3)hrdLayout.addChoice(i, k1);if (layout[i] == 4 && i < 19 && layout[i+1] == 4 &&(col1 != 1 || layout[i-1] != 4) ) {if (h == 2) {hrdLayout.addChoice(i, k1);}}if (layout[i] == 5 && layout[i+1] == 5) {if (h == 2)hrdLayout.addChoice(i, k1);}}if (col2 > 0) {i = k2 - 1;zinb(hrdLayout, i, k2);if (layout[i] == 4) {hrdLayout.addChoice(i - 1, k2 - 1);}}if(k2>3) {i = k2 - 4;zinb(hrdLayout, i, k2);if(layout[i]==1 && layout[i-4] == 3) {hrdLayout.addChoice(i - 4, k2 - 4);}}if(col2<3) {i = k2 + 1;zinb(hrdLayout, i, k2);if(layout[i]==4) {if(h==2) {hrdLayout.addChoice(i, k1);}hrdLayout.addChoice(i, k2);}}if(k2<16) {i = k2 + 4;zinb(hrdLayout, i, k2);if(layout[i]==3) {if(h==1) {hrdLayout.addChoice(i, k1);}hrdLayout.addChoice(i, k2);}}}private void zinb(HrdNode hrdLayout, int src, int dst) {if (hrdLayout.layout[src] == 2) {//小兵if (h > 0) {hrdLayout.addChoice(src, k1);hrdLayout.addChoice(src, k2);} else {hrdLayout.addChoice(src, dst);}}}//走一步函数@Overridepublic void step(int[] layout, int src, int dst) {int c = layout[src];int lx = c;if (c == 1) {lx = layout[src-4];}switch(lx) {case 2: //兵layout[src] = 0;layout[dst] = c;break;case 3: //竖layout[src] = layout[src+4] = 0;layout[dst] = c;layout[dst+4] = 1;break;case 4: //横layout[src] = layout[src+1]=0;layout[dst] = layout[dst+1]=c;break;case 5: //王layout[src] = layout[src+1]= layout[src+4]=layout[src+5]=0;layout[dst] = layout[dst+1]= c;layout[dst+4]=layout[dst+5]= 1;break;}}
}
package game.hrd.game.hrd.refactor;public class HrdNode {public int[] layout;public int level = 0;public HrdNode parent = null;//记录上次移动的索引private int preMovedIndex = -1;//原位置,目标位置,最多只会有10步public int[] srcArr = new int[10];public int[] dstArr = new int[10];public int totalChoices = 0;private IAnalyzer analyzer;private boolean isHashLayout;public int nodeNum=1;public boolean outable = false;public int hNum;private int dstCode = -1;public int bmCode = -2;public void setGoal(int code) {dstCode = code;}public HrdNode(int[] layout, IAnalyzer analyzer, boolean useHash) {this.layout = layout;this.analyzer = analyzer;isHashLayout = useHash;analyzer.analyze(this);}public void addChoice(int src, int dst) {srcArr[totalChoices] = src;dstArr[totalChoices] = dst;totalChoices++;}public boolean isGoal() {if (dstCode >= 0) {return bmCode == dstCode;}return layout[13] == 5 && layout[14] == 5;}public HrdNode giveBirth(IChecker encoder, Solver.IListener listener) {HrdNode answer = null;for (int i = 0; i < totalChoices; i++) {if (srcArr[i] == preMovedIndex) {//和上次移动同一个棋子时不搜索,可提速20%左右continue;}int[] childLayout = HrdUtil.copy(layout);analyzer.step(childLayout, srcArr[i], dstArr[i]);if (encoder.checkAndModify(childLayout)) {//get permission to giveBirthHrdNode child = new HrdNode(childLayout, analyzer, isHashLayout);child.bmCode = encoder.getCurrentCode();child.parent = this;child.setGoal(dstCode);child.level = this.level + 1;child.setPreMovedIndex(dstArr[i]);if (listener != null) {listener.validNodeCreated(child);if (child.isGoal()) {answer = child;}}}}return answer;}// public int getValidChildrenNum() {
// return validChildrenNum;
// }public boolean isHashLayout() {return isHashLayout;}public void setPreMovedIndex(int preMovedIndex) {this.preMovedIndex = preMovedIndex;}
}package game.hrd.game.hrd.refactor;import game.hrd.PmBm;import java.util.ArrayList;/*** Created by huangcongjie on 2017/12/29.*/
public class TreeFinder {HrdNode[] queue;int searchAmount = 0;int processingIndex = 0;int maxAmount = 500000;private int[] flagMap;private int[][] layoutMap = new int[500000][20];private int[] codeSnMap; //根据编码找序列号private void addToQueue(HrdNode node, int nodeCode, int dcCode) {if (searchAmount >= maxAmount) {System.out.println("对溢出");return;}queue[searchAmount] = node;searchAmount++;markSearched(nodeCode);markSearched(dcCode);}//--广度优先--private HrdNode find(int[] layout) {long t1 = System.currentTimeMillis();long cost = 0;IAnalyzer analyzer = new HashLayoutAnalyzer();HrdNode root = new HrdNode(layout, analyzer, false);if (root.isGoal()) {root.outable = true;}IChecker checker = new LayoutToCode(root.layout);maxAmount = ((LayoutToCode) checker).codeTotalNum / 10;queue = new HrdNode[maxAmount];searchAmount = processingIndex = 0;HrdNode curNode = root;checker.checkAndModify(root.layout);addToQueue(root, checker.getCurrentCode(), checker.getSymmetricCode());while (processingIndex < searchAmount) {
// System.out.println("searchAmount: " + searchAmount);HrdNode answer = curNode.giveBirth(checker, new Solver.IListener() {@Overridepublic void validNodeCreated(HrdNode child) {addToQueue(child, checker.getCurrentCode(), checker.getSymmetricCode());}});if (answer != null) {
// cost = System.currentTimeMillis() - t1;
// System.out.println("found answer! total steps: " + answer.level + " cost: " + cost + "ms");
// displaySolution(answer);root.outable = true;}processingIndex++;curNode = queue[processingIndex];}cost = System.currentTimeMillis() - t1;root.nodeNum = searchAmount;return root;}private void init(int hCount) {
// for (int m = 0; m < 6; m++) {LayoutEnumerator enumerator = new LayoutEnumerator(hCount);int count = 0;System.out.print(enumerator.getPrintLayout(enumerator.getLayout(), count));int[] first = enumerator.getBin15Layouts()[0];HashLayoutEncoder encoder = new HashLayoutEncoder(first);int[] JD = new int[encoder.bmTotal]; //节点字典codeSnMap = new int[encoder.bmTotal];while ((enumerator != null)) {int[][] layouts = enumerator.getBin15Layouts();for (int i = 0; i < layouts.length; i++) {int code = encoder.encode(layouts[i]);if (JD[code] == 0) {JD[code] = 1;codeSnMap[code] = count;layoutMap[count] = layouts[i];} else {System.out.println("error! detected duplicate layout, count: " + count +", code: " + code);}count++;}enumerator = enumerator.next();}System.out.println(String.format("%d横式共有%d节点", hCount, count));flagMap = new int[count];
// } //for}public void test(int hCount) {init(hCount);int solvableCount = 0;int playableCount = 0;ArrayList trees = new ArrayList<>();int[] curLayout = getUnSearchedLayout();while (curLayout != null) {HrdNode tree = find(curLayout);trees.add(tree);
// System.out.println("found tree: " + tree.nodeNum + ", remain: " + getUnsearchedCount()
// + ", solvable: " + tree.outable);if (tree.outable) {solvableCount++;if (tree.nodeNum > 500) {playableCount++;}
// System.out.print(LayoutEnumerator.getPrintLayout2(tree.layout, trees.size()));
// System.out.println("found tree: " + tree.nodeNum + ", remain: " + getUnsearchedCount());}curLayout = getUnSearchedLayout();}System.out.println(String.format("%d横式共有%d颗树, 其中%d个树有解, %d个树可玩性好",hCount, trees.size(), solvableCount, playableCount));}private void markSearched(int code) {if (code >= 0) {int serialNum = codeSnMap[code];flagMap[serialNum] = 1;}}private int[] getUnSearchedLayout() {for (int i = 0; i < flagMap.length; i++ ) {if (flagMap[i] != 1) {return layoutMap[i];}}return null;}private int getUnsearchedCount() {int count = 0;for (int i = 0; i < flagMap.length; i++ ) {if (flagMap[i] != 1) {count++;}}return count;}
} package game.hrd.game.hrd.refactor;import java.util.ArrayList;/*** Created by huangcongjie on 2017/12/20.*/
public class Solver {HrdNode[] queue;int searchAmount = 0;int processingIndex = 0;int maxAmount = 500000;private void addToQueue(HrdNode node) {if (searchAmount >= maxAmount) {System.out.println("对溢出");return;}queue[searchAmount] = node;searchAmount++;}//--广度优先--public int bfs(int[] layout, boolean useHash) {
// System.out.println("use hash checker: " + useHash);long t1 = System.currentTimeMillis();long cost = 0;IAnalyzer analyzer = new HashLayoutAnalyzer();HrdNode root = new HrdNode(layout, analyzer, useHash);IChecker checker = useHash ? new LayoutToHash() : new LayoutToCode(root.layout);if (useHash) {maxAmount = 40 * 1024;} else {maxAmount = ((LayoutToCode) checker).codeTotalNum / 10;}queue = new HrdNode[maxAmount];HrdNode curNode = root;addToQueue(root);while (processingIndex < searchAmount) {
// System.out.println("searchAmount: " + searchAmount);HrdNode answer = curNode.giveBirth(checker, new IListener() {@Overridepublic void validNodeCreated(HrdNode child) {addToQueue(child);}});if (answer != null) {cost = System.currentTimeMillis() - t1;System.out.println("found answer! total steps: " + answer.level + " cost: " + cost + "ms");if (checker instanceof LayoutToHash) {System.out.println("hash conflicts: " + ((LayoutToHash) checker).cht );}
// displaySolution(answer);return 1;}processingIndex++;curNode = queue[processingIndex];}cost = System.currentTimeMillis() - t1;System.out.println("already searched all nodes, cannot found answer! cost: " + cost + "ms");return 0;}public int reachable(int[] layout1, int[] layout2) {long t1 = System.currentTimeMillis();long cost = 0;IAnalyzer analyzer = new HashLayoutAnalyzer();HrdNode root = new HrdNode(layout1, analyzer, false);LayoutToCode checker = new LayoutToCode(root.layout);int dstCode = checker.encode(layout2);root.setGoal(dstCode);maxAmount = checker.codeTotalNum / 10;queue = new HrdNode[maxAmount];HrdNode curNode = root;addToQueue(root);while (processingIndex < searchAmount) {
// System.out.println("searchAmount: " + searchAmount);HrdNode answer = curNode.giveBirth(checker, new IListener() {@Overridepublic void validNodeCreated(HrdNode child) {addToQueue(child);}});if (answer != null) {cost = System.currentTimeMillis() - t1;System.out.println("found answer! total steps: " + answer.level + " cost: " + cost + "ms");displaySolution(answer);return 1;}processingIndex++;curNode = queue[processingIndex];}cost = System.currentTimeMillis() - t1;System.out.println("already searched all nodes, cannot found answer! cost: " + cost + "ms");return 0;}public interface IListener {void validNodeCreated(HrdNode child);}private void displaySolution(HrdNode hrdObj) {ArrayList list = new ArrayList<>();list.add(hrdObj);HrdNode node = hrdObj;while (node.parent != null) {list.add(node.parent);node = node.parent;}for (int i = list.size() - 1; i >= 0; i--) {displayStep(list.get(i));}}private void displayStep(HrdNode hrdObj) {System.out.println("第" + hrdObj.level + "步");int[] layout = hrdObj.isHashLayout() ? HrdUtil.convertToScreen(hrdObj.layout) :hrdObj.layout;for (int i = 0; i < layout.length; i += 4) {System.out.println(String.format("%d\t%d\t%d\t%d", layout[i], layout[i+1], layout[i+2], layout[i+3]));}System.out.println();}
} 测试代码
public class TestHrdEnumerator {public static void main(String args[]) {
// testBin15Layouts();
// testPmHx();
// testEncoder();
// testLayoutEncoder();for (int i = 0; i < 6; i++) {TreeFinder treeFinder = new TreeFinder();treeFinder.test(i);}
// testReachable();}public static void testBin15Layouts() {int hCount = 1;LayoutEnumerator enumerator = new LayoutEnumerator(hCount);int count = 0;System.out.print(enumerator.getPrintLayout(enumerator.getLayout(), count));int[][] layouts = enumerator.getBin15Layouts();for (int i = 0; i < layouts.length; i++) {count++;System.out.print(LayoutEnumerator.getPrintLayout(layouts[i], count));}}public static void testPmHx() {int hCount = 1;LayoutEnumerator enumerator = new LayoutEnumerator(hCount);int count = 0;System.out.print(enumerator.getPrintLayout(enumerator.getLayout(), count));PmHx hx = new PmHx();while ((enumerator != null)) {int[][] layouts = enumerator.getBin15Layouts();for (int i = 0; i < layouts.length; i++) {count++;if ( hx.check(layouts[i]) != 1 ) {System.out.println("error! detected duplicate layout, count: " + count);}}enumerator = enumerator.next();}System.out.println(String.format("%d横式共有%d节点, 发生哈希冲突%d", hCount, count, hx.cht));}public static void testEncoder() {
// int[] qp = {
// 6, 15, 15, 7,
// 6, 15, 15, 7,
// 8, 11, 11, 5,
// 8, 3, 4, 5,
// 2, 0, 0, 1
// };
// int[] qp = {
// 6, 15, 15, 7,
// 6, 15, 15, 7,
// 3, 11, 11, 5,
// 4, 10, 10, 5,
// 2, 0, 0, 1
// };
// int[] qp = {
// 10, 10, 5, 7,
// 11, 11, 5, 7,
// 12, 12, 3, 4,
// 15, 15, 1, 2,
// 15, 15, 0, 0
// };int[] qp = {8, 6, 5, 7,8, 6, 5, 7,1, 2, 3, 9,15, 15, 4, 9,15, 15, 0, 0};PmBm pmBm = new PmBm(qp);
// int code1 = pmBm.Bm(qp);int[] qp2 = HrdUtil.convertToHashLayout(qp);HashLayoutEncoder encoder = new HashLayoutEncoder(qp2);
// int code2 = encoder.encode(qp2);
// System.out.println(code1 + " == " +code2);int[] qp3 = {5, 5, 3, 3,1, 1, 1, 1,3, 3, 2, 2,1, 1, 2, 3,2, 0, 0, 1};int[] qp4 = {5, 5, 3, 3,1, 1, 1, 1,3, 2, 3, 2,1, 2, 1, 3,2, 0, 0, 1};int[] n1 = HrdUtil.hashLayoutConvertToNormal(qp3);int code4 = pmBm.Bm(n1);int code3 = encoder.encode(qp3);int code2 = encoder.encode(qp4);System.out.println(code3 + " != " +code2 + ", " + code4 + " == " + code3);}public static void testLayoutEncoder() {for (int m = 0; m < 6; m++) {int hCount = m;LayoutEnumerator enumerator = new LayoutEnumerator(hCount);int count = 0;System.out.print(enumerator.getPrintLayout(enumerator.getLayout(), count));int[] first = enumerator.getBin15Layouts()[0];HashLayoutEncoder encoder = new HashLayoutEncoder(first);PmBm pmBm = new PmBm(HrdUtil.hashLayoutConvertToNormal(first));int[] JD = new int[encoder.bmTotal]; //节点字典while ((enumerator != null)) {int[][] layouts = enumerator.getBin15Layouts();for (int i = 0; i < layouts.length; i++) {count++;int code = encoder.encode(layouts[i]);
// int[] normalLayout = HrdUtil.hashLayoutConvertToNormal(layouts[i]);
// int code = pmBm.Bm(normalLayout);if (JD[code] == 0) {JD[code] = 1;} else {System.out.println("error! detected duplicate layout, count: " + count +", code: " + code);}}enumerator = enumerator.next();}System.out.println(String.format("%d横式共有%d节点", hCount, count));}}static public String toLayoutString(int[] layout2) {String layout = "";for (int i = 0; i < 20; i++) {layout += layout2[i];if (i % 4 == 3) {layout += ",|";} else {layout += ", ";}}layout = layout.substring(0, layout.length() - 2);return layout;}static public void testReachable() {int[] qp1 = {5, 5, 4, 4,1, 1, 3, 3,3, 3, 1, 1,1, 1, 2, 2,2, 2, 0, 0};int[] qp2 = {5, 5, 3, 3,1, 1, 1, 1,4, 4, 3, 3,2, 2, 1, 1,2, 2, 0, 0};Solver solver = new Solver();solver.reachable(qp1, qp2);}
}最终结果，
5 5 3 3
1 1 1 1
3 3 3 0
1 1 1 0
0 0 0 0
---------0-----------0横式共有15660节点
0横式共有80颗树, 其中1个树有解, 1个树可玩性好
5 5 4 4
1 1 3 3
3 3 1 1
1 1 0 0
0 0 0 0
---------0-----------1横式共有65880节点
1横式共有898颗树, 其中52个树有解, 2个树可玩性好
5 5 4 4
1 1 4 4
3 3 3 0
1 1 1 0
0 0 0 0
---------0-----------2横式共有109260节点
2横式共有2653颗树, 其中230个树有解, 1个树可玩性好
5 5 4 4
1 1 4 4
4 4 3 3
0 0 1 1
0 0 0 0
---------0-----------3横式共有106800节点
3横式共有2609颗树, 其中146个树有解, 1个树可玩性好
5 5 4 4
1 1 4 4
4 4 4 4
3 0 0 0
1 0 0 0
---------0-----------4横式共有51660节点
4横式共有1729颗树, 其中107个树有解, 1个树可玩性好
5 5 4 4
1 1 4 4
4 4 4 4
4 4 0 0
0 0 0 0
---------0-----------5横式共有14220节点
5横式共有505颗树, 其中19个树有解, 1个树可玩性好“可玩性好”表示树的节点不能少于500个，不然就太简单了。
对于任意一颗华容道的树，如何找到一种节点布局，使得以此节点为根，生成的树，层数最少？
如何找到另有一种节点，使得以此节点为根，生成的树，层数最多？
这两个问题是新的坑，太闲了再来研究，
联系邮箱: hcj_xhu@qq.com
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！