¿Imposible? Juego de Rompecabezas imposible

[AlbertoBSD]

Bueno les dejo aquí el código del Juego del imposible...

Se juega usando las teclas w,a,s,d como si fueran las flechas del teclado, esta seguida de un enter.

El reto "imposible" es definir dada la matriz inicial llegar a su forma inversa:

Código [Seleccionar] Expandir

[ 1][ 2][ 3][ 4]
[ 5][ 6][ 7][ 8]
[ 9][10][11][12]
[13][14][15][  ]

Código [Seleccionar] Expandir

[15][14][13][12]
[11][10][ 9][ 8]
[ 7][ 6][ 5][ 4]
[ 3][ 2][ 1][  ]


Y si, es IMPOSIBLE

Código (c) [Seleccionar] Expandir

/*
Juego del Imposible | Programación en C

[ 1][ 2][ 3][ 4]
[ 5][ 6][ 7][ 8]
[ 9][10][11][12]
[13][14][15][  ]
               
w
asd

Contacto
Twitter: @albertobsd
Email: alberto.bsd@gmail.com
*/
#include<stdio.h>

void imprimir_tablero();

int tabla[4][4];
int x= 3,y =3;

int main() {
int i = 0,j =0,contador = 1;
char caracter,enter;
//Inicializar la tabla o matriz de juego
while(i < 4) {
j = 0;
while(j < 4) {
tabla[i][j] = contador;
//printf("[%2i]",tabla[i][j]);
j++;
contador++;
}
printf("\n");
i++;
}
tabla[y][x] = 0;
imprimir_tablero();
do {
caracter = getchar();
enter = getchar();
switch(caracter) {
case 'w': //arriba
if(y <= 2) {
//Movimiento de ficha
tabla[y][x] = tabla[y+1][x];
tabla[y+1][x] = 0;
imprimir_tablero();
y++;
}
else {
printf("Fuera de los limites\n");
}
break;
case 's': //abajo
if(y >= 1) {
//Movimiento de ficha
tabla[y][x] = tabla[y-1][x];
tabla[y-1][x] = 0;
imprimir_tablero();
y--;
}
else {
printf("Fuera de los limites\n");
}
break;
case 'a': //izquierda
if(x <= 2) {
//Movimiento de ficha
tabla[y][x] = tabla[y][x+1];
tabla[y][x+1] = 0;
imprimir_tablero();
x++;
}
else {
printf("Fuera de los limites\n");
}

break;
case 'd': //derecha
if(x >= 1) {
tabla[y][x] = tabla[y][x-1];
tabla[y][x-1] = 0;
imprimir_tablero();
x--;
}
else {
printf("Fuera de los limites\n");
}
break;
case '0': //Salida
break;
default:
printf("Caracter Incorrecto");
break;
}
printf("Caracter : %c\n",caracter);
}while(caracter != '0');
return 0;
}

void imprimir_tablero() {
int i = 0,j;
while(i < 4) {
j = 0;
while(j < 4) {
if(tabla[i][j] != 0) {
printf("[%2i]",tabla[i][j]);
}
else {
printf("[  ]");
}
j++;
}
printf("\n");
i++;
}
}


Video:

[youtube=640,360]https://www.youtube.com/watch?v=etbTecakXFg[/youtube]

Dejo también un Documento donde se explica de forma matemática por que es imposible el acomodo invertido dada una posición inicial.

http://miscelaneamatematica.org/Misc40/Campos_r.pdf

Aclaro que ese documento no es mio, lo realizaron los autores ahí señalados en el mismo.

Saludos!

[class_OpenGL]

No sé si será imposible o no, pero yo me quedé cerca XDD:



Por cierto, bien programado

[AlbertoBSD]

Por cierto, bien programado

Si vieras que si me equivocaba un buen al momento de mover las fichas me fallaba el desplazamiento o se movian para otro lado xD....


Asi se queda, no es posible acomodar ese ultimo uno.

Según explican en el documento final


Estaba pensando en un reto para este juego seria crear un grafo con todas las posibilidades dada una configuración inicial y apartir de ahi determinar si una combinación dada es posible o no dada la configuración inicial.


El reto tiene de todo, desde busqueda, creacion del grafo hasta eficiencia de los algoritmos para buscar.

Saludos

[Sr Limone]

Muy buen juego  ... Felicidades 

