To make the specifications more concise, we use the following definitions and notations. A puzzle state is a permutation of the sequence . Each of the elements of the puzzle state is called a tile. 0 is called the empty tile. For convenience, we will represent a puzzle state by an NxN row-major matrix. Let s be a state, let . We define tiles(i,j) to be the tile located in row i column j of s, where s is represented by a row-major N x N matrix. For every state s and tile , we define the tile location locs(t)=(i,j) where tiles(i,j)=t. Let l1=(i1,j1) and l2=(i2,j2) be two locations. The distance between l1 and l2 is defined as d(l1,l2)=|i1 - i2|+|j1 - j2|. Let be a state. Let be the goal state. The number of placed tiles is the largest p such that ti=gi for all . The expression of p+1 in the matrix notation is called the next location and is marked as NextLoc(s). gp is called the next tile and is marked as NextTile(s). Figure 11 shows examples for the above notations. The heuristic function is the one described in the beginning of Section 4, generalized to the NxN puzzle. It is a linear combination of three factors. The weights were chosen to be high enough to enforce a lexicographic order. The least significant factor is the Manhattan distance between the empty tile and the next tile. Since it is bounded above by 2(N-1), the second factor is multiplied by 2N to make sure that it is dominant. For the same reason, we multiply the most significant factor by 4N2.
Table 19 lists the exact parameters used for MICRO-HILLARY in the NxN puzzle domain.