Gata  , am rezolvat, a fost o problema de neatentie din partea mea  , in back-ul in care generam linia eu foloseam ca numar de coloane pe "n".

Mersi George Marcus pentru ca ti-ai aratat interesul in a ma ajuta. 

Pai in algoritmul meu, "linie[16]" reprezinta o linie cu "m" componente, care contine semnele pentru fiecare
coloana  (generate de backtracking). Daca parcurg fiecare coloana din fiecare linie a matricei, cu "j",
atunci si vectorul cu semne pentru fiecare coloana il parcurg tot cu acelasi "j".

Dupa ce am trecut singur prin toate etapele discutate aici (greedy -20pct, back simplu-40pct) am ajuns la backul optimizat care ar trebui sa dea 100 de pct, dar imi da 70 si chiar nu pot sa-mi dau seama de ce... 
Vazand ca nu gasesc nimic in neregula, am aruncat un ochi pe sursele de 100 de pct trimise si e exact aceiasi idee... Deci nu inteleg de ce nu merge...
Va rog, daca se poate uita cineva pe sursa pe care am trimis-o si sa-mi zica daca vede ceva gresit...