// PrpGrnGod

// PrpGrnGod.cpp : Defines the entry point for the console application.

// This is the Purple and Green Sliding Puzzle God's Algorithm Solver

// by Adrian Dale 2002

// Just to keep my brain in gear...

// Shame my PC is running short of memory - makes this difficult to test

// (Which is probably why it is now - 2007 - broken ...)

// NB Need to alter Stack Allocation linker setting to something huge!

// #include "stdafx.h"

// What this program does is to solve the Purple and Green puzzle in

// the optimum manner by working backwards from a solved puzzle to get

// the puzzle into all possible states.

// 16,777,216 of them, although we can exclude ones with spaces in the

// middle, leaving only 92400 positions

// Then to solve the puzzle we find the state that it is in and follow

// the From pointers back up to the winning Depth==1 state.

#include "stdio.h"

#include "malloc.h"

#include "stdlib.h"

#include "assert.h"

typedef unsigned int PuzzleDepth;

typedef unsigned int PuzzleHashId;

// This structure holds the hash id that each of the three possible

// slides could move to.

typedef struct stPuzzleState

{

// Hash id for position we came from

// (Wastes one byte for simplicity)

unsigned int From;

// What this position looks like

PuzzleHashId PuzState;

// This could be smaller but for now not bothered as even if Depth

// is only one byte (which isn't enough, anyway) the struct sizes at

// 8 bytes

PuzzleDepth Depth;

} PuzzleState;

#define HASH_SIZE 100000

// A hash id is an array of three bytes, one for the Front, Middle and Back // faces.

// id[0] = Front(Purple)

// id[1] = Middle(Yellow/Space)

// id[2] = Back(Green)

// Each face has four squares, represented by two bytes each.

// The two bytes can be:

// 00 = Space

// 01 = Green

// 10 = Purple

// 11 = Yellow

// In order from LSB to MSB, each face is ordered:

// +-+-+

// |0|2|

// +-+-+

// |4|6|

// +-+-+

typedef struct stPuzzleState *PuzzleStatePtr;

PuzzleStatePtr gpAllStates;

unsigned int giNextState = 0;

void PopulateTableBFS();

void GetPossibleMoves( PuzzleHashId PuzTo, PuzzleHashId *NewPuzTo1,

PuzzleHashId *NewPuzTo2, PuzzleHashId *NewPuzTo3 );

PuzzleHashId IdBitSwap( PuzzleHashId PuzTo, int iFaceX, int iFaceY );

void DisplayPuzId( PuzzleHashId PuzId );

char GetPiece( PuzzleHashId Puz, int n );

void WriteTable( char *FileName );

void ReadTable( char *FileName );

void Solve( PuzzleHashId Puz );

void Curious( void );

#define WIN_STATE1 (0x0055fea8)

#define WIN_STATE2 (0x0055fba2)

#define WIN_STATE3 (0x0055ef8a)

#define WIN_STATE4 (0x0055bf2a)

#define WIN_STATE5 (0x0054fdaa)

#define WIN_STATE6 (0x0051f7aa)

#define WIN_STATE7 (0x0045dfaa)

#define WIN_STATE8 (0x00157faa)

int main(int argc, char* argv[])

{

printf("Purple/Green Puzzle Solver - Gods Algorithm\n");

printf("sizeof(PuzzleState)=%d Allocating %d bytes\n",

sizeof(PuzzleState), sizeof(PuzzleState) * HASH_SIZE);

// Allocate our storage so that it is intialised to zero.

gpAllStates = (PuzzleStatePtr)calloc(HASH_SIZE, sizeof(PuzzleState));

if (gpAllStates == NULL)

printf("Not enough memory\n");

else

printf("Memory successfully allocated\n");

// Bit of testing here:

//WriteTable("C:\\TEMP\\PrpGrnGod.dat");

//DisplayPuzId(WIN_STATE1);

//PuzzleHashId m1, m2, m3;

//GetPossibleMoves(WIN_STATE1, &m1, &m2, &m3); //printf("GetPossibleMoves(%x)=%x %x %x\n",

// WIN_STATE1, m1, m2, m3);

//DisplayPuzId(m1);

//DisplayPuzId(m2);

//DisplayPuzId(m3);

//exit(0);

// End

#if 0

// Make the table

PopulateTableBFS();

WriteTable("C:\\TEMP\\PrpGrnGod.dat");

#endif

// Cheat and read it in from a file - should speed things up

// a bit!

ReadTable("C:\\TEMP\\PrpGrnGod.dat");

// Now need to solve the thing!

PuzzleHashId ScrambledState = 0x76bd98;

Solve(ScrambledState);

//Curious();

return 0;

}

// Show some statistics

void Curious()

{

for( int i=0; i<92400; i++ )

{

if (gpAllStates[i].Depth > 22)

{

DisplayPuzId(gpAllStates[i].PuzState);

}

void Solve( PuzzleHashId Puz )

{

int i;

for( i=0; i<92400; i++ )

{

if (gpAllStates[i].PuzState == Puz)

break;

}

if ( i == 92400 )

{

printf("ERROR - Puzzle state %x not found in table\n", Puz);

exit(-1);

}

printf("State %x is %d moves from solved\n", Puz, gpAllStates[i].Depth);

{

DisplayPuzId(gpAllStates[i].PuzState);

i = gpAllStates[i].From;

}

while( gpAllStates[i].Depth != 1 );

DisplayPuzId(gpAllStates[i].PuzState);

}

// This is my Breadth First Search attempt at Populate Table

#define MAX_DEPTH 93000

void PopulateTableBFS()

{

unsigned int uiDepth;

unsigned int uiHPos;

int NewNodeFound=1;

int FoundNode1;

int FoundNode2;

int FoundNode3;

PuzzleHashId NewPuzTo1, NewPuzTo2, NewPuzTo3;

// Pre-populate the states array with the winning states

gpAllStates[giNextState].Depth = 1;