Appendix B. The Efficiency of Solving NxN Puzzles by MICRO-HILLARY

This section contains a proof that a specific set of macros learned by MICRO-HILLARY is complete with respect to the heuristic function h defined in Table 19, and that a problem solver that uses these macros can solve any solvable NxN puzzle problem in O(N³) with a reasonable constant. The proof can be easily generalized to specify sufficient conditions for a set of macros to be complete.

Lemma 1   Let h be the heuristic function and B the set of basic operators defined in Table 19. Let s_g be a goal state of NxN puzzle. Let $s=\left\langle t_1, \ldots ,t_{N^2} \right\rangle$ be a puzzle state different from s_g such that solvable(s,s_g).
If $d \left(loc_s(0), loc_s(nextTile(s))\right) > 1$, then there exists a basic operator $o \in B$ such that h(o(s),s_g) < h(s,s_g).

Proof:
Let $loc_s(NextTile(s))=\left\langle i_{p}, j_{p} \right\rangle$, $loc_s(0)=\left\langle i_{0}, j_{0} \right\rangle$ and $NextLoc(s)=\left\langle i_{t}, j_{t} \right\rangle$. The following basic operators will decrease the value of h:

$$o=\left\{ \begin{array}{ll} j_{p} > j_{0} & r \\ j_{p} = j_... ...{p} \leq i_{0} & l \end{array}\right . \\ \end{array}\right .$$ (4)

Table 20: The macro used for each of the conditions on the tile indices. The right column shows an example for a state before and after the macro application.

jp=j0	$\begin{array}{c} i_{p}>i_{0}\\ \scriptstyle{(i_{p}=i_{0}+1)} \end{array}$			d	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{13} & \scriptscriptstyle {24} & \scriptscriptstyle {21} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{13} & \scriptscriptstyle {24} & \scriptscriptstyle {21} \\ \hline \end{array}$
	$\begin{array}{c} i_{p}<i_{0}\\ \scriptstyle{(i_{p}=i_{0}-1)} \end{array}$	jp>jt		lur	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ... {19} & \scriptscriptstyle { } & \scriptscriptstyle {18} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{24} & \scriptscriptstyle {19} & \scriptscriptstyle {18} \\ \hline \end{array}$
		jp<jt		rul	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{16} & \scriptscriptstyle {24} & \scriptscriptstyle {23} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{16} & \scriptscriptstyle {24} & \scriptscriptstyle {23} \\ \hline \end{array}$
		jp=jt	jp<N	ruuld	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ... {23} & \scriptscriptstyle { } & \scriptscriptstyle {15} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{23} & \scriptscriptstyle {15} & \scriptscriptstyle {18} \\ \hline \end{array}$
			jp=N	uuldrdluurd	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{12} & \scriptscriptstyle {11} & \scriptscriptstyle {15} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{12} & \scriptscriptstyle {11} & \scriptscriptstyle {15} \\ \hline \end{array}$

Lemma 2   Let h, B, s_g and s be defined as in Lemma 1. Let M be the following set of macros:

$$M= \left\{\parbox{11.5cm}{\raggedright lur, rul, uld, ruuld,... ...drrullldrrurd, llurdrrullldrrurd, uldllurdrulldrrurd}\right\}$$

Then the set M is a complete set of macros, i.e., there is always an operator $o \in B \cup M$ such that h(o(s),s_g) < h(s,s_g).

Proof:
By Lemma 1, we need to prove only for the cases where $d \left(loc_s(0),loc(NextTile(s)) \right )=1$. There are four possible cases. Tables 20 and 21 show which operator can be applied in each of the cases to decrease the value of h. To make the proof simpler, the tables assume N > 4.

Table 21: (Cont.) The macro used for each of the conditions on the tile indices. The right column shows an example for a state before and after the macro application.

$\begin{array}{c} j_p>j_0\\ \scriptstyle{(j_{p}=j_{0}+1)} \end{array}$	ip=i0	jp>jt		r	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{16} & \scriptscriptstyle {24} & \scriptscriptstyle {23} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{16} & \scriptscriptstyle {24} & \scriptscriptstyle {23} \\ \hline \end{array}$
		jp<jt	ip<N	drrul	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{16} & \scriptscriptstyle {24} & \scriptscriptstyle {23} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{16} & \scriptscriptstyle {24} & \scriptscriptstyle {23} \\ \hline \end{array}$
			$\begin{array}{c} i_{p}=N\\ i_{t}<N-1 \end{array}$	urrdluld	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{21} & \scriptscriptstyle {19} & \scriptscriptstyle {24} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...15]} & \scriptscriptstyle {19} & \scriptscriptstyle {24} \\ \hline \end{array}$
			$\renewcommand{\arraystretch}{0.7}\begin{array}{c} i_{p}=N\\ i_{t}=N-1\\ j_t - j_p \leq 1 \end{array}$	urrdluld	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...19]} & \scriptscriptstyle {24} & \scriptscriptstyle {23} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...2} & \scriptscriptstyle {[19]} & \scriptscriptstyle {23} \\ \hline \end{array}$
			$\renewcommand{\arraystretch}{0.7}\begin{array}{c} i_{p}=N\\ i_{t}=N-1\\ j_t - j_p > 1 \end{array}$	urdrrullldrrurd	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...20]} & \scriptscriptstyle {24} & \scriptscriptstyle {23} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{23} & \scriptscriptstyle {[20]} & \scriptscriptstyle {} \\ \hline \end{array}$
		jp = jt	j0 > 1	lurrdluld	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{16} & \scriptscriptstyle {24} & \scriptscriptstyle {23} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{16} & \scriptscriptstyle {24} & \scriptscriptstyle {23} \\ \hline \end{array}$
			j0 = 1	urdrulldrur	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{21} & \scriptscriptstyle {24} & \scriptscriptstyle {22} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{20} & \scriptscriptstyle {24} & \scriptscriptstyle {22} \\ \hline \end{array}$
