N Königinnen, X von Y Board Entscheidungsproblem Interview Frage

Die folgende Frage wurde mir heute in einem Interview gestellt und ich habe seitdem darüber nachgedacht. Ich konnte es nicht beantworten und konnte online keine Lösung finden.

Bestimmen Sie bei einem Schachbrett mit den Dimensionen X x Y und N Königinnen, ob es möglich ist, diese Königinnen so auf dem Brett anzuordnen, dass sie sich nicht gegenseitig angreifen können.

Ein 2 x 3-Board mit 2 Königinnen hat eine Lösung, sodass der Algorithmus true zurückgeben würde:

Q . .
. . Q

Ich suche nach einem Programmieransatz für dieses Rätsel, nicht nur nach Möglichkeiten, es beispielsweise auf Papier zu lösen.

Dies ist aus programmtechnischer Sicht kein (IMO) sehr interessantes Problem. Sie könnten einen rekursiven Algorithmus entwickeln, der jede Anordnung ausprobiert, etwa so:

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)
}

Wenn Sie ein wenig über das Problem nachdenken, werden Sie feststellen, dass es keine Möglichkeit gibt, N Königinnen auf ein Brett zu setzen, auf dem X <N oder Y <N ist, da dies erfordern würde, dass mindestens zwei Königinnen in demselben Rang oder derselben Datei landen. und sie würden sich deshalb gegenseitig angreifen. Wenn Sie über das Problem der n-Königinnen lesen, werden Sie schnell feststellen, dass es immer möglich ist, N-Königinnen für N> 3 auf einer NxN-Tafel zu platzieren. Jetzt wissen wir, dass die Antwort NEIN für (X <N oder Y <N) ist. und JA für (X> = N und Y> = N, N> 3). Übrig bleiben nur die Sonderfälle:

• N = 1 (JA)
• N = 2 (JA für X> = 2 und Y> 2 oder umgekehrt)
• N = 3 (JA für X> = 3 und Y> 3 oder umgekehrt)

Jetzt wird unsere schöne rekursive Funktion zu einer einfachen Funktion, die nur N mit X und Y vergleicht und ein vordefiniertes Ergebnis zurückgibt. Das ist aus Sicht der Leistung großartig, da Sie in konstanter Zeit eine Antwort erhalten können. Aus programmtechnischer Sicht ist es nicht so toll, weil Sie an diesem Punkt erkennen, dass es bei der Frage mehr darum geht, wie gut Sie Rätsel lösen können, als darum, ob Sie eine rekursive Funktion schreiben können.

(Und Junge, Junge, ich hoffe wirklich, dass ich in meiner Smarty-Pants-Antwort keinen dummen Fehler gemacht habe. ;-)

Wenn der Interviewer Sie gebeten hat, den Code für das Problem zu schreiben, dann denke ich, dass es nicht fair ist. Der Algorithmus erfordert Arbeit. Wenn die Idee jedoch darin bestand, dem Interviewer die Klassen, Methoden oder einige Konzepte zu zeigen, die Sie verwenden müssten, oder ähnliches, dann könnte dies eine faire Frage sein.

Das Problem ist ein klassisches Informatikproblem und wird in vielen solchen Büchern diskutiert. Eine ausgezeichnete Erklärung mit Animation und 12 verschiedenen Lösungen zusammen mit etwas Code finden Sie hier:

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

Auch Code finden Sie hier: http://www.codeproject.com/KB/java/EightQueen.aspx

Fühlen Sie sich nicht schlecht dabei, wie gesagt, es ist nicht einfach.

Dies ist eigentlich eher ein Kommentar, aber er passt nicht hinein ...

Ein Schachbrett hat 8x8 Felder, nicht mehr und nicht weniger (diese Fragen nerven mich immer mit dem Ansatz eines maßgeschneiderten Schachbretts).

Aber wie auch immer, wenn Sie ein x * y-Schachbrett und n Königinnen haben und davon ausgehen, dass die Königin diese Felder "nimmt"

Könntest du einfach ein zweidimensionales Array erstellen und alle Felder "markieren", die eine Königin angreift? Platzieren Sie dann das andere (von der Mitte des Bretts aus), markieren Sie die verbleibenden Felder usw., bis Sie entweder Felder oder Königinnen ausführen.

Dies ist natürlich ein sehr vereinfachter Ansatz, da bei einer schlechten Positionierung die maximale Anzahl von Königinnen variieren würde.

Hmm, habe das auch gerade gefunden - 8 Königinnen Problem.

