OJ Board

Code: Select all

#include <stdio.h>
#include <string.h>

/* Final state of the problema */
int sol[] = {0,3,4,3,0,5,6,5,0,1,2,1,0,7,8,7,0,9,10,9,0,1,2,1};
/* Actual state */
int v[24];

/* Rotates the vector */
void Rotar(int rotacion) {
	int vtmp[24];
	int i;

	/* Get a copy of the actual state */
	memcpy(vtmp, v, sizeof(v));

	/* 1 Left Wheel Clockwise rotation */
	if(rotacion == 1) {
		for(i=0;i<12;i++) {
			v[(i+2)%12] = vtmp[i%12];
		}		
		v[21] = v[9];
		v[22] = v[10];
		v[23] = v[11];		
	}
	/* 2 Right Wheel Clockwise rotation */
	else if(rotacion == 2) {
		for(i=2;i<12;i++) {
			v[i-2+12] = vtmp[i+12];
		}		
		v[22] = vtmp[12];
		v[23] = vtmp[13];
		v[9] = v[21];
		v[10] = v[22];
		v[11] = v[23];
	}
	/* 3 Left Wheel Counter-Clockwise rotation */
	else if(rotacion == 3) {
		for(i=2;i<12;i++) {
			v[i-2] = vtmp[i];
		}		
		v[21] = v[9] = vtmp[11];
		v[22] = v[10] = vtmp[0];
		v[23] = v[11] = vtmp[1];
	}
	/* 4 Right Wheel Counter-Clockwise rotation */
	else if(rotacion == 4) {
		for(i=0;i<12;i++) {
			v[((i+2)%12)+12] = vtmp[(i%12)+12];
		}
		v[12] = vtmp[22];
		v[13] = vtmp[23];
		v[9] = v[21];
		v[10] = v[22];
		v[11] = v[23];
		
	}
}

/* returns 1 if we've found the solution */
int Solucion(int *s) {
	int i;
	for(i=0;i<24;i++) {
		if(s[i] != sol[i]) return 0;
	}
	return 1;
}

/* Generates another level */
void Generar(int nivel, int *s) {		
		/* Undo previous rotation */
		if(s[nivel] == 1) Rotar(3);
		if(s[nivel] == 2) Rotar(4);
		if(s[nivel] == 3) Rotar(1);
		if(s[nivel] == 4) Rotar(2);
		s[nivel]++;
		if(nivel>0) {
			if((s[nivel-1] == 1) && (s[nivel] == 3)) s[nivel]++;
			else if((s[nivel-1] == 2) && (s[nivel] == 4)) s[nivel]++;
			else if((s[nivel-1] == 3) && (s[nivel] == 1)) s[nivel]++;
			else if((s[nivel-1] == 4) && (s[nivel] == 2)) s[nivel]++;
		}
		
		if(s[nivel] <= 4)
		{
			Rotar(s[nivel]);			
		}
}

/* returns 1 if there's no more brothers */

int NoMasHermanos(int nivel, int *s) {
	if(s[nivel] == 4) return 1;
	else return 0;
}

/* Backtracking */
void buscar(int *s) {
	int i, j, nivel = 0, fin = 0;
	/* s = initial solution */
	for(i=0;i<16;i++) s[i] = 0;
	while(nivel>=0) {
		Generar(nivel, s);		
		if(s[nivel] > 4) {
			s[nivel] = 0;	
			nivel--;
			continue;
		}
		if(Solucion(v)) {
			for(j=0;j<=nivel;j++) printf("%d", s[j]);
			printf("\n");
			return;
		}
		else if(nivel<15) {
			nivel++;
		}
		else {
			while(NoMasHermanos(nivel, s) && nivel >= 0 ) {
				Rotar(2);
				s[nivel] = 0;	
				nivel--;				
			}
		
		}
	}
	printf("NO SOLUTION WAS FOUND IN 16 STEPS\n");
}

/* Start */
int main() {
	int s[16];	
	int i, j, casos;
	scanf("%d", &casos);
	for(i=0;i<casos;i++) {
		for(j=0;j<24;j++) {
			scanf("%d", &v[j]);
		}
		if(Solucion(v)) printf("PUZZLE ALREADY SOLVED\n");
		else buscar(s);
	}
	return 0;
}