[AlbertoBSD]

Gracias  

Estaba pensando en la estructura del nodo para el grafo mencionado y esta seria la base:

Código (c) [Seleccionar] Expandir

struct nodo {
int tabla[4][4];
int x,y;
struct nodo *arriba;
struct nodo *abajo;
struct nodo *izquierda;
struct nodo *derecha;
bool visitado;
};

La idea del algoritmo para generar todas las posibles combinaciones del juego es mas o menos la siguiente.

Declarar el nodo inicial (Primera matriz) y apartir de ahi declararlo como pivote,

Generar las 4 configuraciones posibles para cada arista (arriba, abajo, izquierda, derecha) marcar como NULL aquellas donde no exista la posibilidad,

Con cada configuracion que generemos tendremos que validar que esta no exista previamente en el Grafo y si existe simplemente apuntar la arista que la genero al Nodo adecuado.

Es algo complejo pero se puede.

sobre la variable de visitado todavia no estoy 100% seguro de como implementarla.

Saludos



dejo aqui un codigo como el descrito para el grafo,

Código (c) [Seleccionar] Expandir

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

struct nodo {
unsigned char tabla[4][4];
unsigned char x,y;
struct nodo *arriba;
struct nodo *abajo;
struct nodo *izquierda;
struct nodo *derecha;
};

void imprimir_tablero(struct nodo *n);
struct nodo *crear_nodo(struct nodo *previo, char movimiento);

int main() {
struct nodo *grafo = NULL;

//Inicializamos el grafo (Primer Nodo)
int i = 0,j =0,contador = 0;
grafo = calloc(sizeof(struct nodo),1);
while(i < 4) {
j = 0;
while(j < 4) {
grafo->tabla[i][j] = contador+1;
j++;
contador++;
}
i++;
}
grafo->x = 3;
grafo->y = 3;
grafo->tabla[grafo->y][grafo->x] = 0;


//Generamos los nodos vecinos:
grafo->arriba = crear_nodo(grafo,'w');
grafo->abajo = crear_nodo(grafo,'s');
grafo->izquierda = crear_nodo(grafo,'a');
grafo->derecha = crear_nodo(grafo,'d');

//Imprimimos el grafo y los primero 4 nodos vecinos
imprimir_tablero(grafo);
printf("Combinaciones:\n");
printf("Arriba:\n");
imprimir_tablero(grafo->arriba);
printf("Abajo:\n");
imprimir_tablero(grafo->abajo);
printf("Izquierda:\n");
imprimir_tablero(grafo->izquierda);
printf("Derecha:\n");
imprimir_tablero(grafo->derecha);
return 0;
}

struct nodo *crear_nodo(struct nodo *previo, char movimiento) {
struct nodo *n = NULL;
n = calloc(sizeof(struct nodo),1);
if(n != NULL) {
memcpy(n->tabla,previo->tabla,sizeof(int) * 16);
n->x = previo->x;
n->y = previo->y;
switch(movimiento) {
case 'w': //arriba
if(n->y <= 2) {
//Movimiento de ficha
n->tabla[n->y][n->x] = n->tabla[n->y+1][n->x];
n->tabla[n->y+1][n->x] = 0;
n->y++;
}
else {
free(n);
n =NULL;
//printf("Fuera de los limites\n");
}
break;
case 's': //abajo
if(n->y >= 1) {
//Movimiento de ficha
n->tabla[n->y][n->x] = n->tabla[n->y-1][n->x];
n->tabla[n->y-1][n->x] = 0;
//imprimir_tablero();
n->y--;
}
else {
free(n);
n =NULL;
//printf("Fuera de los limites\n");
}
break;
case 'a': //izquierda
if(n->x <= 2) {
//Movimiento de ficha
n->tabla[n->y][n->x] = n->tabla[n->y][n->x+1];
n->tabla[n->y][n->x+1] = 0;
//imprimir_tablero();
n->x++;
}
else {
free(n);
n =NULL;
//printf("Fuera de los limites\n");
}
break;
case 'd': //derecha
if(n->x >= 1) {
n->tabla[n->y][n->x] = n->tabla[n->y][n->x-1];
n->tabla[n->y][n->x-1] = 0;
//imprimir_tablero();
n->x--;
}
else {
free(n);
n =NULL;
//printf("Fuera de los limites\n");
}
break;
}
}
else {
printf("Error de memoria!\nSaliendo\n");
exit(1);
}
return n;
}

