elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Recuerda que debes registrarte en el foro para poder participar (preguntar y responder)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  ¿Imposible? Juego de Rompecabezas imposible		0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: ¿Imposible? Juego de Rompecabezas imposible  (Leído 5,315 veces)
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.705


🏴 Libertad!!!!!


Ver Perfil WWW
¿Imposible? Juego de Rompecabezas imposible
« en: 21 Julio 2016, 16:57 pm »
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:
	[ 1][ 2][ 3][ 4]
	[ 5][ 6][ 7][ 8]
	[ 9][10][11][12]
	[13][14][15][  ]

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


Y si, es IMPOSIBLE

Código
  1. /*
  2. 	Juego del Imposible | Programación en C
  3.  
  4. 	[ 1][ 2][ 3][ 4]
  5. 	[ 5][ 6][ 7][ 8]
  6. 	[ 9][10][11][12]
  7. 	[13][14][15][  ]
  8.  
  9. 	 w
  10. 	asd
  11.  
  12. 	Contacto
  13. 	Twitter:	@albertobsd
  14. 	Email:		alberto.bsd@gmail.com		
  15. */
  16. #include<stdio.h>
  17.  
  18. void imprimir_tablero();
  19.  
  20. int tabla[4][4];
  21. int x= 3,y =3;
  22.  
  23. int main()	{
  24. 	int i = 0,j =0,contador = 1;
  25. 	char caracter,enter;
  26. 	//Inicializar la tabla o matriz de juego
  27. 	while(i < 4)	{
  28. 		j = 0;
  29. 		while(j < 4)	{
  30. 			tabla[i][j] = contador;
  31. 			//printf("[%2i]",tabla[i][j]);
  32. 			j++;
  33. 			contador++;
  34. 		}
  35. 		printf("\n");
  36. 		i++;
  37. 	}
  38. 	tabla[y][x] = 0;
  39. 	imprimir_tablero();
  40. 	do	{
  41. 		caracter = getchar();
  42. 		enter = getchar();
  43. 		switch(caracter)	{
  44. 			case 'w':	//arriba
  45. 				if(y <= 2)	{
  46. 					//Movimiento de ficha
  47. 					tabla[y][x] = tabla[y+1][x];
  48. 					tabla[y+1][x] = 0;
  49. 					imprimir_tablero();
  50. 					y++;
  51. 				}
  52. 				else	{
  53. 					printf("Fuera de los limites\n");
  54. 				}
  55. 			break;
  56. 			case 's':	//abajo
  57. 				if(y >= 1)	{
  58. 					//Movimiento de ficha
  59. 					tabla[y][x] = tabla[y-1][x];
  60. 					tabla[y-1][x] = 0;
  61. 					imprimir_tablero();
  62. 					y--;
  63. 				}
  64. 				else	{
  65. 					printf("Fuera de los limites\n");
  66. 				}
  67. 			break;
  68. 			case 'a':	//izquierda
  69. 				if(x <= 2)	{
  70. 					//Movimiento de ficha
  71. 					tabla[y][x] = tabla[y][x+1];
  72. 					tabla[y][x+1] = 0;
  73. 					imprimir_tablero();
  74. 					x++;
  75. 				}
  76. 				else	{
  77. 					printf("Fuera de los limites\n");
  78. 				}
  79.  
  80. 			break;
  81. 			case 'd':	//derecha
  82. 				if(x >= 1)	{
  83. 					tabla[y][x] = tabla[y][x-1];
  84. 					tabla[y][x-1] = 0;
  85. 					imprimir_tablero();
  86. 					x--;
  87. 				}
  88. 				else	{
  89. 					printf("Fuera de los limites\n");
  90. 				}
  91. 			break;
  92. 			case '0':	//Salida
  93. 			break;
  94. 			default:
  95. 				printf("Caracter Incorrecto");
  96. 			break;
  97. 		}
  98. 		printf("Caracter : %c\n",caracter);
  99. 	}while(caracter != '0');
  100. 	return 0;
  101. }
  102.  
  103. void imprimir_tablero()	{
  104. 	int i = 0,j;
  105. 	while(i < 4)	{
  106. 		j = 0;
  107. 		while(j < 4)	{
  108. 			if(tabla[i][j] != 0)	{
  109. 				printf("[%2i]",tabla[i][j]);
  110. 			}
  111. 			else	{
  112. 				printf("[  ]");
  113. 			}
  114. 			j++;
  115. 		}
  116. 		printf("\n");
  117. 		i++;
  118. 	}	
  119. }


Video:



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!
« Última modificación: 21 Julio 2016, 19:44 pm por AlbertoBSD » En línea
class_OpenGL


Desconectado Desconectado

Mensajes: 437

Si usas Direct3D, no eres mi amigo :P


Ver Perfil
Re: ¿Imposible? Juego de Rompecabezas imposible
« Respuesta #1 en: 21 Julio 2016, 18:00 pm »
No sé si será imposible o no, pero yo me quedé cerca XDD:



