N królowe, X przez Y problem z decyzją zarządu pytanie wywiad wywiad

W dzisiejszym wywiadzie zadano mi następujące pytanie i odtąd o tym myślę. Nie byłem w stanie odpowiedzieć na to pytanie i nie byłem w stanie znaleźć rozwiązania online.

Biorąc pod uwagę szachownicę o wymiarach X według królowych Y i N, ustal, czy możliwe jest ułożenie tych królowych na planszy tak, aby nie mogły się nawzajem atakować.

Płyta 2 x 3 z 2 królowymi ma rozwiązanie, więc algorytm zwróciłby prawdę:

Q . .
. . Q

Szukam podejścia programowego do tej układanki, a nie tylko na przykład rozwiązania na papierze.

To nie jest (IMO) bardzo interesujący problem z punktu widzenia programowania. Możesz wymyślić algorytm rekurencyjny, który wypróbuje każde ustawienie, coś takiego:

bool try_queens(Board board, int n)
{
    if (n == 0) {
        // no queens left to place, so we're done
        return true
    }
    // try each open position until we find one that works
    for each position on the board {
        if (is_empty(board, position) and not is_attacked(board, position)) {
            place_queen(board, position)
            if (try_queens(board, n-1)) {
                return true
            }
            remove_queen(board, position)
        }
    }
    // if we get this far, there's no available position
    return false
}

main()
{
    initialize board(X,Y)
    return try_queens(board, N)
}

Jeśli zastanowisz się trochę nad tym problemem, zdasz sobie sprawę, że nie ma sposobu, aby dopasować N królowych na planszy, gdzie X <N lub Y <N, ponieważ wymagałoby to, aby co najmniej dwie królowe znalazły się w tym samym rankingu lub pliku, i dlatego atakują się nawzajem. Jeśli przeczytasz o problemie n-królowych, szybko dowiesz się, że zawsze można umieścić N królowych na tablicy NxN dla N> 3. Teraz wiemy, że odpowiedź brzmi NIE dla (X <N lub Y <N) i TAK dla (X> = N i Y> = N, N> 3). Pozostały tylko specjalne przypadki:

• N = 1 (TAK)
• N = 2 (TAK dla X> = 2 i Y> 2 lub odwrotnie)
• N = 3 (TAK dla X> = 3 i Y> 3 lub odwrotnie)

Więc teraz nasza ładna funkcja rekurencyjna staje się prostą funkcją, która po prostu porównuje N z X i Y i zwraca wynik standardowy. To świetne z punktu widzenia wydajności, ponieważ możesz uzyskać odpowiedź w stałym czasie. Z punktu widzenia programowania nie jest to takie wspaniałe, ponieważ zdajesz sobie sprawę, że w tym momencie chodzi o to, jak dobrze rozwiązywać zagadki, niż o umiejętność pisania funkcji rekurencyjnej.

(A chłopcze, och chłopcze, naprawdę mam nadzieję, że nie popełniłem głupiego błędu w odpowiedzi na smarty-spodnie. ;-)

Jeśli ankieter poprosił cię o napisanie kodu problemu, myślę, że to niesprawiedliwe. Algorytm wymaga pracy. Jeśli jednak chodziło o pokazanie ankieterowi klas, metod lub niektórych pojęć, których należy użyć lub czegoś podobnego, może to być uczciwe pytanie.

Problem jest klasycznym problemem informatycznym i jest omawiany w wielu takich książkach. Doskonałe wyjaśnienie, z animacją i 12 różnymi rozwiązaniami wraz z pewnym kodem można znaleźć tutaj:

http://en.wikipedia.org/wiki/Eight_queens_puzzle

Również kod można znaleźć tutaj: http://www.codeproject.com/KB/java/EightQueen.aspx

Nie przejmuj się tym, jak powiedziałem, nie jest to łatwe.

To naprawdę jest komentarz, ale nie pasuje ...

Szachownica ma kwadraty 8x8, nie mniej więcej (te pytania zawsze mnie denerwują podejściem do niestandardowej szachownicy).

Ale tak czy inaczej, jeśli masz szachownicę x * y, n królowe i biorąc pod uwagę, że królowa „bierze” te pola

czy możesz po prostu stworzyć dwuwymiarową tablicę i „oznaczyć” wszystkie pola atakowane przez jedną królową. Następnie umieść drugie (ze środka planszy), oflaguj pozostałe pola i tak dalej ... aż uruchomisz jedno z pól lub królowych.

