重构华容道自动求解

之前的关于华容道自动求解的代码，变量名的命名很不规范，结构也不太容易理解，过一段时间后，重新来看，又会不知道以前的代码的意思了，明明之前已经看懂，结果现在又不懂了，很浪费时间。所以，应该自己再来针对代码的可读写进行重构。

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 = Integer.MAX_VALUE; 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 = useHash ? new HashLayoutAnalyzer() : new LayoutAnalyzer(); 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() { @Override public 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 interface IListener { void validNodeCreated(HrdNode child); } private void displaySolution(HrdNode hrdObj) { ArrayList<HrdNode> 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(); } } package game.hrd.game.hrd.refactor; /** * Created by huangcongjie on 2017/12/20. */ public interface IAnalyzer { void analyze(HrdNode hrdLayout); void step(int[] layout, int src, int dst); } package game.hrd.game.hrd.refactor; /** * Created by huangcongjie on 2017/12/20. */ public interface IChecker { //return true if layout is unique, first appear boolean checkAndModify(int[] layout); } package game.hrd.game.hrd.refactor; import game.hrd.ZBD; /** * Created by huangcongjie on 2017/12/20. */ public class LayoutToHash implements IChecker { private long[] hsb; private long[] hsb2; public int cht; //哈希冲突次数 //使用128k(17位)哈希表,如果改用更大的表,相应的哈希计算位数也要改 static private final int hSize = 128 * 1024; public int count = 0; public LayoutToHash() { hsb = new long[hSize + hSize/4 + 64]; hsb2 = new long[hsb.length / 4]; cht = 0; } @Override public boolean checkAndModify(int[] layout) { if (check(layout) == 1) { symmetricCheck(layout); return true; } return false; } public int check(int[] layout) { // count++; //生成散列参数n1,n2,m0 //以下参数生成算法不保证参数与棋盘的唯一对应关系,因此理论上存在哈希表冲突判断错误的可能 //只不过产生错误的可能性几乎可能完全忽略 int[] p = ZBD.layoutCompress(layout); long n1 = ( ( p[1] << 3 )+ (p[2] << 5) + p[0]); //每次折叠时都应充分发挥各子作用,增强散列 long n2 = ( ( p[3] << 1) + (p[4] << 4) ); long m0 = (n2 << 6) ^ (n1 << 3); //增强散列参数 //第一哈希处理 long h1 = ( n1 + n2 + m0 ) & 0x0000ffffffffL; long h = (( h1 & 0x0001FFFF ) ^ ( h1 >> 17 )) & 0x0000ffffffffL; int h0 = (int) h; // if (count < 1000) // System.out.println("PmHx check count: " + count + ", h: " + h0); for (int i = 0; i < 2; i++) { if (hsb[h0] == 0) { //从未出现过的布局 hsb[h0] = h1; return 1; } if (hsb[h0] == h1) { //已经出现过的布局 return 0; } //有哈希冲突 h0++; } //多次查表,最多32次 //第二哈希处理 h1 = (n1 - n2 + m0) & 0x0000ffffffffL; h = (( h1 & 0x00007FFF ) ^ ( h1 >> 19 )) & 0x0000ffffffffL; h0 = (int) h; for(int i = 0; i < 10; i++) { if (hsb2[h0] == 0) { hsb2[h0] = h1; return 1; } if (hsb2[h0] == h1) { return 0; } h0++; } //首次查表 cht++; //哈希冲突计数(通过5次哈希,一般情况下冲突次数为0) return 1; } //按左右对称规则考查棋盘,并记录到哈希表 public void symmetricCheck(int[] q20) { int[] p20 = new int[20]; for (int i = 0; i < 20; i+= 4) { p20[i] = q20[i+3]; p20[i+1] = q20[i+2]; p20[i+2] = q20[i+1]; p20[i+3] = q20[i]; } check(p20); } } package game.hrd.game.hrd.refactor; import game.hrd.LocalConst; /** * Created by huangcongjie on 2017/12/20. */ //盘面编码类 public class LayoutToCode implements IChecker { //组合序号表 short[] Hz; //横将 short[] Sz; //竖将 short[] Bz; //小兵 //权值表 int[] Hw; int[] Sw; int[] Mw; public int codeTotalNum; int[] JD; //节点字典 public LayoutToCode(int[] layout) { Hz = new short[4096 * 3]; Sz = new short[4096]; Bz = new short[128]; //C12取5=792 Hw = 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(LocalConst.U[layout[i]]=='B') Bn++; if(LocalConst.U[layout[i]]=='H') Hn++; if(LocalConst.U[layout[i]]=='C') Sn++; } Hn /= 2; Sn /= 2; int[] WQ2 = LocalConst.WQ2; int Hmax=WQ2[11],Smax=WQ2[12-Hn*2],Bmax=WQ2[16-(Hn+Sn)*2]; //各种子的最大二进位数 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 && i<Hmax) { Hz[i] = Hx++; } if(k==Sn && i<Smax) { Sz[i]=Sx++; } if(k==Bn && i<Bmax) { Bz[i]=Bx++; } } int 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<Hx;i++) Hw[i]=i*Hq; //初始化横将权值表 for(i=0;i<Sx;i++) Sw[i]=i*Sq; //初始化竖将权值表 codeTotalNum = Mq*12; JD = new int[codeTotalNum]; } @Override public boolean checkAndModify(int[] layout) { int code = encode(layout); if (JD[code] == 0) { // js2++; //js搜索总次数计数和js2遍历的实结点个数 JD[code] = 1; int symmetricCode = symmetricEncode(layout); JD[symmetricCode] = 1; return true; } return false; } //盘面编码 private int encode(int[] layout) { int Bb=0,Bd=-1; //小兵序号记录器 int Sb=0,Sd=-1; //竖条序号记录器 int Hb=0,Hd=-1; //横条序号记录器 int Mb = 0; //大王序号记录器 int c,lx; int[] f = new int[16]; for(int i = 0; i < 20; i++){ c=layout[i]; lx = LocalConst.U[c]; //当前的值 if(lx=='M') { //大王定序 if(f[c] == 0) { Mb = i - LocalConst.ROW[i]; f[c] = 1; } continue; } if (LocalConst.COL[i]<3 && LocalConst.U[layout[i+1]] <= 'H') { Hd++; //横条位置序号(编号) } if (lx == 'H') {//横将定序,转为二进制进行询址得Hb if(f[c] == 0) { Hb += LocalConst.WQ2[Hd]; f[c]=1; } continue; } if (LocalConst.ROW[i]<4 && LocalConst.U[layout[i+4]]<='C') { Sd++; //竖将位置序号(编号) } if (lx=='C') { //竖条定序,转为二进制进行询址得Sb if(f[c] == 0) { Sb += LocalConst.WQ2[Sd]; f[c]=1; } continue; } if(lx<='B') Bd++; //小兵位置序号(编号) if(lx=='B') Bb += LocalConst.WQ2[Bd]; //小兵定序,转为二进制进行询址得Bb } //Hb,Sb,Bb为组合序号,"横刀立马"最大值为小兵C(6,4)-1=15-1,竖条C(10,4)-1=210-1 Bb=Bz[Bb]; Sb=Sz[Sb]; Hb=Hz[Hb];//询址后得得Bb,Sb,Hb组合序号 return Bb+Sw[Sb]+Hw[Hb]+Mw[Mb]; //用位权编码,其中Bb的位权为1 } //按左右对称规则考查棋盘,对其编码 private 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); } } package game.hrd.game.hrd.refactor; import game.hrd.LocalConst; /** * Created by huangcongjie on 2017/12/20. */ public class LayoutAnalyzer implements IAnalyzer { @Override public void analyze(HrdNode hrdLayout) { int i,col,k1=0,k2=0,h=0; //i,列,空格1位置,空格2位置,h为两空格的联合类型 int c,lx; //f[]记录已判断过的棋字 int[] f = new int[16]; hrdLayout.totalChoices=0; //计步复位 int[] layout = hrdLayout.layout; for(i=0; i<20; i++){ if(layout[i] == 0) { k1=k2; k2=i; //查空格的位置 } } if (k1 + 4 == k2) { h = 1; //空格竖联合 } if (k1 + 1 == k2 && LocalConst.COL[k1] < 3) { h = 2; //空格横联合 } for (i = 0; i < 20; i++) { c = layout[i]; lx = LocalConst.U[c]; col = LocalConst.COL[i]; if (f[c] == 1) { continue; } switch (lx) { case 'M'://曹操可能的走步 if (i + 8 == k1 && h == 2) { //向下 hrdLayout.addChoice(i, i + 4); } if (i - 4 == k1 && h == 2) { //向上 hrdLayout.addChoice(i, i - 4); } if (col < 2 && i + 2 == k1 && h == 1) { //向右 hrdLayout.addChoice(i, i + 1); } if (col > 0 && i - 1 == k1 && h == 1) { //向左 hrdLayout.addChoice(i, i - 1); } f[c] = 1; break; case 'H': //关羽可能的走步 if (i + 4 == k1 && h == 2) { hrdLayout.addChoice(i, i + 4); } if (i - 4 == k1 && h == 2) { hrdLayout.addChoice(i, i - 4); } if (col < 2 && (i + 2 == k1 || i + 2 == k2)) { hrdLayout.addChoice(i, i + 1); if (h == 2) { hrdLayout.addChoice(i, k1); } } if (col > 0 && (i - 1 == k1 || i - 1 == k2)) { hrdLayout.addChoice(i, i - 1); if (h == 2) { hrdLayout.addChoice(i, k1); } } f[c] = 1; break; case 'C': //张飞,马超,赵云,黄忠可能的走步 if (i + 8 == k1 || i + 8 == k2) { hrdLayout.addChoice(i, i + 4); if (h == 1) { hrdLayout.addChoice(i, k1); } } if (i - 4 == k1 || i - 4 == k2) { hrdLayout.addChoice(i, i - 4); if (h == 1) { hrdLayout.addChoice(i, k1); } } if (col < 3 && i + 1 == k1 && h == 1) { hrdLayout.addChoice(i, i + 1); } if (col > 0 && i - 1 == k1 && h == 1) { hrdLayout.addChoice(i, i - 1); } f[c] = 1; break; case 'B': if (i + 4 == k1 || i + 4 == k2) { if (h > 0) { hrdLayout.addChoice(i, k1); hrdLayout.addChoice(i, k2); } else { hrdLayout.addChoice(i, i + 4); } } if (i - 4 == k1 || i - 4 == k2) { if (h > 0) { hrdLayout.addChoice(i, k1); hrdLayout.addChoice(i, k2); } else { hrdLayout.addChoice(i, i - 4); } } if (col < 3 && (i + 1 == k1 || i + 1 == k2)) { if (h > 0) { hrdLayout.addChoice(i, k1); hrdLayout.addChoice(i, k2); } else { hrdLayout.addChoice(i, i + 1); } } if (col > 0 && (i - 1 == k1 || i - 1 == k2)) { if (h > 0) { hrdLayout.addChoice(i, k1); hrdLayout.addChoice(i, k2); } else { hrdLayout.addChoice(i, i - 1); } } break; } } } //走一步函数 @Override public void step(int[] layout, int src, int dst) { int c = layout[src]; int lx = LocalConst.U[c]; switch(lx) { case 'B': layout[src] = 0; layout[dst] = c; break; case 'C': layout[src] = layout[src+4] = 0; layout[dst] = layout[dst+4] = c; break; case 'H': layout[src] = layout[src+1]=0; layout[dst] = layout[dst+1]=c; break; case 'M': layout[src] = layout[src+1]= layout[src+4]=layout[src+5]=0; layout[dst] = layout[dst+1]= layout[dst+4]=layout[dst+5]=c; break; } } } 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:横联合} @Override public 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); } } } //走一步函数 @Override public 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; /** * Created by huangcongjie on 2017/12/20. */ 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 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 (isHashLayout) { return layout[13] == 5 && layout[14] == 5; } return layout[17] == 15 && layout[18] == 15; } 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 giveBirth HrdNode child = new HrdNode(childLayout, analyzer, isHashLayout); child.parent = this; child.level = this.level + 1; child.setPreMovedIndex(dstArr[i]); if (listener != null) { listener.validNodeCreated(child); if (child.isGoal()) { return 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; /** * Created by huangcongjie on 2017/12/20. */ public class HrdUtil { /** * * @param layout int array which contains 20 integers * @return an array only contains 5 integers */ static public int[] layoutCompress5(int[] layout) { int[] ret = new int[5]; for (int i = 0; i < 5; i++) { int a = i * 4; ret[i] = layout[a] | (layout[a+1] << 8) | (layout[a+2] << 16) | (layout[a+3] << 24); } return ret; } // int[] layout = { // 6, 15, 15, 7, // 6, 15, 15, 7, // 8, 11, 11, 5, // 8, 3, 4, 5, // 2, 0, 0, 1 // }; // int[] ret = { // 3, 5, 5, 3, // 1, 1, 1, 1, // 3, 4, 4, 3, // 1, 2, 2, 1, // 2, 0, 0, 2 // }; //layout 用1-15表示各棋子,空位用0表示,兵1-4,竖将5-9,横将10-14,大王15 static public int[] convertToHashLayout(int[] layout) { int[] ret = new int[20]; //用1-15表示各棋子,空位用0表示,兵1-4,竖将5-9,横将10-14,大王15 for (int i = 0; i < layout.length; i++) { int cur = layout[i]; if (cur == 15) { if (i-4 >= 0 && ret[i-4] == 5) { ret[i] = 1; } else { ret[i] = 5; } } else if (cur >= 10 && cur <= 14) { ret[i] = 4; } else if (cur >= 5 && cur <= 9) { if (i-4 >= 0 && ret[i-4] == 3) { ret[i] = 1; } else { ret[i] = 3; } } else if (cur >= 1 && cur <= 4) { ret[i] = 2; } else { ret[i] = cur; //空格 } } return ret; } static public int[] convertToScreen(int[] hashLayout) { int[] ret = new int[20]; for (int i = 0; i < hashLayout.length; i++) { int cur = hashLayout[i]; if (cur == 1) { ret[i] = hashLayout[i-4]; } else { ret[i] = hashLayout[i]; } } return ret; } static public int[] copy(int[] layout) { int[] ret = new int[layout.length]; for (int i = 0; i < layout.length; i++) { ret[i] = layout[i]; } return ret; } } package game.hrd; public class LocalConst { //用1-15表示各棋子,空位用0表示,兵1-4,竖将5-9,横将10-14,大王15 //大王只能1个,将必须5个(横竖合计),兵必须为4个 // static final public String U = "ABBBBCCCCCHHHHHM"; static final public int[] U = {'A','B','B','B','B','C','C','C','C','C','H','H','H','H','H','M'}; static final public int[] COL = {0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3}; //列号表 static final public int[] ROW = {0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4}; //行号表 static final public int[] WQ2 = {1,2,4,8,16, 32,64,128,256,512, 1024,2048,4096}; //二进制位权表(12个) //使用128k(17位)哈希表,如果改用更大的表,相应的哈希计算位数也要改 static final public int hsize = 128 * 1024; static final public String[] layoutNames = {"横刀立马", "指挥若定", "将拥曹营", "齐头并进", "兵分三路", "雨声淅沥", "左右布兵", "桃花园中", "一路进军", "一路顺风", "围而不歼", "捷足先登", "插翅难飞", "殊途同归", "守口如瓶1", "守口如瓶2", "双将挡路", "横马当关", "层层布防", "兵将联防", "兵挡将阻", "堵塞要道", "瓮中之鳖", "层峦叠嶂", "水泄不通", "四路进兵", "入地无门", "勇闯五关", "四面楚歌", "前呼后拥", "兵临曹营", "五将逼宫", "前挡后阻", "近在咫尺", "走投无路", "比翼横空", "夹道藏兵", "屯兵东路", "四将连关", "峰回路转"}; static final public int[][] allLayouts = {{ //横刀立马, 1横4竖，难度81 6, 15, 15, 7, 6, 15, 15, 7, 8, 10, 10, 5, 8, 3, 4, 5, 2, 0, 0, 1 }, { //指挥若定，1横4竖，70 6, 15, 15, 7, 6, 15, 15, 7, 2, 10, 10, 1, 8, 3, 4, 5, 8, 0, 0, 5 }, { //将拥曹营，1横4竖 72 0, 15, 15, 0, 6, 15, 15, 7, 6, 8, 5, 7, 1, 8, 5, 2, 10, 10, 3, 4 }, { //齐头并进，1横4竖 60 6, 15, 15, 7, 6, 15, 15, 7, 4, 3, 2, 1, 8, 10, 10, 5, 8, 0, 0, 5 }, { //兵分三路，1横4竖 72 1, 15, 15, 2, 6, 15, 15, 7, 6, 10, 10, 7, 8, 3, 4, 5, 8, 0, 0, 5 }, { //雨声淅沥，1横4竖 47 6, 15, 15, 4, 6, 15, 15, 3, 8, 10, 10, 5, 8, 7, 0, 5, 2, 7, 0, 1 }, { //左右布兵，1横4竖 54 1, 15, 15, 3, 2, 15, 15, 4, 8, 6, 7, 5, 8, 6, 7, 5, 0, 10, 10, 0 }, { //桃花园中，1横4竖 70 1, 15, 15, 3, 8, 15, 15, 5, 8, 6, 7, 5, 2, 6, 7, 4, 0, 10, 10, 0 }, { //一路进军，1横4竖 58 6, 15, 15, 1, 6, 15, 15, 2, 8, 7, 5, 3, 8, 7, 5, 4, 0, 10, 10, 0 }, { //一路顺风，1横4竖 39 6, 15, 15, 1, 6, 15, 15, 2, 8, 10, 10, 5, 8, 3, 7, 5, 0, 4, 7, 0 }, { //围而不歼，1横4竖 62 6, 15, 15, 1, 6, 15, 15, 2, 8, 10, 10, 3, 8, 7, 5, 4, 0, 7, 5, 0 }, { //捷足先登，1横4竖 32 1, 15, 15, 3, 2, 15, 15, 4, 0, 10, 10, 0, 5, 6, 7, 8, 5, 6, 7, 8 }, { //插翅难飞，2横3竖 62 6, 15, 15, 1, 6, 15, 15, 2, 10, 10, 4, 3, 7, 11, 11, 8, 7, 0, 0, 8 }, { //殊途同归，2横3竖 81 6, 15, 15, 7, 6, 15, 15, 7, 1, 8, 0, 3, 2, 8, 0, 4, 10, 10, 11, 11 }, { //守口如瓶1，2横3竖 81 6, 15, 15, 7, 6, 15, 15, 7, 1, 8, 0, 3, 2, 8, 0, 4, 10, 10, 11, 11 }, { //守口如瓶2，2横3竖 99 2, 15, 15, 4, 6, 15, 15, 7, 6, 8, 0, 7, 2, 8, 0, 4, 10, 10, 11, 11 }, { //双将挡路，2横3竖 73 6, 15, 15, 1, 6, 15, 15, 2, 8, 10, 10, 7, 8, 11, 11, 7, 3, 0, 0, 4 }, { //横马当关，2横3竖 83 6, 15, 15, 7, 6, 15, 15, 7, 10, 10, 11, 11, 3, 8, 0, 4, 2, 8, 0, 1 }, { //层层布防，3横2竖 102 8, 15, 15, 7, 8, 15, 15, 7, 1, 10, 10, 3, 2, 11, 11, 4, 0, 12, 12, 0 }, { //兵将联防，3横2竖 120 1, 15, 15, 3, 8, 15, 15, 7, 8, 10, 10, 7, 2, 11, 11, 4, 0, 12, 12, 0 }, { //兵挡将阻，3横2竖 87 1, 15, 15, 7, 2, 15, 15, 7, 8, 10, 10, 3, 8, 11, 11, 4, 0, 12, 12, 0 }, { //堵塞要道，3横2竖 39 1, 15, 15, 3, 2, 15, 15, 4, 8, 7, 10, 10, 8, 7, 11, 11, 0, 0, 12, 12 }, { //瓮中之鳖，3横2竖 103 8, 15, 15, 7, 8, 15, 15, 7, 10, 10, 11, 11, 1, 12, 12, 3, 2, 0, 0, 4 }, { //层峦叠嶂，3横2竖 98 8, 15, 15, 7, 8, 15, 15, 7, 1, 11, 11, 2, 10, 10, 12, 12, 2, 0, 0, 4 }, { //水泄不通，4横1竖 79 8, 15, 15, 1, 8, 15, 15, 2, 10, 10, 13, 13, 11, 11, 12, 12, 3, 0, 0, 4 }, { //四路进兵，4横1竖 77 1, 15, 15, 3, 2, 15, 15, 4, 8, 0, 10, 10, 8, 0, 11, 11, 13, 13, 12, 12 }, { //入地无门，4横1竖 87 8, 15, 15, 1, 8, 15, 15, 2, 4, 10, 10, 3, 11, 11, 12, 12, 0, 13, 13, 0 }, { //勇闯五关 (调兵遣将)，5横0竖 34 1, 15, 15, 3, 2, 15, 15, 4, 10, 10, 11, 11, 12, 12, 13, 13, 0, 14, 14, 0 }, { //四面楚歌，1横4竖 56 5, 1, 2, 7, 5, 15, 15, 7, 3, 15, 15, 8, 6, 10, 10, 8, 6, 0, 0, 4 }, { //前呼后拥，5横0竖 22 1, 2, 15, 15, 14, 14, 15, 15, 13, 13, 11, 11, 12, 12, 10, 10, 0, 0, 3, 4 }, { //兵临曹营，1横4竖 34 1, 15, 15, 3, 2, 15, 15, 4, 8, 10, 10, 7, 8, 5, 6, 7, 0, 5, 6, 0 }, { //五将逼宫，3横2竖 36 10, 10, 12, 12, 8, 15, 15, 7, 8, 15, 15, 7, 1, 11, 11, 4, 2, 0, 0, 3 }, { //前挡后阻，2横3竖 42 15, 15, 10, 10, 15, 15, 6, 1, 8, 7, 6, 3, 8, 7, 2, 4, 0, 11, 11, 0 }, { //近在咫尺，2横3竖 98 1, 8, 6, 7, 2, 8, 6, 7, 10, 10, 3, 4, 11, 11, 15, 15, 0, 0, 15, 15 }, { //走投无路 (传说此局无解) 0横5竖 5, 15, 15, 7, 5, 15, 15, 7, 9, 6, 1, 8, 9, 6, 2, 8, 3, 0, 0, 4 }, { //比翼横空，4横1竖 28 10, 10, 15, 15, 11, 11, 15, 15, 12, 12, 13, 13, 1, 0, 3, 8, 2, 0, 4, 8 }, { //夹道藏兵，4横1竖 75 15, 15, 1, 8, 15, 15, 2, 8, 10, 10, 11, 11, 12, 12, 13, 13, 3, 0, 0, 4 }, { //屯兵东路，1横4竖 71 15, 15, 8, 7, 15, 15, 8, 7, 10, 10, 1, 2, 6, 5, 3, 4, 6, 5, 0, 0 }, { //四将连关，3横2竖 39 15, 15, 10, 10, 15, 15, 11, 11, 8, 7, 12, 12, 8, 7, 1, 2, 3, 0, 0, 4 }, { //峰回路转 (过完一山又一山)，2横3竖 138 1, 2, 3, 7, 15, 15, 6, 7, 15, 15, 6, 8, 0, 10, 10, 8, 0, 4, 11, 11 }}; }

测试代码

public class HuaRongDao { public static void main(String args[]) { // ZBD.test(); // ZBD_HX.test(); // int[] qp = { // 2, 0, 5, 5, // 2, 3, 1, 1, // 3, 1, 2, 3, // 1, 0, 3, 1, // 4, 4, 1, 2 // }; // PmHx hx = new PmHx(); // hx.check(qp); // int[] qp = { // 6, 15, 15, 7, // 6, 15, 15, 7, // 8, 11, 11, 5, // 8, 3, 4, 5, // 2, 0, 0, 1 // }; // Solver solver = new Solver(); // solver.bfs(qp, false); // Solver solver1 = new Solver(); // int[] hashLayout = HrdUtil.convertToHashLayout(qp); // solver1.bfs(hashLayout, true); for (int i = 0; i < LocalConst.allLayouts.length; i++) { int[] layout = LocalConst.allLayouts[i]; String layoutName = LocalConst.layoutNames[i]; Solver solver = new Solver(); int num = i+1; System.out.println("layout name: " + layoutName + ", num: " + num); // int[] hashLayout = HrdUtil.convertToHashLayout(layout); // solver.bfs(hashLayout, true); solver.bfs(layout, false); } } }