/*
	Solitaire solver
	(C) 2001 William Benfold
	wb199@soton.ac.uk
*/	




#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "sparse.h"



#define EMPTY   	0
#define FILLED  	1
#define OUTSIDE 	2


#define UNSOLVED 	0
#define SOLVED   	1


#define SYM_NONE 	0
#define SYM_H    	1
#define SYM_V   	2
#define SYM_R2		4
#define SYM_R4		8

#define moveCount count[SYM_NONE]

#define NUM_SYM_TYPES 4

#define MASK 0
#define CRITERIA 1

#define START board[m->sx][m->sy]
#define MIDDLE board[m->sx+m->xv][m->sy+m->yv]
#define END board[m->sx+m->xv+m->xv][m->sy+m->yv+m->yv]

#define PROGRESS_LIMIT 16


typedef long long BOARD_TYPE;

BOARD_TYPE _board;

BOARD_TYPE _moves[NUM_SYM_TYPES][76][2];


typedef struct{
	int sx,sy,xv,yv;
}Move;


int board[7][7];
int pieceCount;
int startx,starty;
Move *moves[NUM_SYM_TYPES][100];
int count[NUM_SYM_TYPES];

unsigned char **sparseTable;


BOARD_TYPE coordToBit(int x, int y)
{
	int pos;
	switch(y)
	{
		case 0:		pos = x-2;
					break;
		case 1:		pos = x+1;
					break;
		case 5:		pos = x+25;
					break;
		case 6:		pos = x+28;
					break;
		default:	pos = x-8 + y*7;
	}
	return ((BOARD_TYPE) 1) << pos;
}

void dump(BOARD_TYPE *m)
{
	printf("[%x ",m[0]);
	printf("%x]",m[1]);
}


void generateMoveCodes()
{
	int i,j;
	int tmp;
	for(i=0; i<NUM_SYM_TYPES; i++)
		for(j=0; j<count[i]; j++)
		{
			Move *m = moves[i][j];
			_moves[i][j][MASK]  = coordToBit(m->sx         ,m->sy        );
			_moves[i][j][MASK] |= coordToBit(m->sx+m->xv   ,m->sy+m->yv  );
			_moves[i][j][MASK] |= coordToBit(m->sx+2*m->xv ,m->sy+2*m->yv);
			
			_moves[i][j][CRITERIA] = coordToBit(m->sx, m->sy) | coordToBit(m->sx+m->xv, m->sy+m->yv);
		}
}
			
			
			

#ifdef SYM

int testMoveSymH(Move *m1, Move *m2)
{
	return (((6-m1->sx) == m2->sx) && (m1->xv == -m2->xv) && (m1->sy==m2->sy) && (m1->yv==m2->yv))?SYM_H:0;
}

int testMoveSymV(Move *m1, Move *m2)
{
	return (((6-m1->sy) == m2->sy) && (m1->yv == -m2->yv) && (m1->sx==m2->sx) && (m1->xv==m2->xv))?SYM_V:0;
}

int testMoveSymR2(Move *m1, Move *m2)
{
	return (m1->sx == (6-m2->sx)) && (m1->sy == (6-m2->sy)) && (m1->xv==-m2->xv) && (m1->yv==-m2->yv);
}

void cacheSym(int sym, Move *m)
{
	if((board[m->sx][m->sy]!=OUTSIDE) && (board[m->sx+m->xv][m->sy+m->yv]!=OUTSIDE)  && (board[m->sx+2*m->xv][m->sy+2*m->yv]!=OUTSIDE))
	{
		moves[sym][count[sym]++] = m;
		//printMove(m);
	}
}

int testSym(int sym, Move *m1, Move *m2)
{
	//printf("  testing ");
	//printMove(m1);
	//printMove(m2);
	if(sym & SYM_H)
		if(testMoveSymH(m1,m2))
			return 1;
			
	if(sym & SYM_V)
		if(testMoveSymV(m1,m2))
			return 1;
	
	//printf("found symmetry  ");		
	return 0;
}

		

void cacheSymmetries()
{
	int i,j,sym;
	
	for(i=1; i<4; i++)
		count[i] = 0;

	for(i=0; i<moveCount; i++)
		for(sym=1; sym<4; sym++)
		{
			int alreadyThere = 0;
			for(j=0; j<count[sym]; j++)
				if(testSym(sym,moves[SYM_NONE][i],moves[sym][j]))
					alreadyThere = 1;
			if(!alreadyThere)
				cacheSym(sym,moves[SYM_NONE][i]);
		}
	fprintf(stderr,"SYM_H       reduced to %d entries\n",count[SYM_H]);
	fprintf(stderr,"      SYM_V reduced to %d entries\n",count[SYM_V]);
	fprintf(stderr,"SYM_H SYM_V reduced to %d entries\n",count[SYM_H+SYM_V]);
}

int findSymmetries()
{
	int i,j,code=0;
	
	for(i=0; i<3; i++)
		for(j=0; j<7; j++)
			if(board[i][j]!=board[6-i][j])
				goto foo;
	code |= SYM_H;
	
	foo:
	
	for(i=0; i<7; i++)
		for(j=0; j<3; j++)
			if(board[i][j]!=board[i][6-j])
				goto bar;
	code |= SYM_V;
	
	bar:
				
	return code;
}


#endif

