/* Voglio avvalermi di AMPL+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 AMPL 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; # volendo potremmo proseguire qui con i dati specifici dell'istanza qualora essi si discostino dai valori di default (in questo caso sufficienti a descrivere completamente l'istanza principe). # il modo migliore di specificare istanze specifiche e variabili e' farlo da un file separato da includere qui con: # include queens.dat; # oppure: # data queens.dat; # lanciamo lo script per la visualizzazione e la stampa dei risultati su piu' media: include queens_ampl_run.txt;