Peg Solitaire回溯无限循环
Peg Solitaire回溯无限循环
提问于 2015-10-24 18:30:19
我正在用java做一个带回溯的peg solitaire解析器。
这是我做过的方法：
private void solve(Board board, ArrayList<Movement> solution, Boolean result) {
ArrayList<Movement> movs = board.getMovements();
for (Movement movement : movs) {
if (board.isMovementValid(movement)) {
board.doMovement(movement);
if(!board.isSolution()) {
solution.add(movement);
solve(board, solution, result);
result.setValue(false);
} else {
result.setValue(true);
}
}
}
result.setValue(false);
}问题是我找不到解决方案。以下是代码的输出：http://pastebin.com/raw.php?i=BhkLu3qr。正如您所看到的，解决方案数组是不完整的。
谢谢。
回答 2
Stack Overflow用户
发布于 2015-10-24 18:42:49
不是很优雅，但为了回溯和重试替代方案，必须后退一步：
ArrayList<Movement> movs = board.getMovements();
for (Movement movement : movs) {
if (board.isMovementValid(movement)) {
board.doMovement(movement);
solution.add(movement);
if(!board.isSolution()) {
solve(board, solution, result);
// Initialized to result.setValue(false);
if (result.getValue()) { return; }
} else {
result.setValue(true);
return;
}
solution.remove(movement);
board.undoMovement(movement);
}
}
result.setValue(false);此外，对于更一般的解决方案，您对第一个解决方案感到满意，我添加了返回。
Stack Overflow用户
发布于 2015-10-25 22:26:12
假设您的board.getMovements()方法为您提供了从游戏中的这一点开始的所有可能走法的列表，那么您就快要完成了。你只需要在你赢的时候停下来。为了清晰起见，我在bit上进行了重构。
private boolean solve(Board board, ArrayList<Movement> solution) {
// The base case: if it's already solved, we're done
if (board.isSolution())
return true;
// Get all possible moves from this point
ArrayList<Movement> movs = board.getMovements();
for (Movement movement : movs) {
if (board.isMovementValid(movement)) {
board.doMovement(movement);
solution.add(movement);
if (solve(board, solution))
// That move led to success :-)
return true;
else
// That move led to failure :-(
solution.remove(movement);
}
}
return false;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33317155
复制相关文章
相似问题
腾讯云开发者
