Tocmai, nu e deloc greu cu back De aia ma gandeam la ceva mai interesant, in masura in care se va putea.

Alin

OK, dupa ceva incercari 30, 70, 90, 100.
Nu am facut cu backtracking, desi e clar ca asa ar fi cel mai bine.
Am facut un soi de greedy cu perturbari random - deci un algoritm probabilist.
Adica, incerc sa maresc maximal suma pe principiile de bun-simt, pe linie si coloana - cand chestia se poate, flip. In caz ca nu se poate mari suma, atunci coafez matricea pseudoaleator de cateva ori si continui cautarea.
Cea mai interesanta chestie la solutia mea cred ca este faptul ca merge . Tehnic vorbind, cred ca este asemanatoare cu random-restart steepest ascent hill-climbing: http://en.wikipedia.org/wiki/Hill_climbing doar ca nu face random-restart, ci random-sidestepping, random-jiggle, sau cam asa ceva. Oricum, traiasca si-nmulteasca(-se) random seed-ul de pe masina de evaluare .

O sa incerc acum si cu backtracking si... mai am o idee .

Alin