#ident "$Id: solution.c,v 1.5 2004/11/17 17:01:48 pwh Rel $"

/*
 * Panex puzzle solution logic.
 *
 * Author:  Paul W. Hanson
 *
 * References:
 *
 *	1. Some Results on the Panex Puzzle.  by:  Mark Manasse, Danny Sleator
 *	   and Victor K. Wei
 *	2. Recent Results for the Panex Puzzle.  Nick Baxter
 *	3. http://baxterweb.com/puzzles/panex/index.htm
 *
 * The utility routines (moveStackIn, moveStackOut, sinkDisk, floatDisk,
 * Y, Y_not, Z, W and V) are from Manasse, Sleator and Wei (1).  The
 * obvious solution is just that, I came up with it independently and then
 * discovered that Baxter also sketches it.  The efficient solution is from
 * Manasse, Sleator and Wei (1).  The recursive solution is from Baxter (2).
 * The zigzag solution is from Baxter (2) which is an improvement of an idea
 * from Manasse, Sleator and Wei (1).  The better zigzag solution is a
 * combination of ideas from Baxter (2) and Manasse, Sleator and Wei (1).
 * The rest are mine based on the utility rotines from Manasse, Sleator and
 * Wei (1).
 */

#include	<stdlib.h>
#include	<limits.h>
#include	<time.h>
#include	"panex.h"


/* Randomize solution. */
static int parity ( int x )

{
   unsigned int	parity = ( unsigned int ) x;
   int		shift = 1;
   static int	maxShift = CHAR_BIT * sizeof ( int );

   while ( shift < maxShift && ( x = ( int ) ( parity >> shift ) ) ) {

	shift += shift;
	parity ^= ( unsigned int ) x;
   }

   return ( parity & 1 );
}


static int randomPeg ( void )

{
   return ( parity ( rand() ) ? RIGHT_PEG : LEFT_PEG );
}


/* Solution Logic. */
static int swapDisks ( PUZZLE *puzzle )

{
   int	status = 0;
   int	peg1 = randomPeg ();
   int	peg2 = OTHER_PEG ( peg1, CENTER_PEG );

   if ( moveDisk ( puzzle, CENTER_PEG, peg1 )
	&& moveDisk ( puzzle, CENTER_PEG, peg2 )
	&& moveDisk ( puzzle, peg1, CENTER_PEG )
	&& moveDisk ( puzzle, peg2, CENTER_PEG ) ) status = 1;

   return ( status );
}


static int swapSideDisks ( PUZZLE *puzzle, int src )

{
   int	status = 0;
   int	peg1 = randomPeg ();
   int	peg2 = OTHER_PEG ( src, CENTER_PEG );

   if ( peg1 == src ) peg1 = CENTER_PEG;
   else peg2 = CENTER_PEG;

   if ( moveDisk ( puzzle, src, peg1 )
	&& moveDisk ( puzzle, src, peg2 )
	&& moveDisk ( puzzle, peg1, src )
	&& moveDisk ( puzzle, peg2, src ) ) status = 1;

   return ( status );
}


/* Function prototypes for highly recursive routines. */
static int moveStackOut ( PUZZLE *, int, int );
static int moveStackOut1 ( PUZZLE *, int, int );
static int floatDisk ( PUZZLE *, int, int );
static int floatDisk1 ( PUZZLE *, int, int );
static int moveStackIn ( PUZZLE *, int, int );
static int moveStackIn1 ( PUZZLE *, int, int );
static int sinkDisk ( PUZZLE *, int, int );
static int sinkDisk1 ( PUZZLE *, int, int );


static int moveStackOut ( PUZZLE *puzzle, int height, int dest )