void imprimir_tablero(struct nodo *n) {
if(n != NULL) {
int i = 0,j;
while(i < 4) {
j = 0;
while(j < 4) {
if(n->tabla[i][j] != 0) {
printf("[%2i]",n->tabla[i][j]);
}
else {
printf("[  ]");
}
j++;
}
printf("\n");
i++;
}
}
else {
printf("Nodo no valido\n");
}
}

El codigo apartir de un nodo inicial genera los nodos vecinos mediente una funcion para ello, llamada crear_nodo:

Código (c) [Seleccionar] Expandir

struct nodo *crear_nodo(struct nodo *previo, char movimiento) {


Hace falta una lista de todos los nodos validos no repetidos para ir sobre esa misma lista y crear de manera iterativa todos los nodos posibles y una funcion para buscar nodos "repetidos" en valor y hacer que estos sean unicos.

Salida del codigo generado:

Código [Seleccionar] Expandir

[ 1][ 2][ 3][ 4]
[ 5][ 6][ 7][ 8]
[ 9][10][11][12]
[13][14][15][  ]
conbinaciones:
Arriba
Nodo no valido
Abajo
[ 1][ 2][ 3][ 4]
[ 5][ 6][ 7][ 8]
[ 9][10][11][  ]
[13][14][15][12]
Izquierda:
Nodo no valido
Derecha:
[ 1][ 2][ 3][ 4]
[ 5][ 6][ 7][ 8]
[ 9][10][11][12]
[13][14][  ][15]

Saludos!



Bueno ya he hecho el programa para generar los Nodos del grafo, el detalle que consume demasiada memoria.

Código (c) [Seleccionar] Expandir

#include<stdint.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

#define RESERVAR 1000000 //Reserva cada que agota el espacio para RESERVAR cantidad de apuntadores

//Nodo del grafo
struct nodo {
uint32_t id;
uint8_t tabla[4][4];
uint8_t x,y;
struct nodo *aristas[4];
};

//Estructura auxiliar solo para realizar menos comparaciones en el Arbol
struct nodo_comparar {
uint32_t id;
uint64_t v[2];
uint8_t x,y;
struct nodo *aristas[4];
};

//Nodo de un arbol, este solo contiene los apuntadores de un arbol binario y adiconal el valor
//El cual solo es un apuntador a un nodo ya existente del grafo
struct nodo_arbol {
struct nodo_arbol *padre,*izquierdo,*derecho;
struct nodo_comparar *valor;
};

void imprimir_tablero(struct nodo *n);
struct nodo *crear_nodo(struct nodo *previo, char movimiento);
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,struct nodo_comparar *valor);
struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor);
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor);

char *direccion[4] = {"arriba","abajo","izquierda","derecha"};
char dir_char[4] = "wsad";