Jest to oczywiście bardzo uproszczone podejście, ponieważ przy złym ustawieniu, uznaję, że maksymalna liczba królowych byłaby różna.

Hmm, właśnie to znalazłem - problem 8 królowych.

Zasadniczo algorytm cofania działa w następujący sposób:

1. Utwórz tablicę X według Y. Ustaw wszystkie kwadraty na puste.

2. Ustaw liczbę królowej na zero.

3. Ustaw swoją bieżącą pozycję na (1,1)

4. Sprawdź, czy umieścisz królową na aktualnej pozycji.

5. Jeśli możesz, ustaw Array (X, Y) na queen, zwiększ liczbę królów. Jeśli umieściłeś całą królową, przestań , masz rozwiązanie.

6. Jeśli bieżąca pozycja nie jest (X, Y), zwiększ aktualną pozycję i przejdź do kroku 4.

7. Znajdź królową na ostatniej pozycji (tej, która jest ostatnia w kolejności, w której zwiększasz pozycje). Ustaw bieżącą pozycję na pozycję tej królowej, usuń ją i zmniejsz liczbę królów.

8. Jeśli liczba królowych wynosi zero, przestań , nie ma rozwiązania.

9. Zwiększ bieżącą pozycję.

10. Przejdź do kroku 4.

Dodanie do innych odpowiedzi: utworzenie dwuwymiarowej tablicy tylko komplikuje kod.

Potrzebujesz zwykłego wektora o rozmiarze 8 do zwykłej szachownicy. Lub 8 + 1, jeśli podobnie jak C 1. pozycja wynosi 0, tylko w celu uproszczenia kodu i radzenia sobie z 1-8, a nie 0-7.

Jeśli myślisz, że x jest twoją pozycją w tablicy, ay jest treścią pozycji. np. tablica [1] = 8 oznacza, że ​​pierwsza królowa jest w [1,8].

W ten sposób wystarczy sprawdzić poprawność kolumn.

Na wydziale natknąłem się na bardzo starą książkę (lata 60.?), Dotyczącą algorytmów zaimplementowanych w Dartmouth BASIC, która implementowała problem 8 królowych przy użyciu mniejszej możliwej pamięci (jest tak stara, że ​​ma sens).

O ile pamiętam, wykorzystał pomysł wektorowy i zasadniczo brutalnie zmusił wszystkie pozycje na planszy za pomocą dwóch cykli FOR. Aby sprawdzić ważność pozycji, wykorzystano trzecią pętlę, cykl WHILE w każdej pozycji wraca do wektora i sprawdza, czy jest równa liczba, lub formułę używającą operacji stycznej do sprawdzenia przekątnych.

Niestety zgubiłem tę książkę ...

Wspomniany algorytm znalazł wszystkie rozwiązania problemu n-królowej.

Jeśli po prostu musisz napisać algorytm, aby ustalić, czy taki układ istnieje, spójrz na istniejące badania:
Układanka Osiem królowych na Wikipedii .

Możesz trywialnie zwrócić false, jeśli N> min (X, Y).
Po przeczytaniu tej strony wiadomo, że należy zwrócić wartość true, jeśli N <= min (X, Y) i 2, 3! = Min (X, Y).

Który pozostawia 2, 3 == min (X, Y) i N <= min (X, Y).

Cóż, jeśli N <min (X, Y), znalezienie rozwiązania jest banalne.
Jeśli N == min (X, Y), istnieje rozwiązanie tylko wtedy, gdy max (X, Y)> N.

f(X, Y, N)
    if X < Y => f(Y, X, N)
    if Y > N => false
    => (Y < N) or (Y != 2 and Y != 3) or (X > N)

Oczywiście nie ma rozwiązania, jeśli N> min (X, Y). W przeciwnym razie możesz łatwo pokazać, że nie ma rozwiązania dla N = X = Y = 2, N = X = Y = 3. Dla wszystkich innych przypadków wydaje się, że istnieje rozwiązanie. Liczba rozwiązań wydaje się rosnąć wraz ze wzrostem N.

Możesz znaleźć rozwiązanie poprzez wyczerpujące wyszukiwanie z cofaniem się: Umieść królową w pierwszym rzędzie, kolumnie 1. Umieść królową w drugim rzędzie, w pierwszej kolumnie, do której królowa w rzędzie 1 nie może dotrzeć. Umieść królową w drugim rzędzie itp. Jeśli królowej nie można umieścić w rzędzie k, usuń ją i przenieś królową w rzędzie k-1 na następną niezajętą ​​pozycję.