JUEGO_8PUZZLE.c

// JUEGO DEL 8 PUZZLE
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <dos.h>

typedef struct tableros
	{
	int tabla[4][4];
	struct tableros	 *sig;
	};

typedef struct tableros tablero;
tablero	inicio,final,*hijos;

int ix,iy;

void busca_inicio(int x, int y)
	{
	int j,k;
	for (j=0;j<4;j++)
		{
		for (k=0;k<4;k++)
			{
			if (inicio.tabla[j][k]==0)
				{
				iy=j;
				ix=k;
				break;
				}
			}
		}
	gotoxy(x,y);
	printf ("x=%d,y=%d",ix+1,iy+1);
	}

void tabla_inicio(int x,int y)
	{
	int j,k,l,m,c;
	int pass=0;
	randomize();
	for (j=0;j<4;j++)
		{
		for (k=0;k<4;k++)
			{
			gotoxy(x+k*5,y+j);
			pass=0;
			while(1)
				{
				inicio.tabla[j][k]=random(16);
				for (l=0;l<=j;l++)
					{
					if (j==0)
						c=k;
					else
						c=4;
					if (l==j) c=k;
					for (m=0;m<c;m++)
					   {
					   if (inicio.tabla[j][k]==inicio.tabla[l][m])
							pass++;
					   }
					}
				 if (pass==0)
					break;
				 else
					pass=0;

				}
			printf ("%d",inicio.tabla[j][k]);
			}
		}
	}

void tabla_final(int x,int y)
	{
	int j,k;
	int cont=1;
	for (j=0;j<4;j++)
		{
		for (k=0;k<4;k++)
			{
			gotoxy(x+k*5,y+j);
			final.tabla[j][k]=cont++;
			if (j==3 && k==3) final.tabla[j][k]=0;
			printf("%d",final.tabla[j][k]);
			}
		}
	}

int meta(tablero uno,tablero dos)
	{
	int j,k;
	for (j=0;j<4;j++)
		{
		for (k=0;k<4;k++)
			{
			if (uno.tabla[j][k]!=dos.tabla[j][k])
				return 0;
			}
		}
	return 1;
	}

tablero *agregar_lista()
	{
	int j,k;
	tablero *aux=(tablero *)malloc(sizeof(tablero)),*otro;
	if (aux==NULL)
		{
		printf ("No existe suficiente Memoria");
		exit(1);
		}
	for (j=0;j<4;j++)
		{
		for (k=0;k<4;k++)
			{
			aux->tabla[j][k]=inicio.tabla[j][k];
			}
		}
	aux->sig=NULL;
	if (hijos==NULL)
		hijos=aux;
	else
		{
		for (otro=hijos;otro->sig!=NULL;otro=otro->sig);
		otro->sig=aux;
		}
	return aux;
	}

void presenta(tablero cual,int x, int y)
	{
	int j,k;
	for (j=0;j<4;j++)
		{
		for (k=0;k<4;k++)
			{
			gotoxy(x+k*5,y+j);
			printf ("%d ",cual.tabla[j][k]);
			}
		}
	}

int derecha()
	{
	busca_inicio(1,1);
	if (ix==3) return 0;
	inicio.tabla[iy][ix]=inicio.tabla[iy][ix+1];
	inicio.tabla[iy][ix+1]=0;
	return 1;
	}

int izquierda()
	{
	busca_inicio(1,1);
	if (ix==0) return 0;
	inicio.tabla[iy][ix]=inicio.tabla[iy][ix-1];
	inicio.tabla[iy][ix-1]=0;
	return 1;
	}

int arriba()
	{
	busca_inicio(1,1);
	if (iy==0) return 0;
	inicio.tabla[iy][ix]=inicio.tabla[iy-1][ix];
	inicio.tabla[iy-1][ix]=0;
	return 1;
	}

int abajo()
	{
	busca_inicio(1,1);
	if (iy==0) return 0;
	inicio.tabla[iy][ix]=inicio.tabla[iy+1][ix];
	inicio.tabla[iy+1][ix]=0;
	return 1;
	}

void  copiar(tablero *destino,tablero fuente)
	{
	int j,k;
	for (j=0;j<4;j++)
		{
		for (k=0;k<4;k++)
			{
			destino->tabla[j][k]=fuente.tabla[j][k];
			}
		}
	}

int es_repetido(tablero cual)
	{
	tablero *aux;
	for (aux=hijos;aux!=NULL;aux=aux->sig)
		{
		if (meta(cual,*aux))
			return 1;
		}
	return 0;
	}

int movimiento(int x, int y)
	{
	char movimientos;
	tablero aux;
	copiar(&aux,inicio);
	if (derecha()&&!es_repetido(inicio))
		{
		presenta(inicio,x,y);
		delay(300);
		movimientos='D';
		if (meta(inicio,final))
			{
			printf ("%c",movimientos);
			return 1;
			}
		agregar_lista();
		if(movimiento(1,10))
			{
			printf ("%c",movimientos);
			return 1;
			}
		}
	else
		{
		copiar(&inicio,aux);
		}
	if (izquierda()&&!es_repetido(inicio))
		{
		presenta(inicio,x,y);
		delay(300);
		movimientos='I';
		if (meta(inicio,final))
			{
			printf ("%c",movimientos);
			return 1;
			}
		agregar_lista();
		if(movimiento(1,10))
			{
			printf ("%c",movimientos);
			return 1;
			}
		}
	else
		copiar(&inicio,aux);
	if (arriba()&&!es_repetido(inicio))
		{
		presenta(inicio,x,y);
		delay(300);
		movimientos='A';
		if (meta(inicio,final))
			{
			printf ("%c",movimientos);
			return 1;
			}
		agregar_lista();
		if(movimiento(1,10))
			{
			printf ("%c",movimientos);
			return 1;
			}
		}
	else
		{
		copiar(&inicio,aux);
		}
	if (abajo()&&!es_repetido(inicio))
		{
		presenta(inicio,x,y);
		delay(300);
		movimientos='Ab';
		if (meta(inicio,final))
			{
			printf ("%c",movimientos);
			return 1;
			}
		agregar_lista();
		if(movimiento(1,10))
			{
			printf ("%c",movimientos);
			return 1;
			}
		}
	else
		{
		copiar(&inicio,aux);
		}
	return 0;
	}

int main(void )
	{
	clrscr();
	hijos=NULL;
	tabla_inicio(5,2);
	getch();
	tabla_final(40,2);
	getch();
	busca_inicio(1,1);
	gotoxy(1,22);
	if (meta(inicio,final))
		{
		printf ("Es igual inicio y Final");
		getch();
		return 0;
		}
	else
		{
		printf ("Comenzara la Busqueda");
		}
	agregar_lista();
	movimiento(5,10);
	getch();
	return 1;
	}