#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 );
}