/***   IL PROBLEMA DELLE n REGINE         ***/



/*  

IL PROBLEMA
===========

Sia Ch una scacchiera (chessboard)  di dimensione n X n.

Date due regine  (queen) Q1 e Q2 di Ch,
diciamo che Q1  ATTACCA  Q2 se e solo 
se si verifica una delle seguenti condizioni:

-  Q1 e Q2 sono sulla stessa riga
-  Q1 e Q2 sono sulla stessa colonna
-  Q1 e Q2 sono sulla stessa diagonale


Il problema consiste nel disporre n regine  in Ch
in modo che non si attacchino a vicenda.


INPUT
=====

Il valore di n e' letto di standard input.
Si assume n>=4 (altrimenti il problema non ha soluzione)

OUPTUT
======

Devono essere stampate tutte le soluzioni



ESEMPIO
======

Per n=4, l'output e'

SOLUZIONE 1

- X - - 
- - - X 
X - - - 
- - X - 


SOLUZIONE 2

- - X - 
X - - - 
- - - X 
- X - - 


STRUTTURA DATI
==============

Per rappresentare la scacchiera Ch n X n, usiamo  una matrice di char 
di dimensione n X n allocata dinamicamente.

- se Ch[r][c] = EMPTY, significa che la casella (r,c) e' vuota

- se Ch[r][c] = QUEEN, significa che nella casella (r,c) c'e' una regina



*****/




#include <stdio.h>
#include <stdlib.h>

#define EMPTY   '-'  //  casella vuota
#define QUEEN   'X'  // regina 



/***  MAIN  ***/


int main1();
int main2();
int main3();


int main(){
  return main1(); // esegue main1()
}


/*** GESTIONE DELLE MATRICI  ***/


/*  Data la matrice quadrata  M di dimensione n X n,
    pone a EMPTY tutte le caselle nelle righe r tali che row <= r < n 

*/
  
void clean(int row, char **M, int n){
  // ....
   }




/* Crea una matrice quadrata  n X n inizializzata a EMPTY
   e restituisce l'indirizzo della matrice creata
*/

char **newMatr(int  n){
  // ...
  return NULL;
}



/*  Stampa la matrice  quadrata  M  di dimensione  n X n   */

void printMatr(char **matr, int n){
  int r,c;
   for(r=0; r < n ; r++){
    for(c=0; c < n ; c++)
      printf("%c ", matr[r][c]);
    putchar('\n');
  }
}


/*** TEST DI PROVA  ***/


int main1(){
  int n;
  char **ChessBoard;
  printf("Dimensione della scacchiera ---> ");
  scanf("%d", &n);
  ChessBoard = newMatr(n);
  printf("\nScacchiera %d X %d vuota:\n\n", n, n);
  printMatr(ChessBoard,n);
  return 0;
}




/****  FUNZIONI PER RISOLVERE IL PROBLEMA  *****/


/* 

Data la scacchiera Ch di dimensione  n X n, in ogni riga va collocata una e una sola regina. 


Chiamiamo Q(r) la regina alla riga r.

Nella nostra rappresentazione:

-    Q(r) e' nella  colonna  c   SE E SOLO SE    Ch[r][c] = QUEEN


Disponiamo le regine a partire da Q(0) fino  a Q(n-1) (regina nell'ultima riga)  
usando il seguente procedimento ricorsivo.



PROCEDURA RICORSIVA PER TROVARE LE SOLUZIONI
============================================

Assumiamo che 

(*)  Le regine alle righe Q(0),..., Q(r-1) siano  state gia' disposte

(per r=0 l'ipotesi vale banalmente).

Diciamo che la posizione (r,c) e' SAFE (sicura) se mettendo Q(r) in (r,c) 
la regina Q(r) non attacca nessuna delle regine Q(0),...,  Q(r-1)


La procedura  deve disporre le  rimanenti regine Q(r), ..., Q(n-1).

CASO BASE: r=n
==============

In questo caso, per l'ipotesi (*),  tutte le regine   Q(0),..., Q(n-1)
sono state posizionate e Ch contiene una soluzione al problema


PASSO INDUTTIVO: r<n
====================

1) Devo trovare una posizione per  Q(r). Quindi:

   1.1)   Trovo una colonna  c (0<= c < n)  tale che (r,c) e' safe
    
   1.2)   Metto Q(r) in (r,c)


2)  Ricorsivamente, chiamo  la procedura per posizionare  la regine Q(r+1)


NOTA
====

- Per trovare tutte le soluzioni, occorre fare in modo che  al punto 1.1) 
  vengano provate tutte le colonne.

- Prima  di cercare una nuova colonna c per Q(r), 
  occorre PULIRE le righe r, r+1, ... n.
  Infatti, vanno mantenute le regine Q(0), ... , Q(r-1), 
  ma vanno tolte le regine Q(r), ... Q(n-1) (che dovranno essere riposizionate). 
  

*/



/*

Sia   Ch una scacchiera  n X n in cui sono gia' disposte le regine
Q(0), ... , Q(r-1).

La funzione restituisce 1 se la posizione (r,c) e' safe,
0 altrimenti.
 
*/

int safe(int r, int c, char **Ch, int n){
    // ...
   return -1;
}



/*** TEST DI PROVA  ***/

int main2(){
  char **ChessBoard;
  int c,r,n=6;
  ChessBoard = newMatr(n);
  
// Provare  a  cambiare la disposizione delle regine

  ChessBoard[0][0] = QUEEN;
  ChessBoard[1][2] = QUEEN;
  ChessBoard[2][4] = QUEEN;
  printMatr(ChessBoard,n);
  putchar('\n');
  r = 3;
  for(c=0; c<n ;c++)
    if(safe(r,c, ChessBoard,n))
      printf("(%d, %d):  safe\n", r,c);
    else
      printf("(%d, %d):  NOT safe\n", r,c);
  return 0;
}

/*

Sia   Ch una scacchiera  n X n in cui sono gia' disposte le regine
 Q(0), ... , Q(r-1) (in modo che non si attacchino a vicenda)


La funzione  stampa tutte le soluzioni ottenute posizionando
le rimanenti regine  Q(r), ... , Q(n).


Ad ogni istante dell'esecuzione,
la locazione di memoria *sol  deve contenere il numero di soluzioni
trovate fino a quel punto

*/



void queen(int r, char **Ch, int n, int *sol){
  // ... 
}


/***   FUNZIONE PRINCIPALE PER RISOLVERE IL PROBLEMA DELLE n REGINE       ***/

int main3(){
  char **ChessBoard;
  int n;
  int sol = 0; // numero soluzioni trovate
  scanf("%d",  &n);
  if(n>=4){
    ChessBoard = newMatr(n);
    queen(0, ChessBoard, n, &sol);
  }
  else
    printf("Per n = %d il problema non ha soluzioni\n", n);
  return 0;
}