int main() {
struct nodo_arbol *arbol = NULL,*busqueda = NULL; //Nodos de ARBOL y auxiliar de busqueda
struct nodo *grafo = NULL,*aux1 = NULL,*aux2 = NULL,*pivote = NULL; // Nodos de el GRAFO y auxiliares
struct nodo **lista = NULL; //Lista de todos los nodos existentes del grafo
register int indice = 0,aux_memoria = 0; //Almacenara el numero de nodos totales en la lista previa
register int i = 0,j =0,contador = 0;
//Inicializamos el grafo (Primer Nodo)

grafo = malloc(sizeof(struct nodo));
while(i < 4) {
j = 0;
while(j < 4) {
grafo->tabla[i][j] = contador+1;
j++;
contador++;
}
i++;
}
grafo->x = 3;
grafo->y = 3;
grafo->tabla[grafo->y][grafo->x] = 0;
//Fin de inicializacion de nodo inicial
if(indice == aux_memoria) {
aux_memoria += RESERVAR;
lista = realloc(lista,sizeof(struct nodo*)*(aux_memoria+1)); // Espacio para la lista
}
arbol = agregar_valor_arbol(arbol,(struct nodo_comparar*)grafo); // Guardamos el nodo inicial como apuntador al arbol (NODO Raiz)
lista[indice] = grafo; //Guardamos el nodo del primier elemento del grafo en nuestra lista de nodos
indice++; //Incrementamos el indice en 1 ya que actualmente exitte al menos un indice en la lista
j = 0;
do {
pivote = lista[j];
pivote->id = j;
//imprimir_tablero(pivote);
i = 0;
while(i < 4) {
aux1 = crear_nodo(pivote,dir_char[i]); //Creamos el nodo de la Arista Actual con el movimiento adecuado
if(aux1) {
/*
Si es valido tenemos que validar que la secuencia
generada no exista previamente
*/
busqueda = buscar_nodo_arbol(arbol,(struct nodo_comparar*)aux1); // Buscamos el nodo generado en el arbol, para validar que no exista la misma configuracion en el grafo actual
if(busqueda !=  NULL) { // Si el apuntador es valido entonces ya existe la secuencia de aux1 en el Grafo actual
free(aux1); //Liberamos la secuencia duplicada
pivote->aristas[i] = (struct nodo*)busqueda->valor; //La arista actual apunta a la secuencia qua ya existia
}
else {
pivote->aristas[i] = aux1; //La arista actual apunta a la nueva secuencia (Unica)
if(indice == aux_memoria) {
aux_memoria += aux_memoria;
lista = realloc(lista,sizeof(struct nodo*)*(aux_memoria+1)); // Ajustamos la memoria de la lista de nodos
}
lista[indice] = aux1; //agregamos el nuevo elemento a la lista
indice++; //Incrementamos el indice para la lista
arbol = agregar_valor_arbol(arbol,(struct nodo_comparar*)aux1);// Agregamos el nodo al arbol para posteriormente buscar
}
}
else {
//El nodo no es valido por lo tanto, no hay nada que validar
pivote->aristas[i] = aux1; //Guardamos NULL en la arista actual
}
i++; //Incrementamos el indice de las aristas
}
j++; //Incrementamos el indice de los nodos procesados dentro de la lista de Nodos
if(!(j % 10000)) { // Solo informamos del avance cada 10000 Nodos
printf("%i < %i\n",j,indice);
}
}while(j < indice); //Condicien para continuar procesando nodos
printf("%i < %i\n",j,indice); // Imprimimos contadores finales
j = 0;
while(lista[j] != NULL) {
free(lista[j]); // Liberamos memoria de los nodos del grafo
}
free(lista); // Liberamod memoria la lista
return 0;
}


//Crea un nuevo Nodo en base a un nodo previo y el movimiento usado en el juego
struct nodo *crear_nodo(struct nodo *previo, char movimiento) {
struct nodo *n = NULL;
n = malloc(sizeof(struct nodo));
if(n != NULL) {
memcpy(n->tabla,previo->tabla,sizeof(int) * 18);
/*
n->x = previo->x;
n->y = previo->y;
*/
switch(movimiento) {
case 'w': //arriba
if(n->y <= 2) {
//Movimiento de ficha
n->tabla[n->y][n->x] = n->tabla[n->y+1][n->x];
n->tabla[n->y+1][n->x] = 0;
n->y++;
}
else {
free(n);
n =NULL;
}
break;
case 's': //abajo
if(n->y >= 1) {
//Movimiento de ficha
n->tabla[n->y][n->x] = n->tabla[n->y-1][n->x];
n->tabla[n->y-1][n->x] = 0;
//imprimir_tablero();
n->y--;
}
else {
free(n);
n =NULL;
}
break;
case 'a': //izquierda
if(n->x <= 2) {
n->tabla[n->y][n->x] = n->tabla[n->y][n->x+1];
n->tabla[n->y][n->x+1] = 0;
n->x++;
}
else {
free(n);
n =NULL;
}
break;
case 'd': //derecha
if(n->x >= 1) {
n->tabla[n->y][n->x] = n->tabla[n->y][n->x-1];
n->tabla[n->y][n->x-1] = 0;
//imprimir_tablero();
n->x--;
}
else {
free(n);
n =NULL;
}
break;
}
}
else {
printf("Error de memoria!\nSaliendo\n");
exit(1);
}
return n;
}

//Imprime el estado actual de un Nodo
void imprimir_tablero(struct nodo *n) {
if(n != NULL) {
int i = 0,j;
printf("%p:\n",n);
while(i < 4) {
j = 0;
while(j < 4) {
if(n->tabla[i][j] != 0) {
printf("[%2i]",n->tabla[i][j]);
}
else {
printf("[  ]");
}
j++;
}
printf("\n");
i++;
}
}
else {
printf("Nodo no valido\n");
}
}