{
   int	status = 1;

   if ( dest == CENTER_PEG ) {

	status = 0;

   } else if ( height > 0 ) {

	if ( height > 2 ) {

		status = ( moveStackOut ( puzzle, height - 2, dest )
			&& swapDisks ( puzzle )
			&& floatDisk ( puzzle, height - 1, dest )
			&& moveStackOut ( puzzle, height - 1, dest ) );

	} else {

		status = ( ( height < 2
			|| moveDisk ( puzzle, CENTER_PEG, dest ) )
			&& moveDisk ( puzzle, OTHER_PEG ( dest, CENTER_PEG ),
								dest ) );
	}
   }

   return ( status );
}


static int moveStackOut1 ( PUZZLE *puzzle, int height, int dest )

{
   int	status = 1;

   if ( dest == CENTER_PEG ) {

	status = 0;

   } else if ( height > 0 ) {

	if ( height > 2 ) {

		status = ( moveStackOut1 ( puzzle, height - 2, dest )
			&& swapDisks ( puzzle )
			&& floatDisk ( puzzle, height - 1, dest )
			&& moveStackOut ( puzzle, height - 1, dest ) );

	} else {

		int	other_peg = OTHER_PEG ( dest, CENTER_PEG );

		status = ( ( height < 2
			|| moveDisk ( puzzle, CENTER_PEG, other_peg ) )
			&& moveDisk ( puzzle, CENTER_PEG, dest )
			&& ( height < 2
			|| moveDisk ( puzzle, other_peg, dest ) ) );
	}
   }

   return ( status );
}


static int floatDisk ( PUZZLE *puzzle, int height, int dest )

{
   int	status = 1;

   if ( dest == CENTER_PEG ) {

	status = 0;

   } else if ( height > 3 ) {

	status = ( moveStackIn ( puzzle, height - 2, dest )
		&& sinkDisk ( puzzle, height - 1, dest )
		&& swapDisks ( puzzle )
		&& floatDisk ( puzzle, height - 1, dest ) );

   } else if ( height == 3 ) {

	int	other_peg = OTHER_PEG ( dest, CENTER_PEG );

	status = ( moveDisk ( puzzle, dest, CENTER_PEG )
		&& moveDisk ( puzzle, dest, other_peg )
		&& moveDisk ( puzzle, CENTER_PEG, dest )
		&& moveDisk ( puzzle, CENTER_PEG, dest )
		&& moveDisk ( puzzle, other_peg, CENTER_PEG )
		&& moveDisk ( puzzle, dest, CENTER_PEG )
		&& moveDisk ( puzzle, dest, other_peg )
		&& moveDisk ( puzzle, CENTER_PEG, dest ) );

   } else if ( height == 2 ) {

	status = ( moveDisk ( puzzle, dest, OTHER_PEG ( dest, CENTER_PEG ) )
		&& moveDisk ( puzzle, CENTER_PEG, dest ) );

   } else if ( height == 1 ) {

	status = moveDisk ( puzzle, CENTER_PEG, dest );
   }

   return ( status );
}


static int floatDisk1 ( PUZZLE *puzzle, int height, int dest )

{
   int	status = 1;

   if ( dest == CENTER_PEG ) {

	status = 0;

   } else if ( height > 3 ) {

	status = ( moveStackIn ( puzzle, height - 2, dest )
		&& sinkDisk ( puzzle, height - 1, dest )
		&& swapDisks ( puzzle )
		&& floatDisk1 ( puzzle, height - 1, dest ) );

   } else if ( height == 3 ) {

	int	other_peg = OTHER_PEG ( dest, CENTER_PEG );
	int	which_solution = randomPeg ();

	if ( which_solution != dest ) {

		status = ( swapSideDisks ( puzzle, dest )
			&& moveDisk ( puzzle, CENTER_PEG, other_peg )
			&& moveDisk ( puzzle, dest, CENTER_PEG )
			&& moveDisk ( puzzle, dest, CENTER_PEG ) );

	} else {

		status = ( moveDisk ( puzzle, dest, CENTER_PEG )
			&& moveDisk ( puzzle, dest, other_peg )
			&& moveDisk ( puzzle, CENTER_PEG, dest )
			&& moveDisk ( puzzle, CENTER_PEG, dest )
			&& moveDisk ( puzzle, other_peg, CENTER_PEG )
			&& moveDisk ( puzzle, dest, other_peg )
			&& moveDisk ( puzzle, dest, CENTER_PEG ) );
	}

	if ( status ) status = moveDisk ( puzzle, other_peg, dest );
	
   } else if ( height == 2 ) {

	int	other_peg = OTHER_PEG ( dest, CENTER_PEG );

	status = ( moveDisk ( puzzle, dest, other_peg )
		&& moveDisk ( puzzle, CENTER_PEG, dest )
		&& moveDisk ( puzzle, other_peg, CENTER_PEG ) );

   } else if ( height == 1 ) {

	status = moveDisk ( puzzle, CENTER_PEG, dest );
   }

   return ( status );
}