Move *findMove(BOARD_TYPE *m)
{
	int i;
	for(i=0; i<count[SYM_NONE]; i++)
		if(_moves[SYM_NONE][i] == m)
			return moves[SYM_NONE][i];
	printf("The impossible has happened.");
	exit(-1);
}

void printMove(Move *m)
{
	printf("(%d,%d) to (%d,%d)\n",m->sx,m->sy,m->sx+2*m->xv,m->sy+2*m->yv);
}

void initBoard()
{
	int i,j;
	for(i=0; i<7; i++)
		for(j=0; j<7; j++)
			if((i<2 || i>4) && (j<2 || j>4))
				board[i][j] = OUTSIDE;
			else
				board[i][j] = FILLED;
	pieceCount = 32;
}



void cacheMove(int x, int y, int xv, int yv)
{
	if((board[x][y]!=OUTSIDE) && (board[x+xv][y+yv]!=OUTSIDE)  && (board[x-xv][y-yv]!=OUTSIDE))
	{
		Move *m;
		moves[0][count[0]++] = (m = malloc(sizeof(Move)));
		m->sx = x-xv;
		m->sy = y-yv;
		m->xv = xv;
		m->yv = yv;
	}
}

void cacheMoves()
{
	int i,j,k;
	for(i=0; i<7; i++)
		for(j=0; j<7; j++)
		{
			if(i<6 && i>0)
			{
				cacheMove(i,j,1,0);
				cacheMove(i,j,-1,0);
			}
			if(j<6 && j>0)
			{
				cacheMove(i,j,0,1);
				cacheMove(i,j,0,-1);
			}
		}
	fprintf(stderr,"\nCached %d moves\n",moveCount);
}


inline void doMove(BOARD_TYPE *move)
{
	_board ^= move[MASK];
}

inline void undoMove(BOARD_TYPE *move)
{
	_board ^= move[MASK];
}

inline int checkMove(BOARD_TYPE *move)
{
	return ((_board & move[MASK]) == move[CRITERIA]);
}

inline int alreadyTried()
{
	return (*sparseLookup(sparseTable,_board/8) & (1<<(_board&0x07)));
}

inline void setTried()
{
	*sparseLookup(sparseTable,_board/8) |= (1<<(_board&0x07));
}


void progress(int recLevel, int pos)
{
	int i;
	for(i=0;i<PROGRESS_LIMIT-recLevel+1; i++)
		fprintf(stderr,"\b\b\b");
	fprintf(stderr,"%02d ",pos);
	for(i=0;i<PROGRESS_LIMIT-recLevel; i++)
		fprintf(stderr,"   ");
}
	

int solve(int recLevel)
{
	int i,s=0;
	BOARD_TYPE *m;
	
	if(_board==coordToBit(startx,starty))
		return SOLVED;
	
	
	#ifdef CACHE
	if(recLevel<26 && (recLevel %2==0))
		if(alreadyTried())
			return UNSOLVED;
	
	#endif
	

	#ifdef SYM
	s = findSymmetries();
	#endif
	
	
	for(i=0; i<count[s]; i++)
	{
		#ifdef PROGRESS
		if(recLevel<= PROGRESS_LIMIT)
			progress(recLevel,i);
		#endif
		
		m = _moves[s][i];
		if(checkMove(m))
		{
			doMove(m);
			if(solve(recLevel+1))
			{
				printMove(findMove(m));
				return SOLVED;
			}
			undoMove(m);
		}
	}
	
	#ifdef CACHE
	setTried();
	#endif
	
	return UNSOLVED;
}

void initBoardRegister()
{
	int i,j;
	_board = 0;
	for(i=0; i<7; i++)
		for(j=0; j<7; j++)
			if(board[i][j]==FILLED)
				_board |= coordToBit(i,j);
}

int main(int argc, char **argv)
{
	unsigned int i,s,t,result;
	
	printf("\nSolitaire Solver\n");
	printf("(C) 2001 William Benfold\n");
	printf("wb199@soton.ac.uk\n");
	
	
	if(argc!=3)
	{
		printf("Usage: sol <startx> <starty>\n");
		exit(0);
	}
	
	
	printf("\nCompiled on %s %s\n",__DATE__,__TIME__);
	printf("compile options: ");
	#ifdef SYM
	printf("SYM ");
	#endif
	#ifdef CACHE
	printf("CACHE ");
	#endif
	#ifdef PROGRESS
	printf("PROGRESS ");
	#endif
	printf("CHUNK_SIZE=%d ",CHUNK_SIZE);
	printf("sizeof(BOARD_TYPE)=%dbit\n",8*sizeof(BOARD_TYPE));
	
	
	startx = atoi(argv[1]);
	starty = atoi(argv[2]);
	
	printf("Solving for start/end position (%d,%d)\n",startx,starty);
	
	initBoard();
	cacheMoves();
	#ifdef SYM
	cacheSymmetries();
	#endif
	generateMoveCodes();
	board[startx][starty] = EMPTY;
	initBoardRegister();
	#ifdef CACHE
	sparseTable = makeSparseTable(((unsigned int) 1)<<30);
	#endif
	
	puts("----");
	
		
	t = time(0);
	
	result = solve(0);
	if(result==UNSOLVED)
		printf("No solution exists.\n");
	
	t = time(0) - t;
	printf("\nSeconds taken: %d",t);
	
	return result;
}