Grundsätzlich funktioniert der Backtrack-Algorithmus folgendermaßen:

1. Erstellen Sie ein X x Y-Array. Setze alle Quadrate auf leer.

2. Setzen Sie die Anzahl der Königinnen auf Null.

3. Stellen Sie Ihre aktuelle Position auf (1,1)

4. Sehen Sie, ob Sie eine Königin an der aktuellen Position platzieren können.

5. Wenn Sie können, setzen Sie Array (X, Y) auf Königin und erhöhen Sie die Anzahl der Königinnen. Wenn Sie alle Königin, platziert Anschlag , haben Sie eine Lösung.

6. Wenn die aktuelle Position nicht (X, Y) ist, erhöhen Sie die aktuelle Position und fahren Sie mit Schritt 4 fort.

7. Finden Sie die Königin an der letzten Position (die letzte in der Reihenfolge, in der Sie die Positionen erhöhen). Stellen Sie die aktuelle Position auf die Position dieser Königin ein, entfernen Sie sie und verringern Sie die Anzahl der Königinnen.

8. Wenn die Anzahl der Königinnen Null ist, hören Sie auf , es gibt keine Lösung.

9. Erhöhen Sie die aktuelle Position.

10. Fahren Sie mit Schritt 4 fort.

Hinzufügen zu den anderen Antworten: Das Erstellen eines zweidimensionalen Arrays verkompliziert nur den Code.

Sie benötigen nur einen Vektor der Größe 8 für ein normales Schachbrett. Oder 8 + 1, wenn wie C 1. Position 0 ist, nur um den Code zu vereinfachen, und behandeln Sie 1-8 und nicht 0-7.

Wenn Sie daran denken, dass x Ihre Position im Array und y der Inhalt der Position ist. zB Brett [1] = 8 bedeutet, dass die erste Königin bei [1,8] ist.

Auf diese Weise müssen Sie nur die Spaltenüberprüfung überprüfen.

Zur Zeit der Fakultät stieß ich auf ein sehr altes Buch (60er Jahre?) Über in Dartmouth BASIC implementierte Algorithmen, das das 8-Queen-Problem mit weniger möglichem Speicher implementierte (da es so alt ist, macht es Sinn).

Soweit ich mich erinnere, wurde die Vektoridee verwendet, und es wurden im Wesentlichen alle Positionen im Board mit zwei FOR-Zyklen brutal erzwungen. Zur Überprüfung der Positionsgültigkeit wurde eine dritte Schleife verwendet, ein WHILE-Zyklus in jeder Position geht zurück in den Vektor und prüft auf eine gleiche Anzahl oder auf eine Formel unter Verwendung einer Tangentenoperation, um nach Diagonalen zu suchen.

Leider habe ich das Buch aus den Augen verloren ...

Dieser Algorithmus fand alle Lösungen für das n-Queen-Problem.

Wenn Sie nur einen Algorithmus schreiben müssen, um festzustellen, ob eine solche Anordnung existiert, dann schauen Sie sich die vorhandene Forschung an:
Acht Königinnen Puzzle auf Wikipedia .

Sie können trivial false zurückgeben, wenn N> min (X, Y).
Nachdem Sie diese Seite gelesen haben, müssen Sie true zurückgeben, wenn N <= min (X, Y) und 2, 3! = Min (X, Y).

Was 2, 3 == min (X, Y) und N <= min (X, Y) lässt.

Wenn N <min (X, Y) ist, ist es trivial, eine Lösung zu finden.
Wenn N == min (X, Y) ist, gibt es nur eine Lösung, wenn max (X, Y)> N ist.

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)

Es gibt offensichtlich keine Lösung, wenn N> min (X, Y). Ansonsten können Sie leicht zeigen, dass es keine Lösung für N = X = Y = 2, N = X = Y = 3 gibt. Für alle anderen Fälle scheint es eine Lösung zu geben. Die Anzahl der Lösungen scheint zu steigen, wenn N wächst.

Sie können eine Lösung durch umfassende Suche mit Rückverfolgung finden: Setzen Sie eine Königin in die erste Reihe, Spalte 1. Setzen Sie eine Königin in die zweite Reihe, in die erste Spalte, die die Königin in Reihe 1 nicht erreichen kann. Setzen Sie eine Königin in die zweite Reihe usw. Wenn eine Königin nicht in Reihe k gesetzt werden kann, entfernen Sie sie und bewegen Sie die Königin in Reihe k-1 in die nächste unbesetzte Position.