使用回溯帮助调试移动数组元素 [英] Help debugging on moving array elements using backtracking
问题描述
嗯，这是我基本上已经解决的一项任务，但是有一些我无法找到的小虫，我想也许你们可以帮助我。
在链接中检查游戏（http://www.clickmazes.com/puffball/ixpuffball.htm），我的程序应接受任何尺寸和坐标，创建游戏，然后尝试查找所有解决方案并打印他们，每个球得到一个从1到数目的数字，并且解决方案给了我们膨胀球的顺序。在执行的明星，它似乎在调试器中正常工作，但如果我在它结束之前随机暂停它，我发现一些球从阵列中丢失，检查移动球的方法，它们似乎工作，所以不知道发生了什么
i认为这个问题可能存在于puffBall（）中：
Well, this is an assignment that i have basically solved, but there is a little bug that i cant manage to find, i though maybe you guys could help me.
Check the game in the link ( http://www.clickmazes.com/puffball/ixpuffball.htm) , my program should accept any dimensions and coordinates, create the game, and then try to find all the solutions and print them, each ball get a number from 1 to numberObjectives, and the solutions give us the order for puffing the balls. At the star of the execution it seems to be working properly in the debugger, but if i randomly pause it before it ends, i find that some balls are lost from the array, checked the methods that move the balls and they seems to work, so no idea what is happening
i think the problem may reside in puffBall():
<pre lang="java">
/**
* Moves the balls that will move when we puff one off them in the array,
* and in the Coordintes[]
*
* @param board
* Board with all the param filled
* @param ball
* Ball we want to puff
* @return board Board we get after puffing ball one time
*/
public static Board puffBall(Board board, int ball) {
board.setValid(false);
Coordinates xy = searchCoordinates(board, ball);
Coordinates[] balls = board.getBalls();
// Moving from the edges to resolve conflict when 2 balls are touching
// each other
// Bottom to Top
for (int i = board.getBoard().length - 1; i > xy.getY(); i--) {
if (board.getBoard()[xy.getX()][i] > -1) {
if (checkValidMovement(board.getBoard(), i + 1, 1)) {
balls[searchBall(board, xy.getX(), i)].setY(i + 1);
board.getBoard()[xy.getX()][i + 1] = searchBall(board, xy.getX(), i) + 1;
board.getBoard()[xy.getX()][i] = -1;
board.setValid(true);
}
}
}
// Top to Bottom
for (int i = 0; i < xy.getY(); i++) {
if (board.getBoard()[xy.getX()][i] > -1) {
if (checkValidMovement(board.getBoard(), i - 1, 1)) {
balls[searchBall(board, xy.getX(), i)].setY(i - 1);
board.getBoard()[xy.getX()][i - 1] = searchBall(board, xy.getX(), i) + 1;
board.getBoard()[xy.getX()][i] = -1;
board.setValid(true);
}
}
}
// Right to Left
for (int i = board.getBoard()[0].length - 1; i > xy.getX(); i--) {
if (board.getBoard()[i][xy.getY()] > -1) {
if (checkValidMovement(board.getBoard(), i + 1, 0)) {
balls[searchBall(board, i, xy.getY())].setX(i + 1);
board.board[i + 1][xy.getY()] = searchBall(board, i, xy.getY()) + 1;
board.board[i][xy.getY()] = -1;
board.setValid(true);
}
}
}
// Left to Right
for (int i = 0; i < xy.getX(); i++) {
if (board.getBoard()[i][xy.getY()] > -1) {
if (checkValidMovement(board.getBoard(), i - 1, 0)) {
balls[searchBall(board, i, xy.getY())].setX(i - 1);
board.getBoard()[i - 1][xy.getY()] = searchBall(board, i, xy.getY()) + 1;
board.getBoard()[i][xy.getY()] = -1;
board.setValid(true);
}
}
}
board.setBalls(balls);
return board;
}
或者可能是回溯方法的错误：
or maybe is a fault of the backtracking method:
/**
* Backtracking method that solves a given board
*
* @param board
* board we want to solve
* @param steps
* steps in our current iteration
* @param solutions
* array of solutions found
*/
public static void solvePuffBall(Board board, ArrayList<Integer> steps, ArrayList<ArrayList<Integer>> solutions) {
if (solve(board, steps)) {
solutions.add(new ArrayList<Integer>(steps));
} else {
for (int i = 1; i <= board.getNumObjectives(); i++) {
steps.add(i);
if (checkPartialSolution(board, steps)) {
solvePuffBall(board, steps, solutions);
}
steps.remove(steps.size() - 1);
}
}
}
/**
* Check if the given steps give us a partial solution
*
* @param board
* board we want to check
* @param steps
* steps to try
* @return boolean true if is a partial solution, false otherwise
*/
public static boolean checkPartialSolution(Board board, ArrayList<Integer> steps) {
Board aux = new Board(board);
ArrayList<Board> states = new ArrayList<Board>();
states.add(board);
for (int i : steps) {
aux = puffBall(aux, i - 1);
if (!aux.getValid()) {
return false;
} else if (checkValidPosition(aux)) {
return false;
} else if (states.contains(aux)) {
return false;
} else {
states.add(new Board(aux));
}
}
return true;
}
以下是完整代码：http：//pastebin.com/Wi0ryPGz
Here is the complete code: http://pastebin.com/Wi0ryPGz
推荐答案
我发现有些球从阵列中丢失了
i find that some balls are lost from the array
所以你知道你在代码中的某些地方丢失了一些球。
解决方案是找到问题附加的位置和时间，以缩小调试范围。
为此，你必须制作一段代码，检查你是否丢球。
自一切似乎都在起作用，你需要找到它何时出错。
这样做，你创建一个变量来计算已完成的步数。
每次增加变量时，检查是否丢失了球，如果是，则打印步骤编号并结束程序。
然后在调试器中重新运行程序并告诉调试器在你开始调试时达到步数减1.
当调试器触发时，问题出现在下一步。
So you know you are loosing some balls some where in your code.
The solution is to locate where and when the problem appends, in order to narrow the debugging.
To do so, you have to make a piece of code that check if you have lost balls or not.
Since all seems to work at first, you need to locate when it go wrong.
to do so, you create a variable that will count how many steps have been done.
and every times you increment the variable, you check if you lost balls, if so, print the step number and end the program.
then rerun the program in debugger and tell the debugger to start debugging when you reach the step number minus 1.
When the debugger fires, the problem occurs in next step.
这篇关于使用回溯帮助调试移动数组元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
