#include <stdio.h>
#include <stdbool.h>
#define DIM 8
bool grid[DIM][DIM]={false};
/* Inserisce una regina a partire dalla riga */
/* restiruisce true se l'iserimento è stato fatto, altrimenti false */
bool insert_queen ( int riga );
/* verifica se la cella è sotto attacco */
bool sotto_attacco ( int riga, int colonna );
/* visualizza la configurazione delle regine sulla scacchiera */
void visualizza ();
int main()
{
if ( insert_queen(0)) visualizza();
else printf("\nNessuna configurazione trovata");
return 0;
}
bool insert_queen ( int riga )
{
bool inserimento = false;
for ( int colonna = 0; colonna < DIM && !inserimento; ++colonna ){
if ( !sotto_attacco(riga, colonna) ) { //se la cella non è sotto attacco posiziona la regina
grid[riga][colonna] = true;
if ( riga == DIM-1 ) inserimento = true; // (si giunge a questo passo se) regina all'ultima riga è stata piazzata con successo
else inserimento = insert_queen ( riga + 1); //iazzata una regina in una riga cerchiamo di piazzarne altre alle righe successive ricorsivamente
if ( !inserimento ) grid[riga][colonna] = false; // se non c'è stato inserimento corretto porta la cella a false
}
}
return inserimento;
}
bool sotto_attacco ( int riga, int colonna )
{
bool attacco = false;
for ( int dx = -1; dx <= 1 && !attacco; ++dx ) { //dx = spostamento su riga. sono possibili 3 spostamenti -1=su 0=stessa 1=giù
for(int dy = -1; dy <= 1 && !attacco; ++dy ) {
if (dx!=0 || dy!=0) { //considera tutte le celle adiacenti alla cella considerata
int x = riga + dx; int y = colonna + dy; //definisce la situazione di tutte le celle
while ( x>=0 && x < DIM && y>=0 && y < DIM && !attacco) {
attacco = grid[x][y];
x+=dx; y+=dy;
}
}
}
}
return attacco;
}
void visualizza ()
{
int scacc[DIM][DIM];
//inizializza la scacchiera come vuota
for (int i=0; i<DIM; i++)
for(int j = 0; j<DIM; j++)
scacc[i][j] = '-';
//inserisci regine
for (int i = 0; i<DIM; i++){
for (int j=0; j<DIM; j++)
if( grid[i][j] ) scacc[i][j] = '#';
}
//stampa scacchiera
for (int i = 0; i<DIM; i++){
for (int j = 0; j<DIM; j++)
printf("%3c", scacc[i][j]);
printf("\n");
}
return;
}