我正在编写一个滑动块求解器，其中有一个块对象列表（其中包含块大小和左上角的位置），以及一个表示托盘的2D数组。无论哪里有块，数组中的那个位置都指向该块对象，否则为null。
在我的求解器中，我生成了尚未看到的可能的动作，将它们散列，然后选择一个要执行的操作（这将更改托盘布局），然后在新的托盘布局上递归调用求解器。如果在我返回呼叫之前没有其他可能的移动布局，则反转最后一个移动并继续检查上一个呼叫，依此类推，直到解决了或者我用尽了移动（无解决方案）为止。
问题是，我移动时遇到了空指针异常。奇怪的是，它仅在多次递归调用之后才会发生。该程序通过几次调用/移动正常运行，然后似乎混乱了。
generateMoves（）通过调用move（）来检查之前是否已看到移动，然后在检查到该移动后将其反转。我认为Null指针在调用move（）之后发生，并且move（）设置为toMove = layout [] []。显然，它正在查找数组中一个不为零的位置，而不是该块的位置。似乎块列表与Tray数组之间存在差异...因为在move（）然后调用setTrayAfterMove（）时会引发异常。我不知道的是为什么它可以对solveHelper（）进行多次递归调用，但随后中断。
import java.io.*;
import java.util.*;
public class Solver {
Tray initial;
Tray goal;
HashSet<Integer> visited;
LinkedList<Integer> movesToSolution; // list of moves leading to solution
int recursionCounter;
boolean isSolved;
public Solver(String initial, String goal) {
this.initial = new Tray(initial);
this.goal = new Tray(this.initial, goal);
visited = new HashSet<Integer>();
movesToSolution = new LinkedList<Integer>();
recursionCounter = 0;
isSolved = false;
}
public void solve() {
if (goal.equals(initial)) {
System.out.println("Solver finished no moves");
return;
}
solveHelper(initial);
if (movesToSolution.isEmpty()) {
System.out.println("No solution");
System.exit(1);
}
printMoves();
System.out.println("Solver finished");
}
private void solveHelper(Tray t) {
Stack<Integer> possibleMoves = new Stack<Integer>();
int lastMoveMade = 0;
if (recursionCounter > 5000 || isSolved) {
return;
}
if (goal.equals(t)) {
isSolved = true;
// movesToSolution.addFirst(lastMoveMade);
return;
}
recursionCounter++;
LinkedList<Integer> movesToAdd = t.generateMoves();
Iterator<Integer> movesIter = movesToAdd.iterator();
while (movesIter.hasNext()) {
possibleMoves.push(movesIter.next());
}
while (!possibleMoves.isEmpty()) {
lastMoveMade = possibleMoves.pop();
boolean isMoved = t.move(lastMoveMade, false);
if (isMoved) {
int moveHash = t.hashCode();
visited.add(moveHash);
solveHelper(t);
}
if (isSolved) {
movesToSolution.addFirst(lastMoveMade);
return;
}
}
t.move(lastMoveMade, true);
return;
}
public void printMoves() {
for (Integer move : movesToSolution) {
System.out.println(move);
}
}
public class Tray {
private int length; // number of rows
private int width; // number of columns
private LinkedList<Block> blocks;
private Block[][] layout;
public Tray(String file) {
blocks = new LinkedList<Block>();
try {
Scanner s = new Scanner(new FileReader(file));
length = s.nextInt();
width = s.nextInt();
layout = new Block[width][length];
while (s.hasNextLine()) {
int l = s.nextInt();
int w = s.nextInt();
int r = s.nextInt();
int c = s.nextInt();
Block b = new Block(l, w, r, c);
blocks.add(b);
for (int blockX = b.col; blockX < b.col + b.width; blockX++) {
for (int blockY = b.row; blockY < b.row + b.length; blockY++) {
layout[blockX][blockY] = b;
}
}
s.nextLine();
// isOK();
}
} catch (FileNotFoundException e) {
System.out.println("File not found");
}
}
public Tray(Tray t, String file) {
blocks = new LinkedList<Block>();
try {
this.length = t.length;
this.width = t.width;
Scanner s = new Scanner(new FileReader(file));
layout = new Block[this.width][this.length];
while (s.hasNextLine()) {
int l = s.nextInt();
int w = s.nextInt();
int r = s.nextInt();
int c = s.nextInt();
Block b = new Block(l, w, r, c);
blocks.add(b);
for (int blockX = b.col; blockX < b.col + b.width; blockX++) {
for (int blockY = b.row; blockY < b.row + b.length; blockY++) {
layout[blockX][blockY] = b;
}
}
s.nextLine();
// isOK();
}
} catch (FileNotFoundException e) {
System.out.println("File not found");
}
}
public void print() {
for (Block b : blocks) {
System.out.println(b.length + " " + b.width + " " + b.col + " "
+ b.row);
}
}
public boolean equals(Object o) {
for (int x = 0; x < this.width; x++) {
for (int y = 0; y < this.length; y++) {
if (this.layout[x][y] != null
&& (((Tray) o).layout[x][y] == null || !((Tray) o).layout[x][y]
.equals(this.layout[x][y]))) {
return false;
}
}
}
return true;
}
public int hashCode() {
// TODO come up with hashcode unique to layout taking in
// consideration block at each coordinate, size of block
int hashCode = 0;
for (Block b : blocks) {
hashCode += (17 * (b.width * b.col)) + (7 * (b.length * b.row));
}
return hashCode;
}
public boolean isOK() {
Block[][] trayChecker = new Block[width][length];
Iterator<Block> blockIter = blocks.iterator();
while (blockIter.hasNext()) {
Block b = blockIter.next();
for (int x = b.col; x < x + b.width; x++) {
for (int y = b.row; y < y + b.length; y++) {
if (trayChecker[x][y] != null) {
throw new IllegalStateException(
"Two blocks cannot be in the same location");
}
if (x < 0 || x > width || y < 0 || y > length) {
throw new IllegalStateException(
"Block must be completely on the board");
}
trayChecker[x][y] = b;
}
}
}
return true;
}
// only returns possible valid moves that haven't been seen before
public LinkedList<Integer> generateMoves() {
LinkedList<Integer> movesToTry = new LinkedList<Integer>();
// TODO: generate moves that haven't been seen
int[] moveDir = { -10, 10, -1, 1 };
for (Block b : blocks) {
for (int m : moveDir) {
if (canMove(b, m)) {
int trayMove = createMove(b, m);
move(trayMove, false);
if (!visited.contains(hashCode())) {
movesToTry.add(trayMove);
}
move(trayMove, true); // reverse the move
}
}
}
return movesToTry;
}
public boolean canMove(Block b, int dir) {
int tmp = Math.abs(dir);
int y = tmp % 10;
int x = tmp / 10;
if (dir < 0) {
x = -x;
y = -y;
}
if ((b.col + x < 0 || b.col + b.width + x > this.width)
|| (b.row + y < 0 || b.row + b.length + y > this.length)) {
return false;
}
if (x == 0) {
for (int xBlock = b.col; xBlock < b.col + b.width; xBlock++) {
if (layout[xBlock][b.row + y] != null) {
return false;
}
// } else if(x > 0 && layout[xBlock][b.row + y + b.length -
// 1] != null) {
// return false;
// }
}
}
if (y == 0) {
for (int yBlock = b.row; yBlock < b.row + b.length; yBlock++) {
if (layout[b.col + x][yBlock] != null) {
return false;
}
// } else if(x > 0 && layout[b.col + x + b.width -
// 1][yBlock] != null) {
// return false;
// }
}
}
return true;
}
// only takes valid input
public boolean move(int moveDirections, boolean reverse) {
Block toMove = null;
if (moveDirections == 0) {
return false;
}
// System.out.println(moveDirections + " " + recursionCounter);
int tmp = Math.abs(moveDirections);
int moveY = tmp % 10;
tmp /= 10;
int moveX = tmp % 10;
tmp /= 10;
int blockY = tmp % 1000;
tmp /= 1000;
int blockX = tmp;
System.out.println(blockX + " + " + blockY);
if (reverse) {
if (moveDirections > 0) {
toMove = layout[blockX + moveX][blockY + moveY];
} else {
toMove = layout[blockX - moveX][blockY - moveY];
}
setTrayAfterMove(toMove, true);
if (moveDirections < 0) {
toMove.col += moveX;
toMove.row += moveY;
} else {
toMove.col -= moveX;
toMove.row -= moveY;
}
setTrayAfterMove(toMove, false);
} else {
toMove = layout[blockX][blockY];
setTrayAfterMove(toMove, true);
if (moveDirections < 0) {
toMove.col -= moveX;
toMove.row -= moveY;
} else {
toMove.col += moveX;
toMove.row += moveY;
}
setTrayAfterMove(toMove, false);
}
return true;
// 256x256
// 1x256 23x256
// 100x01 100x001 100x100
// 1x01 1x001 1x100
// 10x01 10x001 10x100
}
private int createMove(Block b, int dir) {
// multiply b.x to get 8 digits
// multiply bh .y to get 5 digits
int move = b.col * 100000;
move += (b.row * 100);
move += Math.abs(dir);
if (dir < 0) {
move *= -1;
}
return move;
}
private void setTrayAfterMove(Block b, boolean isBeforeMove) {
for (int blockX = b.col; blockX < b.col + b.width; blockX++) {
for (int blockY = b.row; blockY < b.row + b.length; blockY++) {
if(isBeforeMove) {
layout[blockX][blockY] = null;
} else {
layout[blockX][blockY] = b;
}
}
}
}
}
public class Block {
private int length;
private int width;
private int row;
private int col;
public Block(int l, int w, int r, int c) {
length = l;
width = w;
row = r;
col = c;
}
public boolean equals(Block b) {
return this.length == b.length && this.width == b.width
&& this.row == b.row && this.col == b.col;
}
}
public static void main(String[] args) {
if (args.length < 2 || args.length > 3) {
throw new IllegalArgumentException(
"Must have at least 2 and no more than 3 arguments");
}
String initialLayout = args[0];
String goalLayout = args[1];
String debug = "";
if (args.length == 3) {
if (args[0].substring(0, 2).equals("-o")) {
debug = args[0].substring(2, args[0].length());
switch (debug) {
// cases for debugging arguments go here
}
} else {
throw new IllegalArgumentException(
"First argument must start with -o");
}
initialLayout = args[1];
goalLayout = args[2];
}
Solver s = new Solver(initialLayout, goalLayout);
s.solve();
}
}
有人可以看看我的代码吗？也欢迎有关如何提高效率的建议。谢谢！
最佳答案
除了解决您的问题外，让我给您一些有关如何根源的建议。
您在和IDE中进行开发吗？如果不是，请立即开始。
您曾经使用过调试器吗？如果没有，请立即开始。
您是否设置了条件breakpoint？如果没有，请立即开始。
在为空的变量上设置条件断点，条件是该变量为空。在调试模式下运行程序，看看发生了什么。
如果社区为您解决了这个问题，那么您还没有学到如何成为一名更好的程序员。自己解决这个问题很重要-否则，您将推迟不可避免的事情：成为一名普通的程序员。