# Zadanie domowe na wdi
## Polecenie:
9. [2] Napisz funkcję minhetmany, która znajduje minimalną liczbę hetmanów atakujących
wszystkie pola szachownicy n$\times$n. (Dokładniej, Twoja funkcja powinna zwrócić taką liczbę
k, że przy pewnym ustawieniu k hetmanów atakowane są wszystkie pola szachownicy nn
i nie jest możliwe ustawienie k – 1 hetmanów tak, aby wszystkie pola szachownicy nn
były atakowane.)
## Rozwiązanie
w moim rozwiązaniu zastosuję metodę brute-force:
1. $m\leftarrow\text{startingPoint}(x)$
2. dopuki $m < n$:
3. Jeżeli można zapełnić całą planszę m-hetmanami:
4. $m\leftarrow m+1$
5. W przeciwnym wypadku:
6. zwróć m-1

czyli w ```c``` bedzie to wyglądało tak:

int minHetmany(int n){
    int m = startingPoint(n);
    while (m < n){
        if(solves(m, n)){
           m = m+1; 
        }
        else{
            return m-1;
        }
    }
}

### Funkcja startingPoint:
Przyjmuje ```int n```, gdzie n to rozmiar planszy.

int startingPoint(const int n) {
    for (int m = 1; m < n; m++) {
        if(n%2==0){
            if(m*(4*n-4) > n*n) return m;
        }
        else{
            if(m*(4*n-3) > n*n) return m;
        }
    }
    return n;
}

Jako że hetman ustawiony na środku planszy o rozmiarach n$\times$n, bedzie "atakował":
- jeżeli n jest parzyste: 4n-4 (środek w tym wypadku oznacza ustawienie hetmana w jednym z czterech pól znajdujących sie na środku planszy).
- jeżeli n jest nie parzyste: 4n-3

Zatem funkcja startingPoint zwraca taką m, że biorąc pola "atakowane" przez hetmana ustawionego na środku planszy n na n razy m, da się wypełnić planszę n na n,
innymi słowy $\text{startingPoint}(n)*\text{(4*n-4 lub 4*n-3, w zalezności od parzystości n)} > n*n$.

wytłumaczenie:
rozpatrzmy plansze o rozmiarach n, gdzie n jest parzyste:

$$
\begin{matrix}
+ & \_ & + & \_ & + & \_ \\
\_ & + & + & + & \_ & \_ \\
+ & + & H & + & + & + \\
\_ & + & + & + & \_ & \_ \\
+ & \_ & + & \_ & + & \_ \\
\_ & \_ & + & \_ & \_ & + \\
\end{matrix}
$$

załóżmy że hetmana ustawimy w lewym górnym rogu kwadratu 2 $\times$ 2 na srodku planszy.
wtedy od hetmana wychodzą "promienie" atakowanych pól w 8 kierunkach (góra-lewo, góra, góra-prawo, prawo, dół-prawo, dół, dół-lewo, lewo).
promienie idące w dół, dół-prawo i prawo mają długość $\frac n2$, z kolei pozostałe mają długość $\frac n2-1$ i jest ich 5, poza tym jest jeszcze pole na którym stoi hetman.
Daje nam to $3*\frac n2 + 5*(\frac n2-1) + 1 = n + \frac n2 + 2*n + \frac n2 - 5 + 1 = 4*n - 4$
(Jeżeli ustawimy hetmana w innym z 4 środkowych pól to otrzymamy ten sam wynik tylko kierunki w które idą promienie z wiekszą długością będą inne).
w wypadku n - nie parzystego sytuacja jest prostsza ponieważ każdy promień ma długość $\frac{n-1}2$
Mamy zatem $8*\frac{n-1}2 + 1 = 4*n - 4 + 1 = 4*n - 3$

### Funkcja solves
przyjmuje ```int m, int n```, gdzie ```m``` to liczba hetmanów do rozmieszczenia, a ```n``` to rozmiar planszy.

bool solves(int m, int n){
    int solution[n] = {-1};
    for(int i = 0; i < n; i++){
        if(i < m) solution[i] = i;
        else      solution[i] = -1;
    }
    while(true){
        if(attacksAll(solution, n)){
            return true;
        }
        if(!permutate(solution, n)){
            return false;
        }
    }
}

### Funkcja attacksAll

przyjmuje tablice ```solution``` trzynającą pozycje hetmanów położonych na planszy, i ```n``` - rozmiar planszy.
zwraca ``` true ```, jeżeli wszystkie pola na planszy są atakowane,

bool attacksAll(int solution[], int n){
int board[n][n] = {0};
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(board[i][j] != 0) continue;
if(solution[i] == j){
for()
}
}
}
}