//Funcion que busca el lugar adecuado para el nodo en cuestion a agregar
//Usando busqueda binaria y comparando los valores de la tabla
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor) {
struct nodo_arbol *temp,*pivote;
int derecho = false;
if(arbol) {
temp = arbol;
while(temp != NULL) {
pivote = temp;
if(valor->v[0] == temp->valor->v[0]) {
if(valor->v[1] > temp->valor->v[1]) {
temp = temp->derecho;
derecho = true;
}
else {
temp = temp->izquierdo;
derecho = false;
}
}
else {
if(valor->v[0] > temp->valor->v[0]) {
temp = temp->derecho;
derecho = true;
}
else {
temp = temp->izquierdo;
derecho = false;
}
}
}
temp = crear_nodo_arbol(pivote,valor);
if(derecho) {
pivote->derecho = temp;
}
else {
pivote->izquierdo = temp;
}
return arbol;
}
else {
temp = crear_nodo_arbol(NULL,valor);
return temp;
}
}

struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor) {
struct nodo_arbol *temp = NULL,*pivote = NULL;
//register int contador = 0;
bool entrar = true;
temp =arbol;
while(entrar  && temp != NULL) {
pivote = temp;
//contador++;
if(valor->v[0] == temp->valor->v[0] && valor->v[1] == temp->valor->v[1]){
entrar = false;
//printf("Encontrado despues de %i\n",contador);
}
else {
if(valor->v[0] == temp->valor->v[0]) {
if(valor->v[1] > temp->valor->v[1]) {
temp = temp->derecho;
}
else {
temp = temp->izquierdo;
}
}
else {
if(valor->v[0] > temp->valor->v[0]) {
temp = temp->derecho;
}
else {
temp = temp->izquierdo;
}
}
}
}
return temp;
}

//Crea un nodo de arbol, agregando el valor del nodo padre y el valor que guardara el nodo (Un apuntador a un  nodo ya existente en el grafo)
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,struct nodo_comparar *valor) {
struct nodo_arbol *n = malloc(sizeof(struct nodo));
if(n == NULL) {
printf("Error de Memoria\n");
exit(0);
}
n->padre = padre;
n->valor = valor;
n->derecho = NULL;
n->izquierdo = NULL;
return n;
}



El programa se auxilia de una Arreglo de apuntadores a Nodo, para tener una lista de todos los nodos del grafo.
Tambien usa un arbol binario para buscar si existen coindicencias previas de un mismo nodo.

Por falta de memoria en mi sistema no he terminado de ejecutarlo la ultima vez llego a mas de 18 Millones de Nodos y el sistema estaba bastante lento.

Saludos




Hola de nuevo he realizado otra versión del código anterior, el cual es el mismo grafo pero ahora en lugar de apuntadores en las aristas, esta versión contiene un indice entero que apunta a una posición dentro de la lista lista. Usa un poco menos de memoria que la version cuando se ejecuta en un sistema de 64 bits, ya que la primera versión los apuntadores son de 8 bytes y en esta versión el indice es de 4 bytes.

Código (c) [Seleccionar] Expandir

#include<stdint.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>

#define RESERVAR 1000000 //Reserva cada que agota el espacio para RESERVAR cantidad de apuntadores

//Nodo del grafo
struct nodo {
uint32_t id;
uint8_t tabla[4][4];
uint8_t x,y;
uint32_t aristas[4];
};

//Estructura auxiliar solo para realizar menos comparaciones en el Arbol
struct nodo_comparar {
uint32_t id;
uint64_t v[2];
uint8_t x,y;
uint32_t aristas[4];
};

//Nodo de un arbol, este solo contiene los apuntadores de un arbol binario y adiconal el valor
//El cual solo es un apuntador a un nodo ya existente del grafo
struct nodo_arbol {
struct nodo_arbol *padre,*izquierdo,*derecho;
uint32_t indice;
};

void imprimir_tablero(struct nodo *n);

struct nodo *crear_nodo(struct nodo *previo, char movimiento);

struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,uint32_t indice);
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,uint32_t indice);
int buscar_nodo_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor);

char *direccion[4] = {"arriba","abajo","izquierda","derecha"};
char dir_char[4] = "wsad";