static int moveStackIn ( PUZZLE *puzzle, int height, int src )

{
   int	status = 1;

   if ( src == CENTER_PEG ) {

	status = 0;

   } else if ( height > 0 ) {

	if ( height > 2 ) {

		status = ( moveStackIn ( puzzle, height - 1, src )
			&& sinkDisk ( puzzle, height - 1, src )
			&& swapDisks ( puzzle )
			&& moveStackIn ( puzzle, height - 2, src ) );

	} else {

		status = ( moveDisk ( puzzle, src,
						OTHER_PEG ( src, CENTER_PEG ) )
			&& ( height < 2
			|| moveDisk ( puzzle, src, CENTER_PEG ) ) );
	}
   }

   return ( status );
}


static int moveStackIn1 ( PUZZLE *puzzle, int height, int src )

{
   int	status = 1;

   if ( src == CENTER_PEG ) {

	status = 0;

   } else if ( height > 0 ) {

	if ( height > 2 ) {

		status = ( moveStackIn ( puzzle, height - 1, src )
			&& sinkDisk ( puzzle, height - 1, src )
			&& swapDisks ( puzzle )
			&& moveStackIn1 ( puzzle, height - 2, src ) );

	} else {

		int	other_peg = OTHER_PEG ( src, CENTER_PEG );

		status = ( ( height < 2
			|| moveDisk ( puzzle, src, other_peg ) )
			&& moveDisk ( puzzle, src, CENTER_PEG )
			&& ( height < 2
			|| moveDisk ( puzzle, other_peg, CENTER_PEG ) ) );
	}
   }

   return ( status );
}


static int sinkDisk ( PUZZLE *puzzle, int height, int src )

{
   int	status = 1;

   if ( src == CENTER_PEG ) {

	status = 0;

   } else if ( height > 3 ) {

	status = ( sinkDisk ( puzzle, height - 1, src )
		&& swapDisks ( puzzle )
		&& floatDisk ( puzzle, height - 1, src )
		&& moveStackOut ( puzzle, height - 2, src ) );

   } else if ( height == 3 ) {

	int	other_peg = OTHER_PEG ( src, CENTER_PEG );

	status = ( moveDisk ( puzzle, src, CENTER_PEG )
		&& moveDisk ( puzzle, other_peg, src )
		&& moveDisk ( puzzle, CENTER_PEG, src )
		&& moveDisk ( puzzle, CENTER_PEG, other_peg )
		&& moveDisk ( puzzle, src, CENTER_PEG )
		&& moveDisk ( puzzle, src, CENTER_PEG )
		&& moveDisk ( puzzle, other_peg, src )
		&& moveDisk ( puzzle, CENTER_PEG, src ) );

   } else if ( height == 2 ) {

	status = ( moveDisk ( puzzle, src, CENTER_PEG )
		&& moveDisk ( puzzle, OTHER_PEG ( src, CENTER_PEG ), src ) );

   } else if ( height == 1 ) {

	status = moveDisk ( puzzle, src, CENTER_PEG );
   }

   return ( status );
}


static int sinkDisk1 ( PUZZLE *puzzle, int height, int src )