Por cierto, bien programado :D
« Última modificación: 21 Julio 2016, 18:03 pm por class_OpenGL » En línea
Programador aficionado. Me quiero centrar en programar videojuegos. La API que uso para crearlos es OpenGL
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.705


🏴 Libertad!!!!!


Ver Perfil WWW
Re: ¿Imposible? Juego de Rompecabezas imposible
« Respuesta #2 en: 21 Julio 2016, 20:28 pm »
Cita de: class_OpenGL en 21 Julio 2016, 18:00 pm
Por cierto, bien programado :D

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
« Última modificación: 24 Julio 2016, 00:14 am por AlbertoBSD » En línea
Sr Limone

Desconectado Desconectado

Mensajes: 5


Ver Perfil
Re: ¿Imposible? Juego de Rompecabezas imposible
« Respuesta #3 en: 21 Julio 2016, 22:59 pm »
Muy buen juego  :D ... Felicidades  ;-)
En línea
AlbertoBSD
Programador y
Moderador Global
***
Desconectado Desconectado

Mensajes: 3.705


🏴 Libertad!!!!!


Ver Perfil WWW
Re: ¿Imposible? Juego de Rompecabezas imposible
« Respuesta #4 en: 23 Julio 2016, 18:54 pm »
Gracias  :xD

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

Código
  1. struct nodo	{
  2. 	int tabla[4][4];
  3. 	int x,y;
  4. 	struct nodo *arriba;
  5. 	struct nodo *abajo;
  6. 	struct nodo *izquierda;
  7. 	struct nodo *derecha;
  8. 	bool visitado;
  9. };

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
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4.  
  5. struct nodo	{
  6. 	unsigned char tabla[4][4];
  7. 	unsigned char x,y;
  8. 	struct nodo *arriba;
  9. 	struct nodo *abajo;
  10. 	struct nodo *izquierda;
  11. 	struct nodo *derecha;
  12. };
  13.  
  14. void imprimir_tablero(struct nodo *n);
  15. struct nodo *crear_nodo(struct nodo *previo, char movimiento);
  16.  
  17. int main()	{
  18. 	struct nodo *grafo = NULL;
  19.  
  20. 	//Inicializamos el grafo (Primer Nodo)
  21. 	int i = 0,j =0,contador = 0;
  22. 	grafo = calloc(sizeof(struct nodo),1);
  23. 	while(i < 4)	{
  24. 		j = 0;
  25. 		while(j < 4)	{
  26. 			grafo->tabla[i][j] = contador+1;
  27. 			j++;
  28. 			contador++;
  29. 		}
  30. 		i++;
  31. 	}
  32. 	grafo->x = 3;
  33. 	grafo->y = 3;
  34. 	grafo->tabla[grafo->y][grafo->x] = 0;
  35.  
  36.  
  37. 	//Generamos los nodos vecinos:
  38. 	grafo->arriba = crear_nodo(grafo,'w');
  39. 	grafo->abajo = crear_nodo(grafo,'s');
  40. 	grafo->izquierda = crear_nodo(grafo,'a');
  41. 	grafo->derecha = crear_nodo(grafo,'d');
  42.  
  43. 	//Imprimimos el grafo y los primero 4 nodos vecinos
  44. 	imprimir_tablero(grafo);
  45. 	printf("Combinaciones:\n");
  46. 	printf("Arriba:\n");
  47. 	imprimir_tablero(grafo->arriba);
  48. 	printf("Abajo:\n");
  49. 	imprimir_tablero(grafo->abajo);
  50. 	printf("Izquierda:\n");
  51. 	imprimir_tablero(grafo->izquierda);
  52. 	printf("Derecha:\n");
  53. 	imprimir_tablero(grafo->derecha);
  54. 	return 0;
  55. }
  56.  
  57. struct nodo *crear_nodo(struct nodo *previo, char movimiento)	{
  58. 	struct nodo *n = NULL;
  59. 	n = calloc(sizeof(struct nodo),1);
  60. 	if(n != NULL)	{
  61. 		memcpy(n->tabla,previo->tabla,sizeof(int) * 16);
  62. 		n->x = previo->x;
  63. 		n->y = previo->y;
  64. 		switch(movimiento)	{
  65. 			case 'w':	//arriba
  66. 				if(n->y <= 2)	{
  67. 					//Movimiento de ficha
  68. 					n->tabla[n->y][n->x] = n->tabla[n->y+1][n->x];
  69. 					n->tabla[n->y+1][n->x] = 0;
  70. 					n->y++;
  71. 				}
  72. 				else	{
  73. 					free(n);
  74. 					n =NULL;
  75. 					//printf("Fuera de los limites\n");
  76. 				}
  77. 			break;
  78. 			case 's':	//abajo
  79. 				if(n->y >= 1)	{
  80. 					//Movimiento de ficha
  81. 					n->tabla[n->y][n->x] = n->tabla[n->y-1][n->x];
  82. 					n->tabla[n->y-1][n->x] = 0;
  83. 					//imprimir_tablero();
  84. 					n->y--;
  85. 				}
  86. 				else	{
  87. 					free(n);
  88. 					n =NULL;
  89. 					//printf("Fuera de los limites\n");
  90. 				}
  91. 			break;
  92. 			case 'a':	//izquierda
  93. 				if(n->x <= 2)	{
  94. 					//Movimiento de ficha
  95. 					n->tabla[n->y][n->x] = n->tabla[n->y][n->x+1];
  96. 					n->tabla[n->y][n->x+1] = 0;
  97. 					//imprimir_tablero();
  98. 					n->x++;
  99. 				}
  100. 				else	{
  101. 					free(n);
  102. 					n =NULL;
  103. 					//printf("Fuera de los limites\n");
  104. 				}
  105. 			break;
  106. 			case 'd':	//derecha
  107. 				if(n->x >= 1)	{
  108. 					n->tabla[n->y][n->x] = n->tabla[n->y][n->x-1];
  109. 					n->tabla[n->y][n->x-1] = 0;
  110. 					//imprimir_tablero();
  111. 					n->x--;
  112. 				}
  113. 				else	{
  114. 					free(n);
  115. 					n =NULL;
  116. 					//printf("Fuera de los limites\n");
  117. 				}
  118. 			break;
  119. 		}
  120. 	}
  121. 	else	{
  122. 		printf("Error de memoria!\nSaliendo\n");
  123. 		exit(1);
  124. 	}
  125. 	return n;
  126. }
  127.  
  128. void imprimir_tablero(struct nodo *n)	{
  129. 	if(n != NULL)	{
  130. 		int i = 0,j;
  131. 		while(i < 4)	{
  132. 			j = 0;
  133. 			while(j < 4)	{
  134. 				if(n->tabla[i][j] != 0)	{
  135. 					printf("[%2i]",n->tabla[i][j]);
  136. 				}
  137. 				else	{
  138. 					printf("[  ]");
  139. 				}
  140. 				j++;
  141. 			}
  142. 			printf("\n");
  143. 			i++;
  144. 		}
  145. 	}
  146. 	else	{
  147. 		printf("Nodo no valido\n");
  148. 	}
  149. }

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