struct nodo **lista = NULL; //Lista de todos los nodos existentes del grafo

int main() {
struct nodo_arbol *arbol = NULL; //Nodos de ARBOL
struct nodo *grafo = NULL,*aux1 = NULL,*aux2 = NULL,*pivote = NULL; // Nodos de el GRAFO y auxiliares
int busqueda; //Variable para la busqueda
register unsigned int indice = 0,aux_memoria = 0; //Almacenara el numero de nodos totales en la lista previa
register int i = 0,j =0,contador = 0;
//Inicializamos el grafo (Primer Nodo)

grafo = malloc(sizeof(struct nodo));
while(i < 4) {
j = 0;
while(j < 4) {
grafo->tabla[i][j] = contador+1;
j++;
contador++;
}
i++;
}
grafo->id = indice;
grafo->x = 3;
grafo->y = 3;
grafo->tabla[grafo->y][grafo->x] = 0;
//Fin de inicializacion de nodo inicial
if(indice == aux_memoria) {
aux_memoria += RESERVAR;
lista = realloc(lista,sizeof(struct nodo*)*(aux_memoria+1)); // Espacio para la lista
}
lista[indice] = grafo; //Guardamos el nodo del primier elemento del grafo en nuestra lista de nodos
arbol = agregar_valor_arbol(arbol,0); // Guardamos el nodo inicial como apuntador al arbol (NODO Raiz
indice++; //Incrementamos el indice en 1 ya que actualmente exitte al menos un indice en la lista
j = 0;
do {
pivote = lista[j];
//imprimir_tablero(pivote);
i = 0;
while(i < 4) {
aux1 = crear_nodo(pivote,dir_char[i]); //Creamos el nodo de la Arista Actual con el movimiento adecuado
if(aux1) {
/*
Si es valido tenemos que validar que la secuencia
generada no exista previamente
*/
busqueda = buscar_nodo_arbol(arbol,(struct nodo_comparar*)aux1); // Buscamos el nodo generado en el arbol, para validar que no exista la misma configuracion en el grafo actual
if(busqueda >= 0) { // Si el apuntador es valido entonces ya existe la secuencia de aux1 en el Grafo actual
free(aux1); //Liberamos la secuencia duplicada
pivote->aristas[i] = busqueda; //La arista actual apunta a la secuencia qua ya existia
}
else {
pivote->aristas[i] = indice; //La arista actual apunta a la nueva secuencia (Unica)
if(indice == aux_memoria) {
aux_memoria += aux_memoria;
lista = realloc(lista,sizeof(struct nodo*)*(aux_memoria+1)); // Ajustamos la memoria de la lista de nodos
}
lista[indice] = aux1; //agregamos el nuevo elemento a la lista
aux1->id = indice;
arbol = agregar_valor_arbol(arbol,indice);// Agregamos el nodo al arbol para posteriormente buscar
indice++; //Incrementamos el indice para la lista
}
}
else {
//El nodo no es valido por lo tanto, no hay nada que validar
pivote->aristas[i] = -1; //Guardamos NULL en la arista actual
}
i++; //Incrementamos el indice de las aristas
}
j++; //Incrementamos el indice de los nodos procesados dentro de la lista de Nodos
if(!(j % 10000)) { // Solo informamos del avance cada 10000 Nodos
printf("%i < %i\n",j,indice);
}
}while(j < indice); //Condicien para continuar procesando nodos
printf("%i < %i\n",j,indice); // Imprimimos contadores finales
j = 0;
while(lista[j] != NULL) {
free(lista[j]); // Liberamos memoria de los nodos del grafo
j++;
}
free(lista); // Liberamod memoria la lista
return 0;
}


