#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<math.h>
#include<time.h>

#define num 4

#define arriba 72
#define abajo 80
#define izquierda 75
#define derecha 77

void generar_rompecabezas();
void imprimir_rompecabezas();
void comprobar_completo();
void mover();
void desordenar();

int main(){
	int puzzle[num][num],reg=0, mov;
	//unsigned char mov;
	generar_rompecabezas(puzzle);
	desordenar(250,puzzle);
	imprimir_rompecabezas(puzzle);

	do{
	system("cls");
	imprimir_rompecabezas(puzzle);
	comprobar_completo(puzzle, reg);
	if(reg==0){
	mov=getch();
	mover(mov,puzzle);
	}
	else{
		system("cls");
		printf("Completado");
	}
	}
	while(reg!=1);

	getch();
	return 0;
}



void generar_rompecabezas(int puzzle[num][num]){
	int aux=1;
	int x,y;

	for(x=0;x<num;x++){
		for(y=0;y<num;y++){
			puzzle[x][y]=aux;
			if(x==num-1 && y==num-1){
				puzzle[x][y]=0;
			}
			//printf("matriz %d %d = %d\n",x,y,puzzle[x][y]);
			aux++;
		}
	}
}

void imprimir_rompecabezas(int puzzle[num][num]){
	int x,y;

	for(x=0;x<num;x++){
		if(x==0)
			printf("\t\t\t---------------------\n");
		printf("\t\t\t|");
		for(y=0;y<num;y++){
			if(puzzle[x][y]<10){
				printf(" ");
			}
			if(puzzle[x][y]==0)
				printf("   |");
			else
				printf(" %d |", puzzle[x][y]);
		}
		printf("\n");
		printf("\t\t\t---------------------\n");
	}
}

void comprobar_completo(int puzzle[num][num],int reg){
	int x,y;
	int aux=1;
	int z=num*num;

	for(x=0;x<num;x++){
		for(y=0;y<num;y++){
			if(puzzle[x][y]==aux){
				aux++;
			}
		}
	}


	if(aux==z){
		printf("resuelto");
		reg=1;

	}
	else{
		printf("No Resuelto");
		reg=0;
	}

}

void mover(int direccion, int puzzle[num][num]){
	int x,y,aux;
	for(x=0;x<num;x++){
		for(y=0;y<num;y++){
			if(puzzle[x][y]==0){
				switch(direccion){
					case izquierda:
						if(y!=num-1){
							aux=puzzle[x][y];
							puzzle[x][y]=puzzle[x][y+1];
							puzzle[x][y+1]=aux;
							printf("\nMovimiento izquierda\n");
						}
						break;

					case derecha:
						if(y!=0){
							//printf("%d a cambiar con %d",puzzle[x][y], puzzle[x][y-1]);
							aux=puzzle[x][y];
							puzzle[x][y]=puzzle[x][y-1];
							puzzle[x][y-1]=aux;
							printf("\nMovimiento derecha\n");
						}
						break;

					case arriba:
						if(x!=num-1){
							aux=puzzle[x][y];
							puzzle[x][y]=puzzle[x+1][y];
							puzzle[x+1][y]=aux;
							printf("\nMovimiento Arriba\n");
						}
						break;

					case abajo:
						if(x!=0){
							aux=puzzle[x][y];
							puzzle[x][y]=puzzle[x-1][y];
							puzzle[x-1][y]=aux;
							printf("\nMovimiento abajo\n");
						}
						break;
				}
			}
		}
	}
}

void desordenar(int cantidad, int puzzle[num][num]){
	int x,opc;
	srand (time(NULL));
	for(x=0;x<cantidad;x++){

		opc=(rand()%4+1);

		switch(opc){
		case 1:
			mover(arriba, puzzle);
			break;
		case 2:
			mover(abajo, puzzle);
			break;
		case 3:
			mover(izquierda, puzzle);
			break;
		case 4:
			mover(derecha, puzzle);
			break;
		}
	}
}

typedef struct paises{
	int IDpais;
	char Pais[20];
	int NoParticipantes;
	int NoMedallas;

	struct paises* p;
} Paises;

Paises*PAIprimero=NULL;
Paises*PAIultimo=NULL;

void insertarPaisesG(int ID, char Nombre[]){
	Paises * nuevo;
	nuevo = (Paises *)malloc(sizeof(Paises));

	nuevo->IDpais=ID;
	strcpy(nuevo->Pais, Nombre);


	if(PAIprimero->p!=PAIultimo){
		PAIprimero=nuevo;
		PAIprimero->p=PAIultimo;

	}
	else{
		nuevo->p=NULL;
		PAIultimo->p=nuevo;
		PAIultimo=nuevo;
	}

}







void guardarPaises(){
	printf("\n\n\nGuardando informaci�n de paises");
	FILE * archivo = fopen("Paises.dat", "wb");
	if(archivo == NULL){
		printf("\n\n\nError al guardar en archivo");
		return;
	}

	Paises * recorre = PAIprimero;
	while (recorre != NULL){
		fwrite(recorre, sizeof(Paises), 1, archivo);
		recorre = recorre->p;
		}

	fclose(archivo);
}