Código
  1. 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:
[ 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
  1. #include<stdint.h>
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<string.h>
  5. #include<stdbool.h>
  6.  
  7. #define RESERVAR 1000000	//Reserva cada que agota el espacio para RESERVAR cantidad de apuntadores
  8.  
  9. //Nodo del grafo
  10. struct nodo	{
  11. 	uint32_t id;
  12. 	uint8_t tabla[4][4];
  13. 	uint8_t x,y;
  14. 	struct nodo *aristas[4];
  15. };
  16.  
  17. //Estructura auxiliar solo para realizar menos comparaciones en el Arbol
  18. struct nodo_comparar	{
  19. 	uint32_t id;
  20. 	uint64_t v[2];
  21. 	uint8_t x,y;
  22. 	struct nodo *aristas[4];
  23. };
  24.  
  25. //Nodo de un arbol, este solo contiene los apuntadores de un arbol binario y adiconal el valor 
  26. //El cual solo es un apuntador a un nodo ya existente del grafo
  27. struct nodo_arbol	{
  28. 	struct nodo_arbol *padre,*izquierdo,*derecho;
  29. 	struct nodo_comparar *valor;
  30. };
  31.  
  32. void imprimir_tablero(struct nodo *n);	
  33. struct nodo *crear_nodo(struct nodo *previo, char movimiento);
  34. struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,struct nodo_comparar *valor);
  35. struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor);
  36. struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor);
  37.  
  38. char *direccion[4] = {"arriba","abajo","izquierda","derecha"};
  39. char dir_char[4] = "wsad";
  40.  
  41. int main()	{
  42. 	struct nodo_arbol *arbol = NULL,*busqueda = NULL;	//Nodos de ARBOL y auxiliar de busqueda
  43. 	struct nodo *grafo = NULL,*aux1 = NULL,*aux2 = NULL,*pivote = NULL; // Nodos de el GRAFO y auxiliares
  44. 	struct nodo **lista = NULL;	//Lista de todos los nodos existentes del grafo
  45. 	register int indice = 0,aux_memoria = 0;	//Almacenara el numero de nodos totales en la lista previa
  46. 	register int i = 0,j =0,contador = 0;
  47. 	//Inicializamos el grafo (Primer Nodo)
  48.  
  49. 	grafo = malloc(sizeof(struct nodo));
  50. 	while(i < 4)	{
  51. 		j = 0;
  52. 		while(j < 4)	{
  53. 			grafo->tabla[i][j] = contador+1;
  54. 			j++;
  55. 			contador++;
  56. 		}
  57. 		i++;
  58. 	}
  59. 	grafo->x = 3;
  60. 	grafo->y = 3;
  61. 	grafo->tabla[grafo->y][grafo->x] = 0;
  62. 	//Fin de inicializacion de nodo inicial
  63. 	if(indice == aux_memoria)	{
  64. 		aux_memoria += RESERVAR;
  65. 		lista = realloc(lista,sizeof(struct nodo*)*(aux_memoria+1));	// Espacio para la lista 
  66. 	}
  67. 	arbol = agregar_valor_arbol(arbol,(struct nodo_comparar*)grafo);	// Guardamos el nodo inicial como apuntador al arbol (NODO Raiz)
  68. 	lista[indice] = grafo;	//Guardamos el nodo del primier elemento del grafo en nuestra lista de nodos
  69. 	indice++;	//Incrementamos el indice en 1 ya que actualmente exitte al menos un indice en la lista
  70. 	j = 0;
  71. 	do {
  72. 		pivote = lista[j];
  73. 		pivote->id = j;
  74. 		//imprimir_tablero(pivote);
  75. 		i = 0;
  76. 		while(i < 4)	{
  77. 			aux1 = crear_nodo(pivote,dir_char[i]);	//Creamos el nodo de la Arista Actual con el movimiento adecuado
  78. 			if(aux1)	{
  79. 				/*
  80. 					Si es valido tenemos que validar que la secuencia
  81. 					generada no exista previamente
  82. 				*/
  83. 				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
  84. 				if(busqueda !=  NULL)	{ // Si el apuntador es valido entonces ya existe la secuencia de aux1 en el Grafo actual
  85. 					free(aux1);	//Liberamos la secuencia duplicada
  86. 					pivote->aristas[i] = (struct nodo*)busqueda->valor;	//La arista actual apunta a la secuencia qua ya existia
  87. 				}
  88. 				else	{
  89. 					pivote->aristas[i] = aux1;	//La arista actual apunta a la nueva secuencia (Unica)
  90. 					if(indice == aux_memoria)	{
  91. 						aux_memoria += aux_memoria;
  92. 						lista = realloc(lista,sizeof(struct nodo*)*(aux_memoria+1));	// Ajustamos la memoria de la lista de nodos
  93. 					}
  94. 					lista[indice] = aux1;	//agregamos el nuevo elemento a la lista
  95. 					indice++;	//Incrementamos el indice para la lista
  96. 					arbol = agregar_valor_arbol(arbol,(struct nodo_comparar*)aux1);// Agregamos el nodo al arbol para posteriormente buscar
  97. 				}
  98. 			}
  99. 			else	{
  100. 				//El nodo no es valido por lo tanto, no hay nada que validar
  101. 				pivote->aristas[i] = aux1;	//Guardamos NULL en la arista actual
  102. 			}
  103. 			i++;	//Incrementamos el indice de las aristas
  104. 		}
  105. 		j++;	//Incrementamos el indice de los nodos procesados dentro de la lista de Nodos
  106. 		if(!(j % 10000))	{	// Solo informamos del avance cada 10000 Nodos
  107. 			printf("%i < %i\n",j,indice);
  108. 		}
  109. 	}while(j < indice);	//Condicien para continuar procesando nodos
  110. 	printf("%i < %i\n",j,indice);	// Imprimimos contadores finales
  111. 	j = 0;
  112. 	while(lista[j] != NULL)	{
  113. 		free(lista[j]);	// Liberamos memoria de los nodos del grafo
  114. 	}
  115. 	free(lista);	// Liberamod memoria la lista
  116. 	return 0;
  117. }
  118.  
  119.  
  120. //Crea un nuevo Nodo en base a un nodo previo y el movimiento usado en el juego
  121. struct nodo *crear_nodo(struct nodo *previo, char movimiento)	{
  122. 	struct nodo *n = NULL;
  123. 	n = malloc(sizeof(struct nodo));
  124. 	if(n != NULL)	{
  125. 		memcpy(n->tabla,previo->tabla,sizeof(int) * 18);
  126. 		/*
  127. 		n->x = previo->x;
  128. 		n->y = previo->y;
  129. 		*/
  130. 		switch(movimiento)	{
  131. 			case 'w':	//arriba
  132. 				if(n->y <= 2)	{
  133. 					//Movimiento de ficha
  134. 					n->tabla[n->y][n->x] = n->tabla[n->y+1][n->x];
  135. 					n->tabla[n->y+1][n->x] = 0;
  136. 					n->y++;
  137. 				}
  138. 				else	{
  139. 					free(n);
  140. 					n =NULL;
  141. 				}
  142. 			break;
  143. 			case 's':	//abajo
  144. 				if(n->y >= 1)	{
  145. 					//Movimiento de ficha
  146. 					n->tabla[n->y][n->x] = n->tabla[n->y-1][n->x];
  147. 					n->tabla[n->y-1][n->x] = 0;
  148. 					//imprimir_tablero();
  149. 					n->y--;
  150. 				}
  151. 				else	{
  152. 					free(n);
  153. 					n =NULL;
  154. 				}
  155. 			break;
  156. 			case 'a':	//izquierda
  157. 				if(n->x <= 2)	{
  158. 					n->tabla[n->y][n->x] = n->tabla[n->y][n->x+1];
  159. 					n->tabla[n->y][n->x+1] = 0;
  160. 					n->x++;
  161. 				}
  162. 				else	{
  163. 					free(n);
  164. 					n =NULL;
  165. 				}
  166. 			break;
  167. 			case 'd':	//derecha
  168. 				if(n->x >= 1)	{
  169. 					n->tabla[n->y][n->x] = n->tabla[n->y][n->x-1];
  170. 					n->tabla[n->y][n->x-1] = 0;
  171. 					//imprimir_tablero();
  172. 					n->x--;
  173. 				}
  174. 				else	{
  175. 					free(n);
  176. 					n =NULL;
  177. 				}
  178. 			break;
  179. 		}
  180. 	}
  181. 	else	{
  182. 		printf("Error de memoria!\nSaliendo\n");
  183. 		exit(1);
  184. 	}
  185. 	return n;
  186. }
  187.  
  188. //Imprime el estado actual de un Nodo 
  189. void imprimir_tablero(struct nodo *n)	{
  190. 	if(n != NULL)	{
  191. 		int i = 0,j;
  192. 		printf("%p:\n",n);
  193. 		while(i < 4)	{
  194. 			j = 0;
  195. 			while(j < 4)	{
  196. 				if(n->tabla[i][j] != 0)	{
  197. 					printf("[%2i]",n->tabla[i][j]);
  198. 				}
  199. 				else	{
  200. 					printf("[  ]");
  201. 				}
  202. 				j++;
  203. 			}
  204. 			printf("\n");
  205. 			i++;
  206. 		}
  207. 	}
  208. 	else	{
  209. 		printf("Nodo no valido\n");
  210. 	}
  211. }
  212.  
  213. //Funcion que busca el lugar adecuado para el nodo en cuestion a agregar
  214. //Usando busqueda binaria y comparando los valores de la tabla
  215. struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor)	{
  216. 	struct nodo_arbol *temp,*pivote;
  217. 	int derecho = false;
  218. 	if(arbol)	{
  219. 		temp = arbol;
  220. 		while(temp != NULL)	{
  221. 			pivote = temp;
  222. 			if(valor->v[0] == temp->valor->v[0])	{
  223. 				if(valor->v[1] > temp->valor->v[1])	{
  224. 					temp = temp->derecho;
  225. 					derecho = true;
  226. 				}
  227. 				else	{
  228. 					temp = temp->izquierdo;
  229. 					derecho = false;
  230. 				}
  231. 			}
  232. 			else	{
  233. 				if(valor->v[0] > temp->valor->v[0])	{
  234. 					temp = temp->derecho;
  235. 					derecho = true;
  236. 				}
  237. 				else	{
  238. 					temp = temp->izquierdo;
  239. 					derecho = false;
  240. 				}
  241. 			}
  242. 		}
  243. 		temp = crear_nodo_arbol(pivote,valor);
  244. 		if(derecho)	{
  245. 			pivote->derecho = temp;
  246. 		}
  247. 		else	{
  248. 			pivote->izquierdo = temp;
  249. 		}
  250. 		return arbol;
  251. 	}
  252. 	else	{
  253. 		temp = crear_nodo_arbol(NULL,valor);
  254. 		return temp;
  255. 	}
  256. }
  257.  
  258. struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor)	{
  259. 	struct nodo_arbol *temp = NULL,*pivote = NULL;
  260. 	//register int contador = 0;
  261. 	bool entrar = true;
  262. 	temp =arbol;
  263. 	while(entrar  && temp != NULL)	{
  264. 		pivote = temp;
  265. 		//contador++;
  266. 		if(valor->v[0] == temp->valor->v[0] && valor->v[1] == temp->valor->v[1]){
  267. 			entrar = false;
  268. 			//printf("Encontrado despues de %i\n",contador);
  269. 		}
  270. 		else	{
  271. 			if(valor->v[0] == temp->valor->v[0])	{
  272. 				if(valor->v[1] > temp->valor->v[1])	{
  273. 					temp = temp->derecho;
  274. 				}
  275. 				else	{
  276. 					temp = temp->izquierdo;
  277. 				}
  278. 			}
  279. 			else	{
  280. 				if(valor->v[0] > temp->valor->v[0])	{
  281. 					temp = temp->derecho;
  282. 				}
  283. 				else	{
  284. 					temp = temp->izquierdo;
  285. 				}
  286. 			}
  287. 		}
  288. 	}
  289. 	return temp;
  290. }
  291.  
  292. //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)
  293. struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,struct nodo_comparar *valor)	{
  294. 	struct nodo_arbol *n = malloc(sizeof(struct nodo));
  295. 	if(n == NULL)	{
  296. 		printf("Error de Memoria\n");
  297. 		exit(0);
  298. 	}
  299. 	n->padre = padre;
  300. 	n->valor = valor;
  301. 	n->derecho = NULL;
  302. 	n->izquierdo = NULL;
  303. 	return n;
  304. }
  305.  


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
  1. #include<stdint.h>
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<string.h>
  5. #include<stdbool.h>
  6.  
  7. #define RESERVAR 1000000	//Reserva cada que agota el espacio para RESERVAR cantidad de apuntadores
  8.  
  9. //Nodo del grafo
  10. struct nodo	{
  11. 	uint32_t id;
  12. 	uint8_t tabla[4][4];
  13. 	uint8_t x,y;
  14. 	uint32_t aristas[4];
  15. };
  16.  
  17. //Estructura auxiliar solo para realizar menos comparaciones en el Arbol
  18. struct nodo_comparar	{
  19. 	uint32_t id;
  20. 	uint64_t v[2];
  21. 	uint8_t x,y;
  22. 	uint32_t aristas[4];
  23. };
  24.  
  25. //Nodo de un arbol, este solo contiene los apuntadores de un arbol binario y adiconal el valor 
  26. //El cual solo es un apuntador a un nodo ya existente del grafo
  27. struct nodo_arbol	{
  28. 	struct nodo_arbol *padre,*izquierdo,*derecho;
  29. 	uint32_t indice;
  30. };
  31.  
  32. void imprimir_tablero(struct nodo *n);	
  33.  
  34. struct nodo *crear_nodo(struct nodo *previo, char movimiento);
  35.  
  36. struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,uint32_t indice);
  37. struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,uint32_t indice);
  38. int buscar_nodo_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor);
  39.  
  40. char *direccion[4] = {"arriba","abajo","izquierda","derecha"};
  41. char dir_char[4] = "wsad";
  42.  
  43. struct nodo **lista = NULL;	//Lista de todos los nodos existentes del grafo
  44.  
  45. int main()	{
  46. 	struct nodo_arbol *arbol = NULL;	//Nodos de ARBOL		
  47. 	struct nodo *grafo = NULL,*aux1 = NULL,*aux2 = NULL,*pivote = NULL; // Nodos de el GRAFO y auxiliares
  48. 	int busqueda;	//Variable para la busqueda
  49. 	register unsigned int indice = 0,aux_memoria = 0;	//Almacenara el numero de nodos totales en la lista previa
  50. 	register int i = 0,j =0,contador = 0;
  51. 	//Inicializamos el grafo (Primer Nodo)
  52.  
  53. 	grafo = malloc(sizeof(struct nodo));
  54. 	while(i < 4)	{
  55. 		j = 0;
  56. 		while(j < 4)	{
  57. 			grafo->tabla[i][j] = contador+1;
  58. 			j++;
  59. 			contador++;
  60. 		}
  61. 		i++;
  62. 	}
  63. 	grafo->id = indice;
  64. 	grafo->x = 3;
  65. 	grafo->y = 3;
  66. 	grafo->tabla[grafo->y][grafo->x] = 0;
  67. 	//Fin de inicializacion de nodo inicial
  68. 	if(indice == aux_memoria)	{
  69. 		aux_memoria += RESERVAR;
  70. 		lista = realloc(lista,sizeof(struct nodo*)*(aux_memoria+1));	// Espacio para la lista 
  71. 	}
  72. 	lista[indice] = grafo;	//Guardamos el nodo del primier elemento del grafo en nuestra lista de nodos
  73. 	arbol = agregar_valor_arbol(arbol,0);	// Guardamos el nodo inicial como apuntador al arbol (NODO Raiz
  74. 	indice++;	//Incrementamos el indice en 1 ya que actualmente exitte al menos un indice en la lista
  75. 	j = 0;
  76. 	do {
  77. 		pivote = lista[j];
  78. 		//imprimir_tablero(pivote);
  79. 		i = 0;
  80. 		while(i < 4)	{
  81. 			aux1 = crear_nodo(pivote,dir_char[i]);	//Creamos el nodo de la Arista Actual con el movimiento adecuado
  82. 			if(aux1)	{
  83. 				/*
  84. 					Si es valido tenemos que validar que la secuencia
  85. 					generada no exista previamente
  86. 				*/
  87. 				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
  88. 				if(busqueda >= 0)	{ // Si el apuntador es valido entonces ya existe la secuencia de aux1 en el Grafo actual
  89. 					free(aux1);	//Liberamos la secuencia duplicada
  90. 					pivote->aristas[i] = busqueda;	//La arista actual apunta a la secuencia qua ya existia
  91. 				}
  92. 				else	{
  93. 					pivote->aristas[i] = indice;	//La arista actual apunta a la nueva secuencia (Unica)
  94. 					if(indice == aux_memoria)	{
  95. 						aux_memoria += aux_memoria;
  96. 						lista = realloc(lista,sizeof(struct nodo*)*(aux_memoria+1));	// Ajustamos la memoria de la lista de nodos
  97. 					}
  98. 					lista[indice] = aux1;	//agregamos el nuevo elemento a la lista
  99. 					aux1->id = indice;
  100. 					arbol = agregar_valor_arbol(arbol,indice);// Agregamos el nodo al arbol para posteriormente buscar
  101. 					indice++;	//Incrementamos el indice para la lista
  102. 				}
  103. 			}
  104. 			else	{
  105. 				//El nodo no es valido por lo tanto, no hay nada que validar
  106. 				pivote->aristas[i] = -1;	//Guardamos NULL en la arista actual
  107. 			}
  108. 			i++;	//Incrementamos el indice de las aristas
  109. 		}
  110. 		j++;	//Incrementamos el indice de los nodos procesados dentro de la lista de Nodos
  111. 		if(!(j % 10000))	{	// Solo informamos del avance cada 10000 Nodos
  112. 			printf("%i < %i\n",j,indice);
  113. 		}
  114. 	}while(j < indice);	//Condicien para continuar procesando nodos
  115. 	printf("%i < %i\n",j,indice);	// Imprimimos contadores finales
  116. 	j = 0;
  117. 	while(lista[j] != NULL)	{
  118. 		free(lista[j]);	// Liberamos memoria de los nodos del grafo
  119. 		j++;
  120. 	}
  121. 	free(lista);	// Liberamod memoria la lista
  122. 	return 0;
  123. }
  124.  
  125.  
  126. //Crea un nuevo Nodo en base a un nodo previo y el movimiento usado en el juego
  127. struct nodo *crear_nodo(struct nodo *previo, char movimiento)	{
  128. 	struct nodo *n = NULL;
  129. 	n = malloc(sizeof(struct nodo));
  130. 	if(n != NULL)	{
  131. 		memcpy(n->tabla,previo->tabla,sizeof(int) * 18);
  132. 		/*
  133. 		n->x = previo->x;
  134. 		n->y = previo->y;
  135. 		*/
  136. 		switch(movimiento)	{
  137. 			case 'w':	//arriba
  138. 				if(n->y <= 2)	{
  139. 					//Movimiento de ficha
  140. 					n->tabla[n->y][n->x] = n->tabla[n->y+1][n->x];
  141. 					n->tabla[n->y+1][n->x] = 0;
  142. 					n->y++;
  143. 				}
  144. 				else	{
  145. 					free(n);
  146. 					n =NULL;
  147. 				}
  148. 			break;
  149. 			case 's':	//abajo
  150. 				if(n->y >= 1)	{
  151. 					//Movimiento de ficha
  152. 					n->tabla[n->y][n->x] = n->tabla[n->y-1][n->x];
  153. 					n->tabla[n->y-1][n->x] = 0;
  154. 					//imprimir_tablero();
  155. 					n->y--;
  156. 				}
  157. 				else	{
  158. 					free(n);
  159. 					n =NULL;
  160. 				}
  161. 			break;
  162. 			case 'a':	//izquierda
  163. 				if(n->x <= 2)	{
  164. 					n->tabla[n->y][n->x] = n->tabla[n->y][n->x+1];
  165. 					n->tabla[n->y][n->x+1] = 0;
  166. 					n->x++;
  167. 				}
  168. 				else	{
  169. 					free(n);
  170. 					n =NULL;
  171. 				}
  172. 			break;
  173. 			case 'd':	//derecha
  174. 				if(n->x >= 1)	{
  175. 					n->tabla[n->y][n->x] = n->tabla[n->y][n->x-1];
  176. 					n->tabla[n->y][n->x-1] = 0;
  177. 					//imprimir_tablero();
  178. 					n->x--;
  179. 				}
  180. 				else	{
  181. 					free(n);
  182. 					n =NULL;
  183. 				}
  184. 			break;
  185. 		}
  186. 	}
  187. 	else	{
  188. 		printf("Error de memoria!\nSaliendo\n");
  189. 		exit(1);
  190. 	}
  191. 	return n;
  192. }
  193.  
  194. //Imprime el estado actual de un Nodo 
  195. void imprimir_tablero(struct nodo *n)	{
  196. 	if(n != NULL)	{
  197. 		int i = 0,j;
  198. 		printf("%p:\n",n);
  199. 		while(i < 4)	{
  200. 			j = 0;
  201. 			while(j < 4)	{
  202. 				if(n->tabla[i][j] != 0)	{
  203. 					printf("[%2i]",n->tabla[i][j]);
  204. 				}
  205. 				else	{
  206. 					printf("[  ]");
  207. 				}
  208. 				j++;
  209. 			}
  210. 			printf("\n");
  211. 			i++;
  212. 		}
  213. 	}
  214. 	else	{
  215. 		printf("Nodo no valido\n");
  216. 	}
  217. }
  218.  
  219. //Funcion que busca el lugar adecuado para el nodo en cuestion a agregar
  220. //Usando busqueda binaria y comparando los valores de la tabla
  221. struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,uint32_t indice)	{
  222. 	struct nodo_arbol *temp,*pivote;
  223. 	struct nodo_comparar *valor = (struct nodo_comparar *)lista[indice];
  224. 	struct nodo_comparar *aux1  = NULL;
  225. 	bool derecho = false;
  226. 	if(arbol)	{
  227. 		temp = arbol;
  228. 		while(temp != NULL)	{
  229. 			pivote = temp;
  230. 			aux1 = (struct nodo_comparar *)lista[temp->indice];
  231. 			if(valor->v[0] == aux1->v[0])	{
  232. 				if(valor->v[1] > aux1->v[1])	{
  233. 					temp = temp->derecho;
  234. 					derecho = true;
  235. 				}
  236. 				else	{
  237. 					temp = temp->izquierdo;
  238. 					derecho = false;
  239. 				}
  240. 			}
  241. 			else	{
  242. 				if(valor->v[0] > aux1->v[0])	{
  243. 					temp = temp->derecho;
  244. 					derecho = true;
  245. 				}
  246. 				else	{
  247. 					temp = temp->izquierdo;
  248. 					derecho = false;
  249. 				}
  250. 			}
  251. 		}
  252. 		temp = crear_nodo_arbol(pivote,indice);
  253. 		if(derecho)	{
  254. 			//printf("Nodo %i creado en el lado derecho de %i\n",valor->id,lista[pivote->indice]->id);
  255. 			pivote->derecho = temp;
  256. 		}
  257. 		else	{
  258. 			//printf("Nodo %i creado en el lado izquierdo de %i\n",valor->id,lista[pivote->indice]->id);
  259. 			pivote->izquierdo = temp;
  260. 		}
  261. 		return arbol;
  262. 	}
  263. 	else	{
  264. 		temp = crear_nodo_arbol(NULL,indice);
  265. 		return temp;
  266. 	}
  267. }
  268.  
  269. int buscar_nodo_arbol(struct nodo_arbol *arbol,struct nodo_comparar *valor)	{
  270. 	int r = -1;
  271. 	struct nodo_arbol *temp = NULL,*pivote = NULL;
  272. 	struct nodo_comparar *aux1 = NULL;
  273. 	//register int contador = 0;
  274. 	bool entrar = true;
  275. 	temp = arbol;
  276. 	while(entrar  && temp != NULL)	{
  277. 		pivote = temp;
  278. 		aux1 = (struct nodo_comparar*)lista[temp->indice];
  279. 		//contador++;
  280. 		if(valor->v[0] == aux1->v[0] && valor->v[1] == aux1->v[1]){
  281. 			r = aux1->id;
  282. 			entrar = false;
  283. 			//printf("Encontrado despues de %i\n",contador);
  284. 		}
  285. 		else	{
  286. 			if(valor->v[0] == aux1->v[0])	{
  287. 				if(valor->v[1] > aux1->v[1])	{
  288. 					temp = temp->derecho;
  289. 				}
  290. 				else	{
  291. 					temp = temp->izquierdo;
  292. 				}
  293. 			}
  294. 			else	{
  295. 				if(valor->v[0] > aux1->v[0])	{
  296. 					temp = temp->derecho;
  297. 				}
  298. 				else	{
  299. 					temp = temp->izquierdo;
  300. 				}
  301. 			}
  302. 		}
  303. 	}
  304. 	return r;
  305. }
  306.  
  307. //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)
  308. struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,uint32_t indice)	{
  309. 	struct nodo_arbol *n = malloc(sizeof(struct nodo));
  310. 	if(n == NULL)	{
  311. 		printf("Error de Memoria\n");
  312. 		exit(0);
  313. 	}
  314. 	n->padre = padre;
  315. 	n->indice = indice;
  316. 	n->derecho = NULL;
  317. 	n->izquierdo = NULL;
  318. 	return n;
  319. }
  320.  

Saludos!
« Última modificación: 24 Julio 2016, 00:14 am por AlbertoBSD » En línea
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
mas de 700mb imposible
Software 		Folstag 1 1,662 Último mensaje 14 Enero 2004, 15:56 pm
por 4rm4ndo
Imposible
Ingeniería Inversa 		josusa 2 2,161 Último mensaje 8 Febrero 2005, 17:42 pm
por josusa
Mision imposible ... y no el juego ... sino encontrar otro
Juegos y Consolas 		Novlucker 0 2,021 Último mensaje 8 Julio 2009, 18:25 pm
por Novlucker
rompecabezas imposible
Programación C/C++ 		rached1 2 2,211 Último mensaje 26 Enero 2018, 15:52 pm
por Serapis
Enserio es imposible hallar punteros a un juego creado con Java
Ingeniería Inversa 		Pirolox 1 3,113 Último mensaje 12 Marzo 2022, 01:52 am
por BloodSharp
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines