Mini-Concurso de programacion 2. Las 8 reinas.

[jgpeiro06]

Mini-Concurso de programacion en C, parte 2: Las 8 reinas.
El concurso empezará el 5 de Mayo y terminará el 20. Hasta el 5 se irán modelando las reglas, condiciones y premios del concurso según vuestros comentarios.


De momento el concurso esta planteado así:

El problema de las 8 reinas consiste en situar 8 reinas en un tablero de ajedrez sin que ninguna se toque entre si.
Cada participante debe implementar un algoritmo que encuentre las 92 soluciones posibles.

Ejemplo de una solucion valida.
+---+---+---+---+---+---+---+---+
|     |     |     |  X |    |     |     |     |
+---+---+---+---+---+---+---+---+
|     |     |     |     |    | X  |     |     |
+---+---+---+---+---+---+---+---+
|     |     |     |     |    |     |     | X  |
+---+---+---+---+---+---+---+---+
|     | X  |     |     |     |     |    |     |
+---+---+---+---+---+---+---+---+
|     |     |     |     |    |     |  X |     |
+---+---+---+---+---+---+---+---+
| X  |     |     |     |     |    |     |     |
+---+---+---+---+---+---+---+---+
|     |     | X  |     |     |    |     |     |
+---+---+---+---+---+---+---+---+
|     |     |     |     | X |     |     |     |
+---+---+---+---+---+---+---+---+

Se dará una función main.c con la estructura básica para que todos podamos probar los programas cómodamente.

Las categorias son las siguientes:
Algoritmo más rápido:
   Gana el algoritmo que encuentre las 92 soluciones en el menor tiempo( menor numero de instrucciones ejecutadas ).
   Requisitos:
   C30: PIC24. Compilador MPLAB C30, sin optimizaciones. No esta permitido el ensamblador incrustado.
   CCS: PIC24. Compilador CCS. ""
   
Algoritmo más sencillo
   Gana el que implemente el algoritmo más simple, más comprensible, mejor organizado...

Algoritmo más lioso
   Gana el más absurdo, el más loco, el que realiza calculos complicando lo más posible sin necesidad...
   No esta permitido añadir código "inútil", todo el código debe ser util para el algoritmo, pero si es posible implementar nuestras propias funciones para
   punto flotante o declarar todas las variables dinamicamente, utilizar switch en lugar de if, utilizar goto...todo aquello que nunca deberíamos hacer.

Algoritmo mas robusto
   Despues de compilar el programa se remmplazan unas cuantas instrucciones, escogidas al azar, por NOPs y se ejecuta el programa para ver que pasa.
   El algoritmo debe estar preparado para poder sobrevivir a estas u otras posibles "putadas"...

Cada concursante tendrá que votar los programas de los demás en las tres ultimas categorías.

El concurso finalizara el 20 de Mayo.
Sobre los premios...son solo algo simbólico para darle gracia al concurso:
   Algoritmo más lioso:
      2º Premio   Pagina web con muchos proyectos interesantes de electrónica. Link
      1º Premio   Librería para trabajar con matrices en C30. Archivo matrices.c
   Algoritmo más sencillo:
      2º Premio   Documental sobre ciencia y tecnología. VideoLink
      1º Premio   Pagina web con animaciones interactivas en flash. Link
   Algoritmo más rapido:
      2º Premio   Foto de el interior de un procesador Pentium 4 (4000x4000 pixels). Link
      1º Premio   Pack de 16 libros de programacion para sistemas empotrados. Link en rapidshare.
   Algoritmo más robusto:
      2º Premio   Entrevista a Bill Gates mostrando el nuevo Windows Paradise. VideoLink en youtube
      1º Premio   Versión moderna del juego The Increible Machine. Link en rapidshare.


El día 5 se colgaran las reglas oficiales y el archivo main.c con el esqueleto del programa.

Bueno, esto es lo que se me ocurre. Hasta el 5 de Mayo hay tiempo añadir o modificar cualquier cosa.
Quien este interesado en participar que se apunte añadiendo un post al hilo.

[gera]

Excelente iniciativa!!! Lamentablemente yo voy a estar preparando finales durante ese periodo, pero voy a hacer todo lo posible para generar un algoritmo.
Por cierto... nunca trabaje con pic24, habra alguna posibilidad de hacer el algoritmo en gcc y despues tratar de portarlo?
saludos!!!

[BrunoF]

A mi ya se me ocurrió el algoritmo pa resolverlo, pero esta vez voy a abstenerme. Al menos esperaré hasta que vengan otros primero.

[gera]

podriamos mandar las soluciones por privado, y asi evitar el robo de ideas

[migsantiago]

podriamos mandar las soluciones por privado, y asi evitar el robo de ideas

Sí es buena idea. Que al final Jgpeiro publique una lista de lo recibido.

[Nocturno]

Entiendo que el algoritmo no recibirá ninguna entrada y devolverá la salida mediante printf() a la salida por defecto, ¿verdad?.

Quizás estaría bien preparar un pequeño esqueleto en Proteus para poder ejecutar las soluciones sin necesidad de montar el circuito en real.

Me encantan estos concursos.

[jgpeiro06]

nunca trabaje con pic24, habra alguna posibilidad de hacer el algoritmo en gcc y despues tratar de portarlo

Lo normal es que el código sea independiente de la plataforma y del compilador. Si usas las librerías más comunes de C seguro que el código no necesita ninguna modificación para compilarlo con C30 o CCS.

podriamos mandar las soluciones por privado, y asi evitar el robo de ideas

