Я пишу решатель скользящих блоков, который имеет список блочных объектов (который содержит размер блока и расположение верхнего левого угла) и 2D-массив, представляющий лоток. Везде, где есть блок, это место в массиве указывает на объект блока, в противном случае оно равно нулю.
В моем решателе я генерирую возможные ходы, которые не были замечены, хеширую их, затем выбираю одно из действий (которое меняет макет лотка) и рекурсивно вызывает решатель в новом макете лотка. Когда больше нет возможных макетов ходов, которые не были видны, прежде чем я возвращаю вызов, отменяю последний ход и продолжаю проверять предыдущий вызов, и так далее, пока либо оно не будет решено, либо у меня не закончатся ходы (нет решения).
Проблема в том, что я получаю исключение нулевого указателя, когда делаю ход. Странно то, что это происходит только после нескольких рекурсивных вызовов. Программа отлично справляется с несколькими вызовами / ходами, а потом кажется, что она испортилась.
generateMoves () проверяет, было ли движение замечено ранее, вызывая move (), а затем меняет ход после проверки. Я думаю, что нулевой указатель появляется после того, как он вызывает move (), а move () устанавливает toMove = layout [] []. Очевидно, он ищет нулевую позицию в массиве вместо позиции с блоком. Кажется, есть несоответствие между списком блоков и массивом Tray ... Потому что, когда move () затем вызывает setTrayAfterMove (), он выдает исключение. Чего я не могу понять, так это того, почему он работает для нескольких рекурсивных вызовов resolveHelper (), но затем перестает работать.
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();
}
}
Может кто-нибудь взглянуть на мой код? Также приветствуются предложения по повышению эффективности. Спасибо!