Inspired by this question and my answer to it I told myself I could try an optimized version for a 4x4 puzzle. There are only \$16!\$ possible states, so the state fits into a single `long`. However, representing the state as a primitive is ugly and precludes generalizations to bigger puzzles. Before reviewing please note my slightly different conventions. To keep it general, there's an abstract parent class: ``` /** Represents a Slidig Puzzle Board. All instances must be immutable. */ public abstract class Board> { /** * Return the manhattan distance between {@code this} and {@code other}, * which gets computed as the sum over all pieces (ignoring the empty field). * * Note that this is a valid lower bound on the necessary number of steps. */ public abstract int distanceTo(B other); /** Return the 2-4 children obtained by moving a neighboring piece to the empty field. */ public abstract Collection children(); /** * Return a board differing by a single swap. This gets used for nearly-solving unsolvable problems. * * The operation must be self-inverse. */ public abstract B alternative(); } ``` Currently, there's a single implementation, which packs its state into a single `long` and uses another one for mapping pieces to indexes (i.e., positions numbered from 0 to 15). This allows a very efficient distance calculation as described here. ``` package maaartin.pazl; import static com.google.common.base.Preconditions.checkArgument; import java.util.Collection; import java.util.List; import java.util.regex.Pattern; import com.google.common.annotations.VisibleForTesting; import com.google.common.base.Splitter; import com.google.common.collect.Lists; import com.google.common.primitives.Longs; import com.google.common.primitives.UnsignedLongs; /** * Represents the standard 4x4 board. * * Terminology: * Index is a number between 0 and 15 denoting the position on the board. * Piece is a numb

By N-by-N puzzles I mean f.e. a 3x3 sliding puzzle with one blank space (so a 8-puzzle) or a 4x4 sliding puzzle (so a 15-puzzle). When I try to solve certain puzzles some take no time but others take to much time to the point that I run out of memory. I think it's due to how I calculate the manhattan distance. Below you see the `Board class`, an instance of this class holds a puzzle in the variable `tiles`. The methods `getRow` and `getCol` is used to get the the row and column of a certain value. Then I can calculate the Manhattan distance with the method `manhattan`. Could someone tell me how I can optimize this code so that my A*-search algorithm works faster? ``` public class Board { private int[][] tiles; private int N; // construct a board from an N-by-N array of tiles public Board(int[][] tiles) { this.tiles = tiles; N = tiles.length; } // return sum of Manhattan distances between blocks and goal public int manhattan() { int count = 0; int expected = 0; for (int row = 0; row < tiles.length; row++) { for (int col = 0; col < tiles[row].length; col++) { int value = tiles[row][col]; expected++; if (value != 0 && value != expected) { // Manhattan distance is the sum of the absolute values of // the horizontal and the vertical distance count += Math.abs(row - getRow(getFinalState().tiles, value)) + Math.abs(col - getCol(getFinalState().tiles, value)); } } } return count; } // helper to get a board in final state public Board getFinalState() { int[][] finalArray = new int[N][N]; int value = 0; for (int row = 0; row < N; row++) { for (int col = 0; col < N; col++) { value

I coded the following program to solve the n-puzzle problem with n = 3. Are there any suggestions regarding readability and variable names? ``` import heapq from random import shuffle import math n=3 fBoard = [1,2,3, 4,5,6, 7,8,0] board = [i for i in range(9)] shuffle(board) print(board) aStar() class Board(): def __init__(self,boardList,cost,parent): self._array = boardList self.heuristic = calcHeuristic(self._array) self.cost = cost self.totalCost = self.cost + self.heuristic self.parent = parent self.hashvalue = hash(tuple(self._array)) def _printBoard(self): for var in range(len(self._array)): if var%3==0 and var!=0: print "\n",self._array[var],",", else: print self._array[var],",", def __hash__(self): return self.hashvalue def __eq__(self,other): return self._array == other._array def aStar(): pq = [] cost = {} visited = {} start = Board(board,0,None) end = Board(fBoard,99,None) heapq.heappush(pq,(start.totalCost,start)) while pq: tmp_tuple = heapq.heappop(pq) tmp_board = tmp_tuple[1] if tmp_board.heuristic == 0: end = tmp_board break index = tmp_board._array.index(0) x = index/3 y = index%3 listOfMoves = checkMove(x,y) for move in listOfMoves: moveBoard = tmp_board._array[:] moveIndex = move[0]*3 + move[1] moveBoard[index],moveBoard[moveIndex] = moveBoard[moveIndex],moveBoard[index] newBoard = Board(moveBoard,tmp_board.cost+1,tmp_board) new_cost = newBoard.totalCost if newBoard not in visited or new_cost =0): listOfMoves.append([x-1,y]) if(y-1>=0): listOfMoves.append([x,y-1]) if(y+1<n): listOfMoves.append([x,y+1]) return listOfMoves ```

I would like some feed back on a method which calculates the sum of Manhattan distances for each tile in a sliding puzzle to its goal position in the goal puzzle. Here is the code: ``` public static int calcManhattanDistance(int[] ps, int[] goal) { int rowSz = calculatePuzzleRowSize(ps); int manhattanDistanceSum = 0; for (int i = 0; i < ps.length; i++) { for (int j = 0; j < ps.length; j++) { if (ps[i] == goal[j]) manhattanDistanceSum += (Math.abs(i/rowSz - j/rowSz) + Math.abs(i%rowSz - j%rowSz)); } } return manhattanDistanceSum; } ``` Please tell me if you think something should be changed or what I can do to increase efficiency. Here is the `calculatePuzzleRowSize(ps)` method: ``` public static int calculatePuzzleRowSize(int[] ps) { int sz = ps.length; int rowSz = (int) Math.sqrt(sz); return rowSz; } ``` Here is the newly implemented `calculateManhattanDistanceSum` ``` public static int calculateManhattanDistanceSum(int[] ps, int[] goal) { int rowSize = (int) Math.sqrt(ps.length); int manhattanDistanceSum = 0; Map psMap = new HashMap(); for (int i : ps) psMap.put(ps[i], i); for (int j : goal) manhattanDistanceSum += Math.abs(psMap.get(j)/rowSize - j/rowSize) + Math.abs(psMap.get(j)%rowSize - j%rowSize); return manhattanDistanceSum; } ```