/*
Voglio avvalermi di GMPL+Solver per risolvere il celebre problema delle 8 regine:
   collocare un massimo numero di regine su una scacchiera in modo che non ve
ne siano due che si "vedano".

Questo modello GMPL e' stato creato da Romeo Rizzi, romeo.rizzi@univr.it
a scopi didattici.
*/

param NUM_ROWS integer, >= 1, default 8;  # Numero di righe della scacchiera
param NUM_COLS integer, >= 1, default 8;  # Numero di colonne della scacchiera

set Rows := 1..NUM_ROWS;  # Insieme degli indici di riga
set Cols := 1..NUM_COLS;  # Insieme degli indici di colonna

set CELL := {Rows, Cols};  # Insieme delle caselle della scacchiera      

param VALORE{CELL} >= 0, integer, default 1;    # Valori delle celle (tutti ad uno nel problema classico dove si vuole massimizzare il "numero" di regine collocate)

var metto{CELL} binary; # introduciamo una variabile di scelta binaria per ogni cella, essa vale 1 se vi colloco una regina, 0 altrimenti

# Definizione della funzione obiettivo:
maximize MaxVal:
         sum{(i,j) in CELL} VALORE[i,j] * metto[i,j];

# prima famiglia di vincoli: al piu' una regina per riga:
subject to alPiuUnaSuRiga{i in Rows}: 
        sum{j in Cols} metto[i,j] <= 1;

# seconda famiglia di vincoli: al piu' una regina per colonna:
subject to alPiuUnaSuColonna{j in Cols}: 
        sum{i in Rows} metto[i,j] <= 1;

# terza famiglia di vincoli: le diagonali:
#set RminusC = (1-NUM_COLS)..(NUM_ROWS-1);
subject to alPiuUnaSuDiag{d in (1-NUM_COLS)..(NUM_ROWS-1)}: 
        sum{(i,j) in CELL : i-j = d} metto[i,j] <= 1;

# quarta famiglia di vincoli: le antidiagonali:
#set RplusC = 2..NUM_ROWS+NUM_COLS;
subject to alPiuUnaSuAntidiag{d in 2..NUM_ROWS+NUM_COLS}: 
        sum{(i,j) in CELL : i+j = d} metto[i,j] <= 1;

solve;

# option omit_zero_rows 1; # non voglio vengano visualizzate variabili a zero
display metto;
printf "VALORE TOTALE = ";
display sum{(i,j) in CELL} VALORE[i,j] * metto[i,j];