{
   int	status = 1;

   if ( src == CENTER_PEG ) {

	status = 0;

   } else if ( height > 3 ) {

	status = ( sinkDisk1 ( puzzle, height - 1, src )
		&& swapDisks ( puzzle )
		&& floatDisk ( puzzle, height - 1, src )
		&& moveStackOut ( puzzle, height - 2, src ) );

   } else if ( height == 3 ) {

	int	other_peg = OTHER_PEG ( src, CENTER_PEG );
	int	which_solution = randomPeg ();

	if ( status = moveDisk ( puzzle, src, other_peg ) ) {

		if ( which_solution != src ) {

			status = ( moveDisk ( puzzle, CENTER_PEG, src )
				&& moveDisk ( puzzle, CENTER_PEG, src )
				&& moveDisk ( puzzle, other_peg, CENTER_PEG )
				&& swapSideDisks ( puzzle, src ) );

		} else {

			status = ( moveDisk ( puzzle, CENTER_PEG, src )
				&& moveDisk ( puzzle, other_peg, src )
				&& moveDisk ( puzzle, CENTER_PEG, other_peg )
				&& moveDisk ( puzzle, src, CENTER_PEG )
				&& moveDisk ( puzzle, src, CENTER_PEG )
				&& moveDisk ( puzzle, other_peg, src )
				&& moveDisk ( puzzle, CENTER_PEG, src ) );
		}
	}

   } else if ( height == 2 ) {

	int	other_peg = OTHER_PEG ( src, CENTER_PEG );

	status = ( moveDisk ( puzzle, CENTER_PEG, other_peg )
		&& moveDisk ( puzzle, src, CENTER_PEG )
		&& moveDisk ( puzzle, other_peg, src ) );

   } else if ( height == 1 ) {

	status = moveDisk ( puzzle, src, CENTER_PEG );
   }

   return ( status );
}


static int Y_base ( PUZZLE *puzzle, int src )

{
   int	other_peg = OTHER_PEG ( src, CENTER_PEG );

   return ( moveDisk ( puzzle, src, CENTER_PEG )
	&& moveDisk ( puzzle, other_peg, src )
	&& moveDisk ( puzzle, CENTER_PEG, src )
	&& moveDisk ( puzzle, CENTER_PEG, other_peg )
	&& moveDisk ( puzzle, src, CENTER_PEG )
	&& moveDisk ( puzzle, src, CENTER_PEG )
	&& moveDisk ( puzzle, other_peg, src )
	&& moveDisk ( puzzle, other_peg, src )
	&& moveDisk ( puzzle, other_peg, src )
	&& moveDisk ( puzzle, CENTER_PEG, other_peg )
	&& moveDisk ( puzzle, CENTER_PEG, other_peg )
	&& moveDisk ( puzzle, src, CENTER_PEG ) );
}


static int YZ ( PUZZLE *puzzle, int src )

{
   int	other_peg = OTHER_PEG ( src, CENTER_PEG );
   int	peg1 = randomPeg ();
   int	peg2 = OTHER_PEG ( peg1, CENTER_PEG );

   if ( peg1 == src ) peg2 = CENTER_PEG;
   else peg1 = CENTER_PEG;

   return ( Y_base ( puzzle, src )
	&& moveDisk ( puzzle, other_peg, peg1 )
	&& moveDisk ( puzzle, other_peg, peg2 )
	&& moveDisk ( puzzle, peg1, other_peg )
	&& moveDisk ( puzzle, peg2, other_peg )
	&& moveDisk ( puzzle, src, other_peg )
	&& moveDisk ( puzzle, src, CENTER_PEG )
	&& moveDisk ( puzzle, other_peg, src )
	&& moveDisk ( puzzle, other_peg, src )
	&& moveDisk ( puzzle, CENTER_PEG, other_peg )
	&& moveDisk ( puzzle, src, other_peg )
	&& swapDisks ( puzzle )
	&& moveDisk ( puzzle, src, other_peg )
	&& moveDisk ( puzzle, CENTER_PEG, src )
	&& moveDisk ( puzzle, CENTER_PEG, src )
	&& moveDisk ( puzzle, other_peg, src ) );
}



