Mini-Concurso de programacion 2. Las 8 reinas.

[jgpeiro06]

Bueno, aqui va el archivo main.c oficial y comienza el concurso.

Código: C

1. /**********************
2. Mini-Concurso de programacion
3.  
4. El concursante deme implementar:
5.         Estructuras Casilla y Tablero
6.         Funciones calculaNuevaPosicion, verificaPosicion y imprimeTablero.
7. Se puede añadir o eliminar cualquier cosa en estas estructuras o funciones.
8. ***********************/
9.  
10. #include        <stdlib.h>
11. #include        <stdio.h>
12. #include        <math.h>
13.  
14. enum Ficha { vacio, reina };
15.  
16. typedef struct {
17.         enum Ficha ficha1;
18. }Casilla;
19.  
20. typedef struct {
21.         Casilla casillas1[8][8];
22. }Tablero;
23.  
24. void calculaNuevaPosicion( const Tablero *ptablrero1 ){
25.         return;
26. }
27. int verificaPosicion( const Tablero *ptablrero1 ){
28.         return 0;
29. }
30. void imprimeTablero( const Tablero *ptablrero1 ){
31.         return;
32. }
33.  
34. int main(){
35.  
36.         Tablero tablero1;
37.         int i;
38.  
39.         printf("www.TODOPIC.com.ar\n");
40.         printf("Mini-Concurso de progracion en C, Parte 2:\n");
41.         printf("Las 8 reinas.\n");
42.         printf("Nombre del concursante: XXXX");
43.        
44.         long long tested = 0;
45.         for( i = 0 ; i < 92 ; i++ ){
46.                 while( !verificaPosicion( &tablero1 ) ){
47.                         tested++;
48.                         calculaNuevaPosicion( &tablero1 );
49.                 }
50.                 printf( "\nTableros comprobados: %f", (double)tested );
51.                 printf( "\nSolucion %d de 92: ", i );
52.                 imprimeTablero( &tablero1 );
53.         }
54.  
55.         printf("\n\nTest terminado.");
56.         return 0;
57. }

[Nocturno]

Dices que se pueden añadir o eliminar cualquier cosa en estructuras y funciones; entiendo que lo único que hay que respetar son los nombres de las mismas para que el main funcione, ¿no?

¿Eso significa que podemos montar otra estructura distinta de casillas y tablero?

[jgpeiro06]

Dices que se pueden añadir o eliminar cualquier cosa en estructuras y funciones...

Si, así cada concursante podrá trabajar más cómodo.

...entiendo que lo único que hay que respetar son los nombres de las mismas para que el main funcione, ¿no?

En principio si que hay que mantener los nombres, pero si alguien cree que puede obtener un código mejor modificando también el main...es libre de hacerlo. Siempre el mensaje impreso sea comprensible.

¿Eso significa que podemos montar otra estructura distinta de casillas y tablero?

Si, cada usuario puede definir las estructuras como mas le convenga, así habrá códigos mas variados...

[migsantiago]

¿Se vale usar C# en vez de C?

[jgpeiro06]

¿Se vale usar C# en vez de C?

No, el concurso es en C, y el programa se compilará con el MPLAB o el CCS.
Solo por curiosidad ¿ofrece alguna ventaja el C# para este problema?

[migsantiago]

Pues es que quería hacer una grafiquita que dibujara las reinas en el tablero. Pero bueno, lo intentaré con C normal.

[migsantiago]

Ya terminé mi algoritmo. Primero lo hice en C# para poderlo depurar a gusto.

Implementé un algoritmo por fuerza bruta, es decir, pasa por todas las posibles posiciones que pueden tener las reinas. Después de cada combinación se busca si hay al menos 2 reinas en la misma fila o en la misma diagonal usando la detección propuesta en el link de Wikipedia que Jgpeiro da.

Si la combinación es apropiada, imprime el tablero con ceros y unos, siendo los unos las reinas.

No conté las combinaciones correctas ya que al hacer un barrido de todas las combinaciones posibles tienen que salir las 92 correctas siempre.

El archivo resultante con los 92 tableros dibujados es este:
http://www.4shared.com/file/104418320/64e40fd2/Reinas.html

Pero como no se vale en C# migré el código a CCS usando un PIC16 que fácilmente puede migrarse a PIC24. El código compila correctamente sin errores ni advertencias, pero no lo puedo probar porque no uso MPLAB. Si alguien lo emula en MPLAB o Proteus por favor que me diga si funciona.

Este es el código de CCS:
http://www.4shared.com/file/104418325/148efb5d/Ocho_Reinas_CCS.html

Y para los interesados, el código en C#.
http://www.4shared.com/file/104418343/abb7f9ee/Ocho_Reinas_VC_2008.html

 

[jgpeiro06]

Ya terminé mi algoritmo.

Ok, lo he revisado y parece todo correcto. No es compatible con el "main.c", pero es igual. No lo he probado con el MPLAB, aunque seguro que funciona con algunas modificaciones mínimas.

Yo también he terminado el código. Lo cuelgo por si alguien lo quiere mirar o probar.
Tarda unos tres minutos en un PIC24 a 120MHz( >7200 millones de instrucciones ). Ocupa <300 instrucciones de ROM y 0 de RAM (+el stack) si no incluimos las funciones de printf.

Utiliza también un algoritmo por fuerza bruta.

[migsantiago]

Vientos Jgpeiro.

Una pregunta... ¿el tiempo de 3 minutos es al simularlo en tu pc o el tiempo que da el stopwatch de mplab?

Es que si corres el simulador de MPLAB en una pc lenta, el tiempo real crecerá. El stopwatch de MPLAB da el tiempo de forma exacta.

[jgpeiro06]

Vientos Jgpeiro.

¿que significa?

¿el tiempo de 3 minutos es al simularlo en tu pc o el tiempo que da el stopwatch de mplab?

Es el tiempo que aparece en el stopwatch, claro, y por eso especifico la velocidad del pic y las instrucciones ejecutadas en ese tiempo. Simularlo en el PC tarda bastante más, quizás 10 o 15 min...

[migsantiago]

Vientos Huracanados Arremolinados significa... buen trabajo... bien hecho 

A ver si me doy un tiempo para instalar MPLAB y CCS para medir el tiempo como tú lo haces.

[gera]

Fuerza bruta??
Si mis calculos no fallan esas son 64C8=4.426.165.368 posibilidades!! Yo tengo algo pensado para descartar todas las posibilidades donde las reinas se atacan por filas o columnas, pero creo q eso solo sigue siendo ineficiente. Lo ideal seria descartar tambien los ataques diagonales y ya estariamos, cada posibilidad seria una solucion.
Saludos!!

[migsantiago]

Por fuerza bruta son 8x8x8x8x8x8x8x8 combinaciones porque cada reina puede ocupar 8 posiciones en su columna.

Total 16,777,216 combinaciones.

[gera]

Ahh, trampa ahi!! jaja. Eso es fuerza no tan bruta jeje. Ahi estas descartando que las reinas se ataquen por columnas. Y si aplicas el metodo de permutar un arreglo para evitar q tambien se ataquen por filas? supongo q te ahorrarias muchos ciclos.
saludos!

[migsantiago]

Oye tienes razón 

Pero bueno, haría la actualización el fin de semana jeje