//Crea un nuevo Nodo en base a un nodo previo y el movimiento usado en el juego
struct nodo *crear_nodo(struct nodo *previo, char movimiento) {
struct nodo *n = NULL;
n = malloc(sizeof(struct nodo));
if(n != NULL) {
memcpy(n->tabla,previo->tabla,sizeof(int) * 18);
/*
n->x = previo->x;
n->y = previo->y;
*/
switch(movimiento) {
case 'w': //arriba
if(n->y <= 2) {
//Movimiento de ficha
n->tabla[n->y][n->x] = n->tabla[n->y+1][n->x];
n->tabla[n->y+1][n->x] = 0;
n->y++;
}
else {
free(n);
n =NULL;
}
break;
case 's': //abajo
if(n->y >= 1) {
//Movimiento de ficha
n->tabla[n->y][n->x] = n->tabla[n->y-1][n->x];
n->tabla[n->y-1][n->x] = 0;
//imprimir_tablero();
n->y--;
}
else {
free(n);
n =NULL;
}
break;
case 'a': //izquierda
if(n->x <= 2) {
n->tabla[n->y][n->x] = n->tabla[n->y][n->x+1];
n->tabla[n->y][n->x+1] = 0;
n->x++;
}
else {
free(n);
n =NULL;
}
break;
case 'd': //derecha
if(n->x >= 1) {
n->tabla[n->y][n->x] = n->tabla[n->y][n->x-1];
n->tabla[n->y][n->x-1] = 0;
//imprimir_tablero();
n->x--;
}
else {
free(n);
n =NULL;
}
break;
}
}
else {
printf("Error de memoria!\nSaliendo\n");
exit(1);
}
return n;
}

//Imprime el estado actual de un Nodo
void imprimir_tablero(struct nodo *n) {
if(n != NULL) {
int i = 0,j;
printf("%p:\n",n);
while(i < 4) {
j = 0;
while(j < 4) {
if(n->tabla[i][j] != 0) {
printf("[%2i]",n->tabla[i][j]);
}
else {
printf("[  ]");
}
j++;
}
printf("\n");
i++;
}
}
else {
printf("Nodo no valido\n");
}
}

//Funcion que busca el lugar adecuado para el nodo en cuestion a agregar
//Usando busqueda binaria y comparando los valores de la tabla
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,uint32_t indice) {
struct nodo_arbol *temp,*pivote;
struct nodo_comparar *valor = (struct nodo_comparar *)lista[indice];
struct nodo_comparar *aux1  = NULL;
bool derecho = false;
if(arbol) {
temp = arbol;
while(temp != NULL) {
pivote = temp;
aux1 = (struct nodo_comparar *)lista[temp->indice];
if(valor->v[0] == aux1->v[0]) {
if(valor->v[1] > aux1->v[1]) {
temp = temp->derecho;
derecho = true;
}
else {
temp = temp->izquierdo;
derecho = false;
}
}
else {
if(valor->v[0] > aux1->v[0]) {
temp = temp->derecho;
derecho = true;
}
else {
temp = temp->izquierdo;
derecho = false;
}
}
}
temp = crear_nodo_arbol(pivote,indice);
if(derecho) {
//printf("Nodo %i creado en el lado derecho de %i\n",valor->id,lista[pivote->indice]->id);
pivote->derecho = temp;
}
else {
//printf("Nodo %i creado en el lado izquierdo de %i\n",valor->id,lista[pivote->indice]->id);
pivote->izquierdo = temp;
}
return arbol;
}
else {
temp = crear_nodo_arbol(NULL,indice);
return temp;
}
}

int buscar_nodo_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor) {
int r = -1;
struct nodo_arbol *temp = NULL,*pivote = NULL;
struct nodo_comparar *aux1 = NULL;
//register int contador = 0;
bool entrar = true;
temp = arbol;
while(entrar  && temp != NULL) {
pivote = temp;
aux1 = (struct nodo_comparar*)lista[temp->indice];
//contador++;
if(valor->v[0] == aux1->v[0] && valor->v[1] == aux1->v[1]){
r = aux1->id;
entrar = false;
//printf("Encontrado despues de %i\n",contador);
}
else {
if(valor->v[0] == aux1->v[0]) {
if(valor->v[1] > aux1->v[1]) {
temp = temp->derecho;
}
else {
temp = temp->izquierdo;
}
}
else {
if(valor->v[0] > aux1->v[0]) {
temp = temp->derecho;
}
else {
temp = temp->izquierdo;
}
}
}
}
return r;
}

//Crea un nodo de arbol, agregando el valor del nodo padre y el valor que guardara el nodo (Un apuntador a un  nodo ya existente en el grafo)
struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,uint32_t indice) {
struct nodo_arbol *n = malloc(sizeof(struct nodo));
if(n == NULL) {
printf("Error de Memoria\n");
exit(0);
}
n->padre = padre;
n->indice = indice;
n->derecho = NULL;
n->izquierdo = NULL;
return n;
}


Saludos!