static int Y_not ( PUZZLE *puzzle, int src )

{
   int	other_peg = OTHER_PEG ( src, CENTER_PEG );

   return ( Y_base ( puzzle, src )
	&& moveDisk ( puzzle, other_peg, CENTER_PEG )
	&& moveDisk ( puzzle, other_peg, src )
	&& moveDisk ( puzzle, CENTER_PEG, other_peg ) );
}


static int W ( PUZZLE *puzzle, int dest )

{
   int	other_peg = OTHER_PEG ( dest, CENTER_PEG );

   return ( moveDisk ( puzzle, other_peg, dest )
	&& moveDisk ( puzzle, CENTER_PEG, dest )
	&& moveDisk ( puzzle, CENTER_PEG, other_peg )
	&& moveDisk ( puzzle, dest, CENTER_PEG )
	&& moveDisk ( puzzle, dest, CENTER_PEG )
	&& moveDisk ( puzzle, other_peg, dest )
	&& moveDisk ( puzzle, other_peg, dest )
	&& moveDisk ( puzzle, other_peg, dest )
	&& moveDisk ( puzzle, CENTER_PEG, other_peg )
	&& moveDisk ( puzzle, dest, other_peg )
	&& moveDisk ( puzzle, dest, CENTER_PEG )
	&& moveDisk ( puzzle, other_peg, dest )
	&& moveDisk ( puzzle, other_peg, dest ) );
}


static int V ( PUZZLE *puzzle, int dest )

{
   int	status = 1;
   int	other_peg = OTHER_PEG ( dest, CENTER_PEG );
   int	i = puzzle->height - 1;
   int	height = i - 1;

   while ( status && i > 3 ) {

	status = ( moveStackOut ( puzzle, i - 2, dest )
		&& swapDisks ( puzzle )
		&& floatDisk ( puzzle, i - 1, dest ) );
	--i;
   }

   status = ( status
		&& W ( puzzle, dest )
		&& moveDisk ( puzzle, other_peg, dest )
		&& moveDisk ( puzzle, CENTER_PEG, other_peg )
		&& moveDisk ( puzzle, CENTER_PEG, other_peg )
		&& moveDisk ( puzzle, dest, CENTER_PEG )
		&& moveDisk ( puzzle, other_peg, CENTER_PEG )
		&& moveDisk ( puzzle, other_peg, dest ) );

   while ( status && i < height ) {

	status = ( sinkDisk ( puzzle, i, other_peg )
		&& swapDisks ( puzzle )
		&& moveStackIn ( puzzle, i - 1, other_peg ) );
	++i;
   }

   status = ( status
	&& ( ++height > 3 ?
	sinkDisk ( puzzle, height, other_peg )
	: moveStackOut ( puzzle, height - 1, other_peg ) )
	&& swapDisks ( puzzle )
	&& floatDisk ( puzzle, height, other_peg ) );

   return ( status );
}


int solvePuzzle ( PUZZLE *puzzle, int height, int solution )