void cargarPaises(){
	FILE * archivo = fopen("Paises.dat", "rb");
	if(archivo == NULL){
		printf("\n\n\nError al cargar desde archivo");
		return;
	}

	Paises * actual = (Paises *) malloc(sizeof(Paises));
	int leidos;
	do{
		leidos = fread(actual, sizeof(Paises), 1, archivo);
		if (leidos == 1)
			insertarPaisesG(actual->IDpais, actual->Pais);
	} while (leidos == 1);

	fclose(archivo);
}

void generar_puzzle(int puzzle[N][N]){

     int i,j,num;
     num=1;
     for(i=0;i<N;i++){
          for(j=0;j<N;j++){
               puzzle[i][j]=num;
               num++;
               if(i==3 && j==3){
               puzzle[i][j]=0;
			   }
          }
     }
}

void imprimir(int puzzle[N][N]){
     int i,j;
     for(i=0;i<N;i++){
          for(j=0;j<N;j++){
               if(puzzle[i][j]==0)
               printf(" |");
               else
               printf("%3d |",puzzle[i][j]);
               }
          printf("\n");
          if(i<N-1)
          printf("\t\t\t ------+-----+-----+------\n");
          }
     }

typedef struct nodo{
	int llave;
	struct nodo * sig; /* auto referencia */
}nodoLista;



void eliminarLista(){
	nodoLista* anterior;
	nodoLista* actual;
	nodoLista* siguiente;
	nodoLista* recorre=primero;

	int op;
	printf("Cual es el entero a eliminar?");
	scanf("%d", &op);

	anterior=primero;
	actual=primero;
	siguiente=primero->sig;

	while(recorre != NULL){

		if(recorre->llave == op){
			anterior->sig=siguiente;
			free(actual);
		}
		else{}
		anterior=recorre;
		recorre = recorre->sig;
		actual=recorre;
		if(recorre != NULL){siguiente = recorre->sig;}
	}
}

#include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define TRUE 1

typedef int boolean;

boolean estaVacia();

typedef struct nodo{
	int llave;
	struct nodo * sig; /* auto referencia */
}nodoLista;

nodoLista * primero = NULL;
nodoLista * ultimo = NULL;

void insertarInicio();
void insertarFinal();
void mostrarLista();
void eliminarLista();

int main(void) {
	setvbuf(stdout, NULL, _IONBF, 0);
	int opcion;
	do{
		printf("\n\nMENU");
		printf("\n0.- Salir");
		printf("\n1.- Agregar un nodo al inicio");
		printf("\n2.- Mostrar los valores de la lista");
		printf("\n3.- Agregar un nodo al final");
		printf("\n4.- Eliminar un elemento");

		printf("\n\nDame tu opci�n");
		scanf("%d", &opcion);

		switch(opcion){
			case 0:
				break;
			case 1:
				insertarInicio();
				break;
			case 2:
				mostrarLista();
				break;
			case 3:
				insertarFinal();
				break;
			case 4:
				eliminarLista();
				break;
		}

	} while (opcion != 0);


	return EXIT_SUCCESS;
}

void insertarInicio(){
	nodoLista * nuevo;
	nuevo = (nodoLista *)malloc(sizeof(nodoLista));

	printf("\n\nDame el valor de la llave");
	scanf("%d", &nuevo->llave);
	nuevo->sig = primero;
	primero = nuevo;

	if(primero->sig == NULL)
		ultimo = primero;
}

void insertarFinal(){
	if (estaVacia()){
		insertarInicio();
		return;
	}

	nodoLista * nuevo;
	nuevo = (nodoLista *)malloc(sizeof(nodoLista));

	printf("\n\nDame el valor de la llave");
	scanf("%d", &nuevo->llave);
	nuevo->sig = NULL;
	ultimo->sig = nuevo;
	ultimo = nuevo;
}

void mostrarLista(){
	if (estaVacia()){
		printf("\n\nLa lista est� vac�a");
		return;
	}
	nodoLista * recorre = primero;
	while (recorre != NULL){
		printf("%d  ", recorre->llave);
		recorre = recorre->sig;
	}
}

void eliminarLista(){
	nodoLista* anterior;
	nodoLista* actual;
	nodoLista* siguiente;
	nodoLista* recorre=primero;

	int op;
	printf("Cual es el entero a eliminar?");
	scanf("%d", &op);

	anterior=primero;
	actual=primero;
	siguiente=primero->sig;

	while(recorre != NULL){

		if(recorre->llave == op){
			anterior->sig=siguiente;
			free(actual);
		}
		else{}
		anterior=recorre;
		recorre = recorre->sig;
		actual=recorre;
		if(recorre != NULL){siguiente = recorre->sig;}
	}
}

boolean estaVacia(){
	if (primero == NULL)
		return TRUE;
	else
		return FALSE;
}