#include <18F4520.h>
#device adc=8

#FUSES NOWDT                    //No Watch Dog Timer
#FUSES WDT128                   //Watch Dog Timer uses 1:128 Postscale
#FUSES HS                       //High speed Osc (> 4mhz)
#FUSES NOPROTECT                //Code not protected from reading
#FUSES BROWNOUT                 //Reset when brownout detected
#FUSES BORV25                   //Brownout reset at 2.5V
#FUSES PUT                      //Power Up Timer
#FUSES NOCPD                    //No EE protection
#FUSES NOSTVREN                 //Stack full/underflow will not cause reset
#FUSES NODEBUG                  //No Debug mode for ICD
#FUSES NOLVP                    //No low voltage prgming, B3(PIC16) or B5(PIC18) used for I/O
#FUSES NOWRT                    //Program memory not write protected
#FUSES NOWRTD                   //Data EEPROM not write protected
#FUSES NOIESO                   //Internal External Switch Over mode disabled
#FUSES NOFCMEN                  //Fail-safe clock monitor disabled
#FUSES PBADEN                   //PORTB pins are configured as analog input channels on RESET
#FUSES NOWRTC                   //configuration not registers write protected
#FUSES NOWRTB                   //Boot block not write protected
#FUSES NOEBTR                   //Memory not protected from table reads
#FUSES NOEBTRB                  //Boot block not protected from table reads
#FUSES NOCPB                    //No Boot Block code protection
#FUSES LPT1OSC                  //Timer1 configured for low-power operation
#FUSES MCLR                     //Master Clear pin enabled
#FUSES NOXINST                    //Extended set extension and Indexed Addressing mode enabled

#use delay(clock=20000000)
#use rs232(baud=9600,parity=N,xmit=PIN_C6,rcv=PIN_C7,bits=8)


// Define el numero de reinas en juego (tamaño tablero)
#define NUM_REINAS 8

/**
   Genera el siguiente nivel del árbol de soluciones.
   Generar un nivel consiste basicamente en colocar una reina en una nueva 
   columna.
 */
void generarNivel (signed int *tablero, signed int nivel) {
   tablero[nivel] = tablero[nivel] + 1;
}

/**
   Comprueba si la posición donde estamos intentando colocar la reina es valida
   o no.
   Una posición será valida si, no hay ninguna reina en la misma fila y columna
   que la que estamos evaluando ni tampoco si se encuentra en alguna de sus 
   diagonales.
 */
int esPosicionValida (signed int *tablero, signed int nivel) {
   int i;
   for (i = 0; i < nivel; i++) {
      if ((tablero[nivel] == tablero[i]) || (abs(tablero[i] - tablero[nivel]) == abs(i - nivel))) {         
         return 0;   
      }   
   }
   return 1;
}

/**
   Comprueba si a partir de la posición actual podemos seguir avanzando en el 
   árbol de soluciones o no.
   Hay que avanzar en el árbol siempre que no hayamos alcanzado el último nivel 
   y la posción donde hemos colocado la reina sea valida.
 */
int hayQueAvanzar(signed int *tablero, signed int nivel, int n) {
   return ((nivel < n) && esPosicionValida(tablero, nivel));
}

/**
   Comprueba si se ha llegado a una solución valida o no.
   Una solucion valida se da cuando estamos en el último nivel del árbol y la 
   reina está en  una posición valida.
 */
int haySolucion (signed int *tablero, signed int nivel, int n) {
   if ((nivel == (n-1)) && esPosicionValida(tablero, nivel)) {
      return 1;
   }
   return 0;
}

/**
   Comprueba si hay más hermanos para el nodo actual del árbol de soluciones.
   Habran más hermanos para el nivel actual, si la reina no está colocada en la
   última columna.
 */
int hayMasHermanos (signed int *tablero, signed int nivel, int n) {
   return (tablero[nivel] < (n-1));
}

/**
   Retrocede un nivel en el árbol de soluciones.
 */
void retrocederNivel (signed int *tablero, signed int *nivel) {
   tablero[*nivel] = -1;
   *nivel = *nivel - 1;
}

/**   
   Algoritmo que se encarga de buscar las soluciones.
 */
void nreinas (signed int *tablero, int n) {
   signed int nivel = 0;   
   int i, j;
   int numSoluciones = 0;
   
   tablero[0] = -1;
   printf("Buscando solucion para %d reinas\r\n", n);
   
   do {
      generarNivel(tablero, nivel);
            
      if (haySolucion (tablero, nivel, n)){
         numSoluciones++;
         
         printf("Solucion %d encontrada: \r\n", numSoluciones);
         
         for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
               if (tablero[i] == j) 
                  printf("[Q]");
               else
                  printf("[ ]");
            }
            printf("\r\n");
         }   
         printf("\r\n");
      }
      if (hayQueAvanzar(tablero, nivel, n)) {         
         nivel++;
         tablero[nivel] = -1;   //inicializamos tablero para dicho nivel
      } else {
         while (!hayMasHermanos(tablero, nivel, n) && (nivel > -1)) {
            retrocederNivel(tablero, &nivel);
         }
      }
   } while (nivel > -1);
   
   printf("Numero de soluciones encontradas: %d\r\n", numSoluciones);
}

void main() {
   
   /* Array que representa el tablero de ajedrez. En vez de usar una matriz se
      un array donde cada posición del array representa la columna en la que se
      coloca la reina, para la fila i-esima, es decir, si por ejemplo tenemos que
      en la posición 4 del arraya hay un 3, quiere decir que hay una reina en la
      fila 5, columna 4 (considerando que se comienza a númerar desde 0). De esta
      forma tambien nos permite comprobar rapidamente si hay una reina en la misma
      fila, columna o diagonal que la que estamos testeando.
   */
   signed int tablero[NUM_REINAS];
   int  i;
   
   setup_adc_ports(NO_ANALOGS|VSS_VDD);
   setup_adc(ADC_OFF|ADC_TAD_MUL_0);
   setup_psp(PSP_DISABLED);
   setup_spi(SPI_SS_DISABLED);
   setup_wdt(WDT_OFF);
   setup_timer_0(RTCC_INTERNAL);
   setup_timer_1(T1_DISABLED);
   setup_timer_2(T2_DISABLED,0,1);
   setup_comparator(NC_NC_NC_NC);
   setup_vref(FALSE);
   
   printf("www.TODOPIC.com.ar\r\n");
   printf("Mini-Concurso de progracion en C:\r\n");
   printf("Las 8 reinas.\r\n");
   printf("Nombre del concursante: Jose Lopez Lopez\r\n");
   
   //Inicializacion del tablero
   for (i = 0; i < NUM_REINAS; i++) {
      tablero[i] = -1;
   }
   
   nreinas(tablero, NUM_REINAS);
   
   while (1){};
  
}