Question

求高手解答java编程问题

有三个白子和三个黑子如下图布置：
○ ○ ○ ● ● ●
用最少的步数将上图中白子和黑子的位置进行交换：
● ● ● ○ ○ ○
规则是：
（1）一次只能移动一个棋子；
（2）棋子可以向空格中移动，也可以跳过一个对方的棋子进入空格，但不能向后跳，也不能跳过两个子。
（本题共60分，要求1占30分，要求2占30分）
要求：
（1）分析问题，找出规律，总结出规则和算法，并描述你的算法设计思想。
（2）编程显示每一步交换过程。
白子和黑子之间有一个空位的，没有显示出来，不好意思啊

Answer 1

/**
* 黑白棋程序入口
*
* @author skr
*
*/
public class HeiBaiQi {

public static void main(String[] args) {
new Run().run();
}
}

/**
* 棋子类,基类
*
* @author skr
*
*/
abstract class QiZi {
/**
* 棋子编号
*/
public int number;

/**
* 棋子所在位置
*/
public int index;

public abstract boolean move(StringBuilder chessboard);
}

/**
* 黑子类继承棋子类
*
* @author skr
*
*/
class HeiZi extends QiZi {

public HeiZi(int num) {
number = num;
}

/**
* 黑子移动方法
*/
public boolean move(StringBuilder chessboard) {
boolean flag = true;
int sIndex = chessboard.indexOf("s");
if (sIndex == index - 1 || sIndex == index - 2) {
chessboard.setCharAt(index, 's');
chessboard.setCharAt(sIndex, 'b');
index = sIndex;
} else
flag = false;
if (chessboard.toString().equals(Run.chessboardEnd))
Run.flag = true;
String strFlag = flag ? "成功" : "失败";
System.out.println("尝试路径：" + Run.routeStr + number + "\t" + chessboard
+ "\t" + strFlag);
return flag;
}
}

/**
* 白子类继承棋子类
*
* @author skr
*
*/
class BaiZi extends QiZi {

public BaiZi(int num) {
number = num;
}

/**
* 白子移动方法
*/
public boolean move(StringBuilder chessboard) {
boolean flag = true;
int sIndex = chessboard.indexOf("s");
if (sIndex == index + 1 || sIndex == index + 2) {
chessboard.setCharAt(index, 's');
chessboard.setCharAt(sIndex, 'w');
index = sIndex;
} else
flag = false;
if (chessboard.toString().equals(Run.chessboardEnd))
Run.flag = true;
String strFlag = flag ? "成功" : "失败";
System.out.println("尝试路径：" + Run.routeStr + number + "\t" + chessboard
+ "\t" + strFlag);
return flag;
}
}

class Run {

/**
* 标志是否找到了最佳路径
*/
public static boolean flag = false;

/**
* 最佳路径字符串
*/
public static StringBuilder routeStr = new StringBuilder();

/**
* 完成时棋盘字符串
*/
public static final String chessboardEnd = "bbbswww";

/**
* 棋盘字符串 b:黑子,s:空格,w:白子
*/
public StringBuilder chessboard = new StringBuilder("wwwsbbb");

/**
* 棋子数组
*/
public QiZi[] qizi = new QiZi[6];

public Run() {
qizi[0] = new BaiZi(0);
qizi[1] = new BaiZi(1);
qizi[2] = new BaiZi(2);
qizi[3] = new HeiZi(3);
qizi[4] = new HeiZi(4);
qizi[5] = new HeiZi(5);
qizi[0].index = 0;
qizi[1].index = 1;
qizi[2].index = 2;
qizi[3].index = 4;
qizi[4].index = 5;
qizi[5].index = 6;

}

/**
* 运行程序，从0步走完开始测试
*/
public void run() {
testRoute();
System.out.println("最佳路径为：" + routeStr);
}

public void testRoute() {
for (int i = 0; i < qizi.length; i++) {
if (flag)
break;
StringBuilder temp = new StringBuilder(chessboard);
int indexTemp = qizi[i].index;
boolean b = qizi[i].move(chessboard);
if (!b)
continue;
if (routeStr.length() != 0
&& i == Integer.parseInt(routeStr.substring(routeStr
.length() - 1)))
continue;
routeStr.append(i);
testRoute();
if (flag)
return;
chessboard = temp;// 还原棋盘
routeStr.deleteCharAt(routeStr.length() - 1);// 还原路径
qizi[i].index = indexTemp;// 还原棋子位置
}
}
}
[楼主，第一版效率较低，我也没时间来考虑优化，仅提供给楼主参考，运行一下几个小时估计可以枚举出结果，楼主可以适当的自己做些优化，比如跳过一些肯定不肯能的情况，可以少很多次迭代，仅供参考，望楼主顺利解决问题 （ 修改了一下，刚才那版有内存溢出的问题）]

经过修改，这个程序效率已经比较高了，上面是我最新修改的，楼主可以拿去试试了
结果（截取）：
尝试路径：23421034521040 bbswbww 失败
尝试路径：23421034521041 bbswbww 失败
尝试路径：23421034521042 bbswbww 失败
尝试路径：23421034521043 bbswbww 失败
尝试路径：23421034521044 bbswbww 失败
尝试路径：23421034521045 bbbwsww 成功
尝试路径：234210345210450 bbbswww 成功
最佳路径为：234210345210450

Answer 2

○ ○ ○ ● ● ●
白1 白2 白3 黑1 黑2 黑3
白3子右移一格
黑1子跳过白3子左移两格 黑2子左移一格
白3子跳过黑2子右移两格 白2子跳过黑1子左移两格 白1子左移1格
黑1子跳过白1子左移两格 黑2子跳过白2子左移两格 黑3子跳过白3子左移两格
白3子右移一格 白2子跳过黑1子右移两格 白1子跳过黑2子右移两格
黑2子右移一格 黑3子跳过白1子右移两格
白1子右移一格
7个位置循环7次 每个循环最多3次
每次移动 1 1 1 0 1 1 1
每次跳动 0 1 2 3 2 1 0

Answer 3

想问下白子与白子之间，黑子与黑子之间有空格吗？还是三个白了紧挨着，三个黑子紧挨着，然后三个白子与三个黑子之间有一个空格。
我想到了一个算法，就是类似冒泡算法这样，先白3右移一格，然后黑1跳过去，这样一直把黑1移到最左边，然后再依次把三个白的左移一格，就形成“黑1白1白2白3空格黑2黑3”这样的情况，然后按上面的继续移动。
但是我不知道是不是最少的移动步骤，如何测试，还没想明白

Answer 4

大致需要15步，如果用我说的那个算法模拟的话得要33个步骤。但是做这个东西有意义吗？没什么必要吧。人工都做出来的再搬到电脑上不是无聊吗？ 我感觉电脑要做的是模拟人工的方法实现大量重复的计算。

Answer 5

不会