int  LeggiClock    ( void );
void Maschera      ( void );
void Regine        ( int );
void VediSoluzione ( void );

/*---------------------------------------------------------------------------
            P R O B L E M A   D E L L E   N  R E G I N E

Si voglia disporre su una scacchiera quadrata con Lato assegnato, un numero
di Regine (degli Scacchi) pari al numero di caselle del lato, senza che
alcun pezzo ne tenga un altro sotto scacco.
La scacchiera, con righe e colonne da 1 a Lato, viene solo immaginata e
non corrisponde ad una reale variabile in memoria: ne controlliamo le
proprietà tramite gli array:
   Casa []        indica la colonna occupata da ciascuna Regina
                  usato solo per visualizzare le soluzioni
   Colonne []     segnala le colonne occupate
   Destre []      segnala le diagonali principali occupate
   Sinistre[]     segnala le diagonali secondarie occupate

Le diagonali sono in numero quasi doppio rispetto alle righe e alle colonne,
andranno quindi dimensionate adeguatamente.

--------------------------- Variabili Globali ----------------------------*/
int   Lato;           // misura del lato della scacchiera in esame
long  Totale;         // totale delle configurazioni trovate
int   Casa    [ 50];  // indica la colonna occupata da ciascuna Regina
int   Colonne [ 50];  // segnala le colonne occupate
int   Destre  [100];  // segnala le diagonali principali occupate
int   Sinistre[100];  // segnala le diagonali secondarie occupate

/*=========================================================================*/
void main (void)
{ int i,
      Time1, Time2;
      char Buffer[100];

  do
  { Maschera();
    gotoxy (20, 23); textcolor(11);
    cprintf("Lato della scacchiera (1..20): ");
    Lato = atoi (gets(Buffer));
  }
  while (Lato<1 || Lato>20);

  Maschera();

  Totale = 0;
  for (i=0; i< 50; Colonne [i] = 0, i++);
  for (i=0; i<100; Sinistre[i] = Destre[i] = 0, i++);

  Time1 = LeggiClock ();
  Regine (1);
  Time2 = LeggiClock () - Time1;

  gotoxy (8, 23); textcolor(10);
  cprintf ("Scacchiera con lato %2d :%10ld soluzioni in %8.3f secondi\n",
            Lato, Totale, Time2/18.2 );
  while (getch() != 27);
}

/*=========================================================================
  Funzione ricorsiva per il posizionamento delle Regine sulla Scacchiera
  Utilizza le variabili globali
      Lato        lato della scacchiera da esaminare
      Totale      totale delle configurazioni trovate
      Casa []     indica la colonna occupata da ciascuna Regina
      Colonne []  segnala le colonne occupate
      Destre []   segnala le diagonali principali occupate
      Sinistre[]  segnala le diagonali secondarie occupate

  Le case della diagonale destra hanno costante la differenza tra gli indici.
  Le case di una diagonale sinistra hanno costante la somma degli indici.
  Nei tre array 0 indica la linea libera, 1 indica la linea occupata.
--------------------------------------------------------------------------*/
void Regine
( int Rig
)
{ int Col,   // 1 <= Col <= Lato successive posizioni sul rigo da tentare
      Sin,   // su diagonale sinistra: Sin = Col + Rig
      Dex;   // su diagonale destra: Dex = Col - Rig + Lato
             // (+Lato per evitare indici negativi).

  for (Col=Lato, Sin=Col+Rig, Dex=Col-Rig+Lato; Col; Col--, Sin--, Dex--)
  { // poiché Rig e Lato sono costanti, Sin e Dex sono funzione
    // solo di Col e quindi vengono decrementate parallelamente.
    if ( ! Colonne  [Col] &&
         ! Sinistre [Sin] &&
         ! Destre   [Dex]   )
    { Colonne [Col] = Sinistre [Sin] = Destre [Dex] = 1; Casa[Rig] = Col;
      if ( Rig < Lato ) Regine (Rig+1);
      else              Totale ++, VediSoluzione();
      Colonne [Col] = Sinistre [Sin] = Destre [Dex] = 0;
    }
  }
}

/*=========================================================================
 Lettura del Timer di sistema all'indirizzo RAM 0046Ch, 
 aggiornato dal PIT, tramite l'IRQ0, 18.2 volte al secondo
--------------------------------------------------------------------------*/
int LeggiClock (void)
{ asm { push Es
        xor  Ax, Ax
        mov  Es, Ax
        mov  Ax, Es:[0x046c]
        pop  Es
      }
  return _AX;
}

/*=======================================================================*/
void Maschera (void)
{ int i;

  clrscr(); textbackground(4); textcolor(0);
  gotoxy( 2, 1); for(i=2; i<=79; cprintf(" "),i++);
  gotoxy(20, 1); cprintf("P R O B L E M A   d e l l e   N   R E G I N E");
  gotoxy( 2,25); for(i=2; i<=79; cprintf(" "),i++);
  gotoxy(58,25); cprintf("di Luigi Lamberti");
  textbackground(0); textcolor(7); gotoxy (1, 3);
}

/*==========================================================================
  Visualizza una soluzione del gioco. Utilizza le variabili globali
      Lato        lato della scacchiera da esaminare
      Totale      totale delle configurazioni trovate
      Casa []     indica la colonna occupata da ciascuna Regina
--------------------------------------------------------------------------*/
void VediSoluzione (void)
{ int r, c, x;

  textcolor(11);
  for (r=1; r<=Lato; r++)
  { gotoxy (20,r+2); c = Casa[r];
    for (x=1; x<c; cprintf ("ù "), x++);
    cprintf ("W ");
    for (x=c+1; x<=Lato; cprintf ("ù "), x++);
  }
  gotoxy (8, 23); textcolor(10);
  cprintf ("Lato %2d :%10ld soluzioni", Lato, Totale);
}