C++ zadanie z backtracking'iem - kłopot

Witam.
Mam takie zadanie do napisania: http://4programmers.net/Pastebin/2518 .
Na razie napisałem tyle: http://4programmers.net/Pastebin/2519 .
Mam do was prośbę: Czy możecie sprawdzić, czy dobrze to robię i podpowiedzieć ewentualnie jak i gdzie zaimplementować to sprawdzanie najmniejszej ilości żołnierzy?
Pytam bo mam już mały mętlik w głowie. Chyba za dużo nad tym ślęczę :)
Będę bardzo wdzięczny za wszelką pomoc.
Pozdrawiam.

Nie tędy droga: Algorytm na ustawienie 8 hetmanów/żołnierzy
Co z tego cop napisałeś ma coś wspólnego z algorytmem węgierskim?

Może spróbuj tak:

Zaczynasz w sytuacji, gdy wybrane masz działa po ukosie:

int MaxInc = 0;
int Change = 0;
int Inc = 0;
int Result[4] = {0, 1, 2, 3};
for(int i=0; i<4;++i)
{
   MaxInc = 0;
   Change = i;
   for(int j=0; j<4;++j)
   {
      int Inc = Pole[i][i] + Pole[j][j] - Pole[i][j] - Pole[j][i]; //Ile zyskam na 'zamianie' kolumn
      if( Inc > MaxInc) { MaxInc = Inc; Change = j; }
   }

   if(MaxInc > 0) std::swap(Result[i], Result[Change]); //Jeśli istnieje zamiana z max zyskiem, to zamień kolumny
}

Pisane na czuja, zaraz zrobię testa na szybko. Nie jestem pewien, czy nie będziesz musiał iterować, dopóki istnieją 'zamiany' z jakimkolwiek zyskiem.

_13th_Dragon
Ja mam to zadanko zrobić bactracking'iem, a nie algorytmem węgierskim. Wiem ,że dużo na ten temat pisaliśmy, zwłaszcza ty i chwała ci za to jeszcze raz.
Jednak muszę to zrobić trochę inaczej. Algorytm węgierski za to przydał mi się do innego podobnego zadania.

@Ola Nordmann, rzesz nakombinował!
Po pierwsze ten algorytm jest do rozwiązania w czasie wielomianowym, patrz link w poście wyżej.
Po drugie:

1. Dodatkowa tablica: result[N]={1,2,3,4,...};
2. Sumowanie: sum+=Tab[i][result[i]-1];
3. Następna kombinacja: do { ... } while(next_permutation(result,result+N));

Czyli całość 5-wierszy.

Czyli rozumiem, że te cztery wiersze to dodatkowo do tego z linka?
PS: Czyli to co mam to źle?

Może jeszcze jakieś propozycje?