$\begin{array}{c} j_p<j_0\\ \scriptstyle{(j_{p}=j_{0}-1)} \end{array}$	ip=i0	jp>jt	$\begin{array}{c} i_{t} < N\\ i_{p} < N \end{array}$	dllur	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{24} & \scriptscriptstyle {22} & \scriptscriptstyle {23} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{19} & \scriptscriptstyle {24} & \scriptscriptstyle {23} \\ \hline \end{array}$
			$\begin{array}{c} i_{t} < N\\ i_{p} = N \end{array}$	uld	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...24} & \scriptscriptstyle {[18]} & \scriptscriptstyle { } \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ... {24} & \scriptscriptstyle { } & \scriptscriptstyle {23} \\ \hline \end{array}$
			$\renewcommand{\arraystretch}{0.7}\begin{array}{c} i_{t} = N\\ j_{0} < N \end{array}$	llurdrrullldrrurd	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...[21]} & \scriptscriptstyle { } & \scriptscriptstyle {24} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ... {24} & \scriptscriptstyle {23} & \scriptscriptstyle { } \\ \hline \end{array}$
			$\renewcommand{\arraystretch}{0.7}\begin{array}{c} i_{t} = N\\ j_{0} = N\\ J_{t} < N - 2\\ \end{array}$	uldllurdrulldrrurd	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...23} & \scriptscriptstyle {[21]} & \scriptscriptstyle { } \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...[21]} & \scriptscriptstyle {24} & \scriptscriptstyle { } \\ \hline \end{array}$
			$\begin{array}{c} i_{t} = N\\ j_{0} = N\\ J_{t} \geq N - 2\\ \end{array}$	Unsolvable puzzle	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...24} & \scriptscriptstyle {[23]} & \scriptscriptstyle { } \\ \hline \end{array}$
		jp < jt		l	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{21} & \scriptscriptstyle {24} & \scriptscriptstyle {23} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{21} & \scriptscriptstyle {24} & \scriptscriptstyle {23} \\ \hline \end{array}$
			jp = jt	uld	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{13} & \scriptscriptstyle {24} & \scriptscriptstyle {21} \\ \hline \end{array}$	$\renewcommand{\arraystretch}{0.5}\setlength{\arraycolsep}{0.5mm}\begin{array}{... ...{13} & \scriptscriptstyle {24} & \scriptscriptstyle {21} \\ \hline \end{array}$

Theorem 1   Let h and M be defined as in Lemma 2. MICRO-HILLARY, using M, can solve any solvable NxN puzzle problem performing no more than 288N³-301N² basic operator applications. The length of the solution is bounded by 50N³-66N².

Proof:
By Lemma 2, we can move from each state to a state with a lower heuristic value. Therefore, after a finite number of states, we will reach the state s with h(s,s_g)=0, which is the goal state. N² tiles are moved into their goal location. The maximum distance of each tile from its goal location is 2(N-1). Each movement of a tile towards its goal location involves moving the blank tile to be adjacent to the next tile, and then using either a basic operator or a macro operator to advance the next tile. At the beginning of this operation the blank tile can be anywhere, so we need to advance it at most (N-1)+(N-2) times to bring it to distance 1 from the next tile. After that, for the remaining 2(N-1)-1 times, a macro operator can move the blank away from the next tile, but the distance will be at most 4 (this is a property of the specific M), so we will need to advance it at most 3 times to bring it next to the next tile. By Lemma 1, the blank tile can be brought to distance 1 using only basic operators. After bringing the empty tile next to the next tile, in the worst case, the algorithm may try all the 4 basic operators and all the macros (with a total length of 124) before finding the one that reduces the heuristic value. All this leads to the following bound on the total number of basic operators applied while solving a problem p using B and M:

N²[4((N-1)+(N-2)+3(2(N-1)-1))+2(N-1)(124+4)]=288N³-301N²

The maximal length of a macro is 18. Therefore, the length of a solution found by
MICRO-HILLARY is bounded by

$$N^2[4((N-1)+(N-2)+3(2(N-1)-1))+2(N-1)18]=50N^3-66N^2 \; \mbox{$\Box$}$$

We can use the same lemmas to prove that MICRO-HILLARY can solve any solvable problem in O(N³) even without learning simply by performing BFS search in each place where a macro is used in the original proof. However, instead of using 128 in the above formula, we will use 4¹⁸ (18, the length of the longest macro, can be used as an upper bound on the depth of the search). This gives a bound of 137,438,953,504N³ - 137,438,953,520N², which is about 477,218,588 times larger than the constant for MICRO-HILLARY after learning. While in the pure sense of computational complexity both bounds belong to the same complexity class, the huge constant makes this fact meaningless for any practical purpose.