Newsgroup: it.hobby.enigmi
Titolo: MathMagic - Problem of the Month (Nov 2002)

Approfitto del sito segnalato da Dario per presentare il problema 
attuale presentato sul sito (trad. a mia cura...).
;-)
Le matrici seguenti sono interessanti per le seguenti tre proprieta':
1) Tutti le celle hanno interi positivi distinti
2) La somma di ogni riga e' equivalente per tutte le righe
3) Il prodotto di ogni colonna e' equivalente per tutte le colonne
Possiamo chiamare queste matrici "somma-prodotto" oppure piu'
semplicemente "Matrici SP".
Ecco due esempi:
   ---- ----                ---- ---- ---- 
  |  4 | 20 |              |  4 | 10 | 12 |
   ---- ----                ---- ---- ---- 
  | 15 |  9 |              | 15 |  6 |  5 |
   ---- ----                ---- ---- ---- 
  | 18 |  6 |
   ---- ----
Queste sono le "Matrici SP" 3x2 e 2x3 con i + piccoli interi.
E' facile verificare che non esistono "Matrici SP" 1xn, nx1 e 2x2.
Esistono di altre dimensioni ? Quali quelle con i + piccoli interi ?
Ci sono "Matrici SP" dove la Somma delle righe ed il Prodotto delle
colonne e' equivalente ?
CiaO,
Massimo

 Esistono di altre dimensioni ? Quali quelle con i + piccoli interi ?
s
p
o
i
l
e
r
s
p
o
i
l
e
r
s
p
o
i
l
e
r
Direi di si`; ad esempio, quelle con i piu` piccoli interi sono
4x2:
 3  9 12 18
24  8  6  4
2x4:
 1 10
 5  6
 8  3
 9  2
3x3:
 3  9 12
 8 10  6
15  4  5
Ho usato le solite tecniche prese a prestito dall'Intelligenza 
Artificiale: Constraint Logic Programming (in particolare ECLiPSe 
www.icparc.ic.ac.uk
 ). Usando ordinamenti lessicografici per ridurre le 
simmetrie, in un paio di secondi trova la soluzione ottima.
Questa volta posto anche il programma, visto che ho avuto un attimo di 
tempo per commentarlo:
:- lib(fd_global).
:- lib(matrix_util).
sp(R,M,N,D) :-
 % Definisco una matrice MxN, che mi viene data come lista di righe in R
 % e lista di colonne in C
	matrix(M,N,R,C),
 % Costruisco la lista di tutte le variabili
	flatten(R,Flat),
 % Assegno un dominio alle variabili che va da 1 a D
	Flat :: 1..D,
 % impongo che i valori siano tutti diversi
	fd_global:alldifferent(Flat),
 % impongo che le righe abbiano la stessa somma
	suml(R,_Sum),
 % impongo che le colonne abbiano lo stesso prodotto
	prodc(C,_Prod),
 % elimino le simmetrie di riga
	sym(R),
 % elimino le simmetrie di colonna
	sym(C),
 % calcolo il valore massimo fra le variabili
	maxlist(Flat,Max),
 % faccio partire la search: minimizzo il valore massimo
	minimize(labeling(Flat),Max).
suml([L],S) :- !,
	sumlist(L,S).
suml([H|T],S) :-
	sumlist(H,S),
	suml(T,S).
prodc([L],P) :- !,
	prod(L,P).
prodc([H|T],P) :-
	prod(H,P),
	prodc(T,P).
prod([X],X) :- !.
prod([H|T],P) :-
	prod(T,P1),
	P #= P1*H.
sym([_]) :- !.
sym([A,B|T]) :-
	lexico_le(A,B),
	sym([B|T]).
ciao ciao,
Marco
--
http://www.ing.unife.it/docenti/MarcoGavanelli/

 Esistono di altre dimensioni ?
avevo trovato - a mano - una 6X2 con tutti i divisori di 120
 3  4  8 10 20 60
40 30 15 12  6  2
...magari ho pure trovato la più piccola, chissà.
La verità è che vorrei avere il tempo e la competenza necessaria ad
affrontare il mondo affascinante dell'IA.
--
Ciao, Silv:o)

 ...magari ho pure trovato la più piccola, chissà.
Si`, hai trovato la piu` piccola, secondo le regole (quella col valore 
massimo piu` piccolo). Il mio programma ne trova un'altra, sempre con 
valore massimo 60:
 1  6 12 15 20 30
60 10  5  4  3  2
Ciao,
Marco
--
http://www.ing.unife.it/docenti/MarcoGavanelli/