No me parece mala idea. La idea era que cada usuario valorase los códigos de los demás usuarios, pero es cierto que seria muy difícil no dejarse influenciar. Se podrían enviar por privado los códigos, indicar en el hilo la versión que cada uno va enviando, si el código es para alguna categoría en concreto... y el dia 20 publico todos los codigos, durante una semana la gente que quiera los prueba, los vota(también por privado) y el día 25 se publican los ganadores.

Entiendo que el algoritmo no recibirá ninguna entrada y devolverá la salida mediante printf() a la salida por defecto, ¿verdad?.

Sip. Aun no tengo preparado el main.c con las funciones básicas para el concurso, pero supongo que con usar el printf sera suficiente.

Quizás estaría bien preparar un pequeño esqueleto en Proteus para poder ejecutar las soluciones sin necesidad de montar el circuito en real.

Las soluciones, como en el mini-concurso anterior, se pueden probar en el MPLAB. Con el MPLAB SIM como debugger la opción de UARTIO habilitada. De esta manera aparece una pestaña en la ventana Output que se llama "Sim Uart1" que permite visualizar lo que imprime un printf.
Con el IDE de CCS no se si esto se puede hacer, pero supongo que también habrá alguna manera de visualizar una consola.

[migsantiago]

Una pregunta, ¿la posición de la foto de abajo es válida? ¿No, verdad?

[Nocturno]

En ajedrez, las reinas comen tanto en horizontal, como en vertical, como en las dos diagonales, así que no es válida.

[jgpeiro06]

Una pregunta, ¿la posición de la foto de abajo es válida? ¿No, verdad?

Nop, no lo es.

Mírate el articulo sobre el problema de las 8 reinas en la wikipedia. Encontraras toda esta información:

Problema de las ocho reinas
    1 Planteamiento del Problema
        1.1 Establecimiento del Algoritmo
        1.2 Descripción del Algoritmo
    2 El problema de las n Reinas
    3 Soluciones al Problema de las Ocho Reinas
    4 Referencias
    5 Enlaces externos
        5.1 Enlaces a Soluciones

http://es.wikipedia.org/wiki/Problema_de_las_ocho_reinas

[jgpeiro06]

Ejemplo del archivo main.c. Solo es una prueba, aun no compila, pero sirve para dar una idea.
El concursante deberá implementar las funciones:
void calculaNuevaPosicion( const Tablero *ptablrero1 );
int verificaPosicion( const Tablero *ptablrero1 );

Código: C

1. /**********************
2. Mini-Concurso de programacion
3. ***********************/
4.  
5. #include        <stdlib.h>
6. #include        <stdio.h>
7. #include        <math.h>
8.  
9. enum ficha { vacia, reina };
10.  
11. casilla{
12.         enum ficha ficha1;
13. };
14.  
15. tablero{
16.         casillas1[8][8];
17. };
18.  
19. void calculaNuevaPosicion( const Tablero *ptablrero1 );
20. int verificaPosicion( const Tablero *ptablrero1 );
21.  
22. void imprimeTablero( const Tablero *ptablrero1 ){
23.         printf("\n\n");
24.         for( i = 0 ; i < 8 ; i++ ){
25.                 for( j = 0 ; j < 8 ; j++ ){
26.                         if( ptablero1->casillas1[i][j].ficha1 == reina )
27.                                 printf("Q");    // Pinta una reina.
28.                         else if((j&1)^(i&1))
29.                                 printf("#");    // Pinta casilla negra.
30.                         else
31.                                 printf(" ");    // Pinta casilla blanca.
32.                 }
33.                 printf("\n");
34.         }
35. }
36.  
37. int main(){
38.  
39.         Tablero tablero1;
40.         int i, j;
41.  
42.         printf("www.TODOPIC.com.ar\n");
43.         printf("Mini-Concurso de progracion en C, Parte 2:\n");
44.         printf("Las 8 reinas.\n");
45.         printf("Nombre del concursante: XXXX");
46.        
47.         long long tested = 0;
48.         for( i = 0 ; i < 92 ; i++ ){
49.                 while( !verificaPosicion( &tablero1 ) );
50.                         tested++;
51.                         calculaNuevaPosicion( &tablrero1 );
52.                 }
53.                 printf( "\nSe han escaneado %d tableros. Solucion %d de 92: ", tested, i );
54.                 imprimeTablero( &tablero1 );
55.         }
56.  
57.         printf("\n\nTest terminado.");
58.         return 0;
59. }

[jgpeiro06]

Bueno, quedan 2 días y aun somos muy pocos para el concurso...si no se apunta nadie más no tiene sentido seguir con el concurso...
Si nadie tiene ningún comentario sobre las reglas del concurso quedaran así.

Saludos

[migsantiago]

¿El archivo main.c ya es definitivo?

No importa si son pocos los interesados. Estoy seguro que más gente está participando con solo leer el tema.

[gera]

Yo estoy hasta las manos con la facultad, pero voy a tratar de aportar mi algoritmo
por cierto, no seria mas facil definir un arreglo 8x8 cuyo contenido sea 0 ó 1 dependiendo si hay reina o no? (es mas, seria mas eficiente con un arreglo de 8x1 jeje, pero seria incomodo).
saludos!!

[jgpeiro06]

¿El archivo main.c ya es definitivo?

Aun no, el original lo publicaré el día 5. Sera lo mismo, pero con las modificaciones que hagan los concursantes.

no seria mas facil definir un arreglo 8x8 cuyo contenido sea 0 ó 1 dependiendo si hay reina o no

Supongo que si que seria mas sencillo. Creo que seria conveniente que cada usuario pueda definir las estructuras tablero y casilla a su gusto.