#define S 3								// Length of a side
#define STACKSIZE 32		 				// Big enough
int nsquared[STACKSIZE][S*S];				// A stack of states
int goal_node[S*S];							// The goal state



init_first_node() 
{
	nsquared[0] = {  1, 2, 3, 6, 4, 5, 7, 8, 0 } ;
}

initialize_goal() 
{
	goal_node = { 1,2,3,4,5,6,7,8,0 } ;
}

try_moves(int lte)
{	// lte is the level to examine in the search
	// First free position on the state stack is lte + 1

int emp_pos;			

	// Find empty position; emp_pos is a storeback parameter
	find_empty_pos(emp_pos,nsquared[lte]);

	either {// The empty square can be moved to the right
		// if its current position is not divisible by S.
		(emp_pos+1)%S != 0;
		add_new_state(lte,lte+1,emp_pos,1);
	}
	or {// The empty square can be moved to the left
		// if its current position does not have
		// remainder 1 when divided by S.
		(emp_pos + 1)%S != 1;
		add_new_state(lte,lte+1,emp_pos,-1);
	}
	or {// The empty square can be moved down if its
		// current position is less than or equal to S*S-S
		emp_pos + 1 <= S*S - S;
		add_new_state(lte,lte+1,emp_pos,S);
	}
	or {// The empty square can be moved up if its
		// current position is greater than S
		emp_pos + 1 > S;
		add_new_state(lte,lte+1,emp_pos,-S);
	}
}

find_empty_pos(int & emp_pos, int vector[S*S])
{
	and(int i=0;i<S*S;i++)
	{
		if vector[i] == 0;
		then
		{
			emp_pos = i;
			return;
		}
	}
}

add_new_state(int lte,newstate,emp_pos,k)
{	// lte is the index of the state being examined
	// newstate is the index of the new state
	// emp_pos is the position of the empty square
	// k is the change in position of the empty square

	// Copy all squares
	and(int j=0;j<S*S;j++)
		nsquared[newstate][j] = nsquared[lte][j];

	// Put empty square in proper place
	nsquared[newstate][emp_pos+k] = 0;

	// Put new square where empty square was
	nsquared[newstate][emp_pos] = nsquared[lte][emp_pos+k];

	// Verify state is new
	check_not_there(newstate);
}


check_not_there(int newstate)
{
	and (int sta=0;sta<newstate;sta++)
		not and(int j=0;j<S*S;j++) 
				nsquared[sta][j] == nsquared[newstate][j];
}


goal(int depth)
{
	and(int j=0;j<S*S;j++) 
		nsquared[depth][j] == goal_node[j];
	output(depth);
}

output(int depth)
{
int emp_pos;
	and(int j=0;j<=depth;j++)
	{
		// Find empty position
		find_empty_pos(emp_pos, nsquared[j]);
		if j == 0;
		then
		printf("\n The empty tile moves from position %d",emp_pos+1);
		else
		printf("\n to position %d ", emp_pos+1);
	}
}


2lp_main() 				// An iterative deepening search
{	
	startup(); 			// Initialize positions
	c_or(int depth=0;depth<STACKSIZE;depth=depth+2){ printf("depth is %d\n",depth);
		and(int lte=0;lte<depth;lte++)   	// Loop down levels
			try_moves(lte);			// Generate new state
		goal(depth);					// Check if goal reached
	}
}

startup()
{
	init_first_node();
	initialize_goal();
}