{
   int	status = 0;
   int	peg1;
   int	peg2;

   /* Seed random number generator. */
   srand( ( unsigned int ) time ( NULL ) );
   peg1 = randomPeg();
   peg2 = OTHER_PEG ( peg1, CENTER_PEG );

   if ( height == 0 ) {

	status = 1;

   } else if ( height == 1 ) {

	status = ( moveDisk ( puzzle, peg1, CENTER_PEG )
		&& moveDisk ( puzzle, peg2, peg1 )
		&& moveDisk ( puzzle, CENTER_PEG, peg2 ) );

   } else if ( height > 0 ) {

	int	i;

	switch ( solution ) {

	   case OBVIOUS_SOLUTION:

		i = height;

		status = 1;

		while ( status && i > 1 ) {

			status = ( moveStackIn ( puzzle, i, peg1 )
				&& moveStackOut ( puzzle, i - 1, peg1 )
				&& moveStackIn ( puzzle, i, peg2 )
				&& moveStackOut ( puzzle, i - 1, peg2 )
				&& moveStackIn ( puzzle, i - 1, peg1 )
				&& moveStackOut ( puzzle, i, peg1 )
				&& moveStackIn ( puzzle, i - 1, peg2 )
				&& moveStackOut ( puzzle, i, peg2 ) );
			--i;
		}

		status = ( status
			&& moveDisk ( puzzle, peg1, CENTER_PEG )
			&& moveDisk ( puzzle, peg2, peg1 )
			&& moveDisk ( puzzle, CENTER_PEG, peg2 ) );
		break;

	   case RECURSIVE_SOLUTION:

		status = ( moveStackIn ( puzzle, height - 1, peg1 )
			&& sinkDisk ( puzzle, height, peg1 )
			&& moveStackIn ( puzzle, height - 1, peg2 )
			&& sinkDisk ( puzzle, height, peg2 )
			&& floatDisk ( puzzle, height, peg1 )
			&& moveStackOut ( puzzle, height - 1, peg1 )
			&& floatDisk ( puzzle, height, peg2 )
			&& moveStackOut ( puzzle, height - 1, peg2 )
			&& solvePuzzle ( puzzle, height - 1, solution ) );
		break;

	   case BETTER_ALTERNATING_SOLUTION:

		if ( height > 3 ) {

			i = height - 1;

			status = ( moveStackIn ( puzzle, height - 1, peg1 )
				&& sinkDisk ( puzzle, height - 1, peg1 )
				&& swapDisks ( puzzle ) );

			while ( status && ( status
				= ( moveStackIn ( puzzle, i - 1, peg2 )
				&& sinkDisk ( puzzle, i, peg2 )
				&& floatDisk ( puzzle, i, peg1 )
				&& moveStackOut ( puzzle, i - 1, peg1 )
				&& floatDisk ( puzzle, i, peg2 )
				&& moveStackOut ( puzzle, i - 2, peg2 ) ) )
				&& --i > 2 ) {

				peg1 ^= peg2;
				peg2 ^= peg1;
				peg1 ^= peg2;
			}

			status = ( status
				&& moveStackIn ( puzzle, i - 1, peg1 )
				&& sinkDisk ( puzzle, i, peg1 )
				&& floatDisk ( puzzle, i, peg2 )
				&& moveDisk ( puzzle, peg1, CENTER_PEG )
				&& moveDisk ( puzzle, peg1, peg2 ) );

			if ( status ) {

				if ( height & 1 ) {

					status = ( moveDisk ( puzzle, peg1,
									peg2 )
					&& moveDisk ( puzzle, CENTER_PEG, peg1 )
					&& moveDisk ( puzzle, CENTER_PEG, peg1 ) 
					&& moveDisk ( puzzle, peg2, CENTER_PEG )
					&& moveDisk ( puzzle, peg1, CENTER_PEG )
					&& moveDisk ( puzzle, peg1, peg2 ) );

					if ( status ) while ( ++i < height - 1
					&& status && ( status =
					( sinkDisk ( puzzle, i, peg1 )
					&& swapDisks ( puzzle )
					&& moveStackIn ( puzzle, i - 1,
								peg1 ) ) ) );

					status = ( status
					&& sinkDisk ( puzzle, height, peg1 )
					&& floatDisk ( puzzle, height, peg2 )
					&& moveStackOut ( puzzle, height - 1,
									peg2 )
					&& floatDisk ( puzzle, height, peg1 )
					&& moveStackOut ( puzzle, height - 1,
								peg1 ) );

				} else {

					status = (
					moveStackOut1 ( puzzle, 2, peg1 )
					&& moveStackIn ( puzzle, height - 1,
									peg2 )
					&& sinkDisk ( puzzle, height, peg2 )
					&& floatDisk ( puzzle, height, peg1 )
					&& moveStackOut ( puzzle, height - 1,
									peg1 )
					&& floatDisk ( puzzle, height, peg2 )
					&& moveStackOut ( puzzle, height - 1,
								peg2 ) );
				}
			}

			break;
		}

	   case ALTERNATING_SOLUTION:

		i = height;

		status = ( moveStackIn ( puzzle, height - 1, peg1 )
			&& sinkDisk ( puzzle, height, peg1 ) );

		while ( status && ( status
			= ( moveStackIn ( puzzle, i - 1, peg2 )
			&& sinkDisk ( puzzle, i, peg2 )
			&& floatDisk ( puzzle, i, peg1 )
			&& moveStackOut ( puzzle, i - 1, peg1 )
			&& floatDisk ( puzzle, i, peg2 )
			&& moveStackOut ( puzzle, i - 2, peg2 ) ) )
			&& --i > 1 ) {

			peg1 ^= peg2;
			peg2 ^= peg1;
			peg1 ^= peg2;
		}

		status = ( status
			&& moveDisk ( puzzle, peg1, CENTER_PEG )
			&& moveDisk ( puzzle, peg1, peg2 )
			&& moveDisk ( puzzle, CENTER_PEG, peg1 ) );
		break;

	   case BETTER_ZIGZAG_SOLUTION:

		if ( height > 2 ) {

			i = 2;

			status = ( moveStackIn ( puzzle, height - 1, peg1 )
				&& sinkDisk ( puzzle, height - 1, peg1 )
				&& swapDisks ( puzzle )
				&& moveStackIn ( puzzle, height - 2, peg2 )
				&& sinkDisk ( puzzle, height - 1, peg2 )
				&& floatDisk1 ( puzzle, height - 1, peg1 )
				&& moveDisk ( puzzle, peg2, peg1 )
				&& moveDisk ( puzzle, CENTER_PEG, peg1 ) );

			while ( status && i < height - 1 ) {

				status = ( sinkDisk ( puzzle, i, peg2 )
					&& floatDisk ( puzzle, i, peg1 )
					&& moveStackOut ( puzzle, i - 1,
								peg1 )
					&& moveStackIn ( puzzle, i - 1,
								peg2 ) );
				++i;
			}

			status = ( status
				&& sinkDisk ( puzzle, height, peg2 )
				&& floatDisk ( puzzle, height, peg1 )
				&& moveStackOut ( puzzle, height - 1, peg1 )
				&& floatDisk ( puzzle, height, peg2 )
				&& moveStackOut ( puzzle, height - 1,
								peg2 ) );
			break;
		}

	   case ZIGZAG_SOLUTION:

		i = 2;

		status = ( moveStackIn ( puzzle, height - 1, peg1 )
			&& sinkDisk ( puzzle, height, peg1 )
			&& moveStackIn ( puzzle, height - 1, peg2 )
			&& sinkDisk ( puzzle, height, peg2 )
			&& floatDisk1 ( puzzle, height, peg1 )
			&& moveDisk ( puzzle, peg2, peg1 ) );

		while ( status && i < height ) {

			status = ( sinkDisk1 ( puzzle, i, peg2 )
				&& floatDisk ( puzzle, i, peg1 )
				&& moveStackOut ( puzzle, i - 1, peg1 ) );
			if ( ++i < height ) status
				= moveStackIn1 ( puzzle, i - 2, peg2 );
		}

		status = ( status
			&& ( height == 2 ?
			( moveDisk ( puzzle, CENTER_PEG, peg1 )
			&& moveDisk ( puzzle, CENTER_PEG, peg2 )
			&& moveDisk ( puzzle, peg1, peg2 ) )
			: ( swapDisks ( puzzle )
			&& floatDisk ( puzzle, height - 1, peg2 )
			&& moveStackOut ( puzzle, height - 1, peg2 ) ) ) );
		break;

	   case BETTER_BOTTOM_UP_SOLUTION:

		if ( height > 2 ) {

			i = height - 1;

			status = ( moveStackIn ( puzzle, height - 1, peg1 )
				&& sinkDisk ( puzzle, height - 1, peg1 )
				&& swapDisks ( puzzle ) );

			while ( status && i > 1 ) {

				status = ( moveStackIn ( puzzle, i - 1,
								peg2 )
					&& sinkDisk ( puzzle, i, peg2 )
					&& floatDisk ( puzzle, i, peg1 )
					&& moveStackOut ( puzzle, i - 2,
								peg1 ) );
				--i;
			}

			status = ( status
				&& moveDisk ( puzzle, peg2, CENTER_PEG )
				&& moveDisk ( puzzle, peg2, peg1 )
				&& sinkDisk1 ( puzzle, height, peg2 )
				&& floatDisk ( puzzle, height, peg1 )
				&& moveStackOut ( puzzle, height - 1, peg1 )
				&& floatDisk ( puzzle, height, peg2 )
				&& moveStackOut ( puzzle, height - 1,
								peg2 ) );
			break;
		}

	   case BOTTOM_UP_SOLUTION:

		i = height;

		status = ( moveStackIn ( puzzle, height - 1, peg1 )
			&& sinkDisk ( puzzle, height, peg1 ) );

		while ( status && i > 1 ) {

			status = ( moveStackIn ( puzzle, i - 1, peg2 )
				&& sinkDisk ( puzzle, i, peg2 )
				&& floatDisk ( puzzle, i, peg1 )
				&& moveStackOut ( puzzle, i - 2, peg1 ) );
			i--;
		}

		status = ( status
			&& moveDisk ( puzzle, peg2, CENTER_PEG )
			&& moveDisk ( puzzle, peg2, peg1 )
			&& moveStackOut1 ( puzzle, height, peg2 ) );
		break;

	   case EFFICIENT_SOLUTION:
	   default:

		i = height;

		switch ( height ) {

		   case 2:

			status = ( moveDisk ( puzzle, peg1, peg2 )
				&& sinkDisk ( puzzle, 2, peg1 )
				&& moveDisk ( puzzle, peg2, peg1 )
				&& sinkDisk ( puzzle, 2, peg2 )
				&& floatDisk ( puzzle, 2, peg1 )
				&& moveDisk ( puzzle, peg2, CENTER_PEG )
				&& moveDisk ( puzzle, peg2, peg1 )
				&& moveStackOut1 ( puzzle, 2, peg2 ) );
			break;

		   case 3:

			status = ( moveStackIn ( puzzle, height - 1, peg1 )
				&& sinkDisk ( puzzle, height, peg1 )
				&& moveStackIn ( puzzle, height - 1, peg2 )
				&& YZ ( puzzle, peg2 ) );
			break;

		   default:

			status = ( moveStackIn ( puzzle, height - 1, peg1 )
				&& sinkDisk ( puzzle, height - 1, peg1 )
				&& swapDisks ( puzzle )
				&& moveStackIn ( puzzle, height - 2,
								peg2 ) );

			if ( status && height > 4 ) {

				status = ( sinkDisk ( puzzle, height - 1,
								peg2 )
					&& floatDisk ( puzzle, height - 1,
								peg1 ) );
				i = height - 2;

				while ( status && i > 3 ) {

					status = ( moveStackOut ( puzzle, i - 1,
								peg1 )
						&& moveStackIn ( puzzle, i - 1,
								peg2 )
						&& sinkDisk ( puzzle, i,
								peg2 )
						&& floatDisk ( puzzle, i,
								peg1 ) );
					--i;
				}

				status = ( status
					&& moveStackOut ( puzzle, 2, peg1 )
					&& moveStackIn ( puzzle, 2,
								peg2 ) );
			}

			status = ( status
				&& Y_not ( puzzle, peg2 )
				&& moveStackOut ( puzzle, 2, peg1 )
				&& moveStackIn ( puzzle, 2, peg2 )
				&& sinkDisk ( puzzle, height, peg2 )
				&& floatDisk ( puzzle, height, peg1 )
				&& V ( puzzle, peg1 )
				&& moveStackOut ( puzzle, height - 1,
								peg2 ) );
			break;
		}
	}
   }

   return ( status );
}