Algorytm na ustawienie 8 hetmanów/żołnierzy

0

Witam.
Mam napisać program, który tak rozstawi na planszy żołnierzy, żeby nie mogli ze sobą walczyć, tzn. żeby w każdym wierszu i w każdej kolumnie nie znajdował się więcej niż jeden (żeby się nie powtarzali). Trzeba to zrobić tak żeby liczba żołnierzy na planszy była jak najmniejsza.
Mam mały mętlik w głowie wiec proszę was o pomoc. Może ma ktoś jakieś sugestie co do tego algorytmu?
Z góry dzięki za pomoc i pozdrawiam.

1

Ale chodzi o hetmanów czy o wieże? Bo hetman potrafi atakować też na skos ;] Jeśli chodzi o same wieże to sposób podałem ci już w ostatnim temacie, tzn wystarczy ustawić sobie ich "po skosie"
1 0 0 0 0 ... 0
0 1 0 0 0 ... 0
0 0 1 0 0 ... 0
0 0 0 1 0 ... 0
0 0 0 0 1 ... 0
...
0 0 0 0 0 ... 1
Ale jeśli chodzi o hetmanów to jest t bardziej skomplikowane.
http://www.algorytm.org/inne/problem-8-hetmanow.html

1

Jeżeli ilość jak najmniejsza to będzie to zero, jeżeli koniecznie musisz postawić to jeden.
Jeżeli jednaj ilość jak największa, to ustawiasz po dowolnej przekątnej, po czym możesz poprzestawiać losowo wiersze oraz kolumny.

1

Przy podanych warunkach, najprostszym rozwiązaniem jest nie wstawiać żadnego zołnierza na planszę.
//Za wolno pisałem

2

Poza sprostowaniem tej "najmniejszej ilości" napisz też, co to jest "żołnierz", bo takiej figury nie kojarzę.

2

Zakładam że chodzi o problem 8 hetmanów (bo to chyba jedyne sensowne dopasowanie do Twojego opisu + to dość klasyczne zadanie).

Niezbyt mi się podoba opis i kod na algorytm.org linkowane przez shaloma (http://www.algorytm.org/inne/problem-8-hetmanow.html) + nigdy tego w sumie nie implementowałem, więc spróbuję samemu omówić.

No więc najpierw oczywista kwestia - nie może być dwóch hetmanów w jednym wierszu (bo by się nawzajem atakowali). Korzystając z tego, można reprezentować rozwiązanie za pomocą tablicy n-elementowej (n = wielkość szachownicy, w klasycznym przypadku 8), gdzie pierwsze pole oznacza kolumnę pierwszego hetmana, drugie pole kolumnę drugiego itp. Przykładowo, tablica [2, 0, 3, 1] oznacza:

..x. (2) (indeksujemy od zera, jak zwykle)
x... (0)
...x (3)
.x.. (1)

(po co taka reprezentacja? upraszcza napisanie algorytmu znajdującego).

No i zadanie algorytmu to znalezienie takiej tablicy, która będzie odpowiadała odpowiedniemu rozmieszczeniu hetmanów.
Najpierw wstawiamy pierwszego hetmana na pierwsze miejsce, później drugiego tak żeby nie atakował pierwszeg, później trzeciego tak żeby nie atakował poprzednich dwóch (lub wracamy do ustawiania pierwszego, jesli trzeciego się tak nie da ustawić) itd:

void place_queens(vector<int> queens, int ndx) {
    int dim = queens.size(); // szerokość/wysokość szachownicy
    // założenie `indukcyjne` - hetmani [0; ndx) są poprawnie ustawieni
    if (ndx == queens.size()) {
        print_board(queens); // rozmieściliśmy wszystkich hetmanów, pozostaje wypisać rozwiązanie
    } else { // ustawiamy n+1tego hetmana
        for (int col = 0; col < dim; col++) { // próbujemy wszystkich kolumn
            bool col_ok = true; // niezbyt ładna ta zmienna, ale niech juz będzie
            for (int prev = 0; prev < ndx; prev++) { // sprawdzamy czy po postawieniu nie zaatakujemy któregoś poprzedniego
                if (col == queens[prev] || abs(col - queens[prev]) == ndx - prev) {
                    col_ok = false; break;
                }
            }
            if (col_ok) { // skoro kolumna jest `nieatakowana`...
                queens[ndx] = col; // ...ustawiamy tam hetmana...
                place_queens(queens, ndx + 1); // ...i sprawdzamy dalej
            }
        }
    }
}

void n_queens(int n) {
    vector<int> queens(n);
    place_queens(queens, 0);
}

print_board to pomocnicza funkcja rysująca planszę (ale u Ciebie może robić cokolwiek innego z każdym rozwiązaniem):

void print_board(vector<int> queens) {
    for (int row = 0; row < queens.size(); row++) {
        for (int col = 0; col < queens.size(); col++) {
            printf("%c", queens[row] == col ? 'x' : '.');
        } printf("\n");
    } printf("---\n");
}
0

Dzięki Panowie za pomysły. Trochę mi się już rozjaśniło. Wrzucam jednak treść zadania: http://4programmers.net/Pastebin/2474.
Co wy na to? Jeszcze bardziej zakręcone co nie?

0

Witam, właśnie bawię się algorytmem węgierskim i mam problem przy "wykreślaniu" zer, mógłby ktoś podpowiedzieć jak to najłatwiej zrobić? Z góry dzięki :)

1
vector<vector<unsigned> > Tb(N,vector<unsigned>(N,0));
vector<bool> DeletedRow(N),DeletedCol(N);

// Jeżeli MSM ma racje i problemem jest algorytm to ...
while(true) 
  {
   vector<unsigned> Row(N),Col(N);
   for(unsigned y=0;y<N;++y) if(!DeletedRow(y)) for(unsigned x=0;x<N;++x) if((!DeletedCol(x))&&(!Tb[y][x])) { ++Row(y); ++Col(x); }
   vector<unsigned>::iterator R=max_element(Row.begin(),Row.end()),C=max_element(Col.begin(),Col.end());
   if(*R>*C) DeletedRow[R-Row.begin()]=true;
   else if(*C) DeletedCol[C-Col.begin()]=true;
   else break;
  }
0

@_13th_Dragon - myślę że chodziło bardziej o to w jaki sposób najprościej wykreślić wszystkie zera jak najmniejszą liczbą linii.
To dokładnie odpowiada szukaniu minimum vertex cover w grafie dwudzielnym, ale nie wiem czy taka redukcja łapie się pod prosty sposób (i raczej nie jest optymalne wykonywanie całej roboty od zera za każdym razem) ;).

edit: większość opisów algorytmu w sieci jest widocznie kierowana do humanistów, bo ten punkt jest kwitowany wykreśl zera jak najmniejszą ilością linii i ani słowa o metodzie. Jak na razie, znalazłem coś takiego:

Draw the minimum number of vertical and horizontal lines necessary to cover all the zeros in the reduced matrix obtained from step 3 by adopting the following procedure:
Mark all the rows that do not have assignments.
Mark all the columns (not already marked) which have zeros in the marked rows.
Mark all the rows (not already marked) that have assignments in marked columns.
Repeat steps 5 (i) to (iii) until no more rows or columns can be marked.
Draw straight lines through all unmarked rows and marked columns.

1 użytkowników online, w tym zalogowanych: 0, gości: 1