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

10

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.

Rozmówca
źródło
Najlepsze pierwsze wyszukiwanie jest z pewnością opcją, podobnie jak inne heurystyki wyszukiwania
Jason
2
nominowany do jednego z najgorszych pytań w historii wywiadu - chyba że oprogramowanie, na którym pracują, opiera się na rozwiązaniach do cofania, w którym to przypadku jest to całkowicie istotne
Steven A. Lowe
1
Aby być uczciwym, ankieter powiedział, że jest to po prostu dodatkowy rodzaj kredytu. Reszta wywiadu była dość wiarygodna przez IMO. Byłem tylko ciekawy.
Rozmówca
Może to był test, czy wykonałby symulację z cofaniem lub (pomyśl o znalezieniu) rozwiązania O (1), wykorzystując fakty podane przez Caleba w swojej odpowiedzi. Umiejętność programowania prostych rzeczy to nie wszystko, czego potrzeba w pracy.
Sopel
zadania domowe są tutaj wyraźnie poza zakresem.
jwenting

Odpowiedzi:

16

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. ;-)

Caleb
źródło
That's great from a performance point of view, since you can get an answer in constant time. It's not so great from a programming point of view because you realize, at this point, that the question is really more about how well you can solve puzzles than it is about your ability to write a recursive function.Myślę, że ankieter czekał na to rozwiązanie O (1), ponieważ jest ono ostatecznie lepsze i nie jest oczywiste dla wielu osób. Problem królowej nxn występuje we wszystkich kursach programistycznych jako ćwiczenie rekurencyjne - wiele osób nie pomyśli głębiej, widząc ten problem ponownie.
Sopel
4

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.

Bez szans
źródło
0

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

wprowadź opis zdjęcia tutaj

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.

Wieża
źródło
Na początku zaproponowałem ten dokładny algorytm, ale uważam, że nie masz gwarancji, że jeśli podejmiesz takie podejście i nie będziesz mieć miejsc, w których mógłbyś umieścić swoją ostatnią Królową, to naprawdę ustaliłeś, że jest to niemożliwe. Wyeliminowałeś tylko ten konkretny układ. Jest to w zasadzie zastosowanie heurystyki najbliższego sąsiada.
Rozmówca
@Interviewee - Tak, wiem. To jest coś, o czym myślałem z góry. Jak już powiedziano, jest to interesujący problem i prawdopodobnie można go poprawić, ale o 4 rano (tutaj) jestem zbyt leniwy, by myśleć. Przy okazji, jak poszedł wywiad?
Rook
@Interviewee, to dobry pomysł. Brakuje tylko tego, że jeśli odkryjesz, że nie ma miejsca dla ostatniej królowej, cofniesz się i spróbujesz zmienić pozycję dla drugiej do ostatniej królowej. Jeśli nie ma miejsca dla tej królowej, które pozwalałoby na umieszczenie ostatniej królowej, cofasz się o kolejny poziom i wypróbowujesz inne miejsce dla trzeciej do ostatniej królowej i tak dalej.
Caleb
Podoba mi się, że twój awatar jest szachowy :)
warren
0

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.

David Schwartz
źródło
W tym opisie algorytm nie cofa się poprawnie: usuwa tylko ostatnią możliwą do umieszczenia królową; ryzykujesz, że nigdy nie spróbujesz wcześniejszych królowych na innych pozycjach.
Kasper van den Berg,
@KaspervandenBerg Algorytm poprawnie cofa się. Odpowiedziałbym bezpośrednio na twoją krytykę, ale szczerze nie rozumiem tego. Nie wiem, co rozumiesz przez „ostatnią królową do umieszczenia”. To usunie tylko ostatnią umieszczoną królową, ale każda królowa może zostać królową zajmującą ostatnie miejsce, gdy królowe umieszczone po jej usunięciu. Będzie cofać się w miarę potrzeb, usuwając królowe w kolejności odwrotnej do kolejności ich umieszczenia.
David Schwartz,
0

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.

Rui F. Ribeiro
źródło
0

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)
Deduplikator
źródło
0

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ę.

gnasher729
źródło