N * N Queen-Algorithmus

  • Ich habe nur mit N-Queen-Problemen herumgespielt, was bedeutet, N Königinnen auf N * N Chees Board unterzubringen, so dass sich niemand gegenseitig töten kann. Ich habe einen einfachen Algorithmus ausprobiert, der Backtracking verwendet. Das Programm funktioniert einwandfrei bis 29 Damen, aber nach 29 läuft es einfach weiter und weiter über 29 * 29 erledigt werden.

    Ich füge meinen Code hier ein. Es ist eine Win32-Konsole-Anwendung. Wenn mir jemand einen Logikfehler oder eine Möglichkeit zur Optimierung mitteilen kann ... Das wäre für mich hilfreich.

    Code ..

         // Queen_Game.cpp : Defines the entry point for the console application.
        #include <iostream>
        using namespace std;
        class chess_block
        {
        public:
            bool bQueen;
            chess_block()
            {
                bQueen=false;
            }
        };
        bool IsSafeToPutQueen(int nRow, int nCol,chess_block **Chess_Board,int n )
        {
            // We need to check for three directions upper left diagonal, lower left diagonal, and left horizontally;
            int nTempColLeft=nCol-1; int nTempBelowRow=nRow+1;int nTempAboveRow=nRow-1;
            bool bSafe=true;
            //
            while(nTempColLeft>=0 || nTempBelowRow<n || nTempAboveRow>=0)
            {
                if( ((nTempAboveRow>=0)&&(nTempColLeft>=0)&&(Chess_Board[nTempAboveRow][nTempColLeft].bQueen==true))    /*Left Upper Diagonal*/
                    ||((nTempBelowRow<n)&&(nTempColLeft>=0)&&(Chess_Board[nTempBelowRow][nTempColLeft].bQueen==true))/*Left Lower Diagonal*/
                    ||((nTempColLeft>=0)&&(Chess_Board[nRow][nTempColLeft].bQueen==true)))      /*Left Block*/
                {
    
                    bSafe=false;
                    break;
    
                }
                else
                {
    
                    nTempColLeft--;
                    nTempAboveRow--;
                    nTempBelowRow++;
                }
            }
            return bSafe;
        }
    
        chess_block **PrepareTheChessBoard(int n)//Allocate memory for n*n blocks
        {
            //chess_block **Chess_Board= (chess_block **)malloc(n*sizeof(chess_block *));
    
            chess_block **Chess_Board= new chess_block *[n];
    
            for(int i=0;i<n;i++)
            {
    
                Chess_Board[i]=new chess_block[n];
    
            }
            for(int nColumn=0;nColumn<n;nColumn++)
            {
                for(int nRow=0;nRow<n; nRow++)
                {
    
                    Chess_Board[nRow][nColumn].bQueen=false;
                }
            }
            return Chess_Board;
        }
        void DestroyTheChessBoard(chess_block **Chess_Board,int n)
        {
            for(int i=0;i<n;i++)
            {
                delete [](Chess_Board[i]);
    
            }
            delete [](Chess_Board);
        }
    
        void PrintPositionsOfQueens(chess_block **Chess_Board,int n)
        {
    
            for(int nColumn=0;nColumn<n;nColumn++)
            {
                for(int nRow=0;nRow<n; nRow++)
                {
                    if(Chess_Board[nRow][nColumn].bQueen==true)//Put The Queen Here
                    {
    
                        cout<<"Column No.:   "<<nColumn   <<"               "<<"Row Number:   "<<nRow<<"\n";
                    }
    
                }
            }    
    
        }
        void ArrangeQueensOnBoard(chess_block **Chess_Board,int n)
        {
            bool bBackTrack=false;
            int nRow=0;
            for(int nColumn=0;nColumn<n;nColumn++)
            {
                for(nRow=0;nRow<n; nRow++)
                {
    
                    if(IsSafeToPutQueen(nRow,nColumn,Chess_Board,n))
                    {
                        if(bBackTrack && Chess_Board[nRow][nColumn].bQueen==true)
                        {
                            Chess_Board[nRow][nColumn].bQueen=false;
                            bBackTrack=false;
                            continue;
                        }
                        else if(!bBackTrack)
                        {
                            Chess_Board[nRow][nColumn].bQueen=true;
                            break;//Now Move to Next Col
                        }
                    }
                }
                if(nRow ==n && Chess_Board[n-1][nColumn].bQueen==false)//means we need to backtrack
                {
                    nColumn--;
                    if(nColumn<0)
                    {
                        cout<<"THis combination can't place the queen ";
                        break;
                    }
                    nColumn--;
                    bBackTrack=true;
                }
    
            }
    
        }
        int _tmain(int argc, _TCHAR* argv[])
        {
            while(1)//Don't be offended for this while loop it is only for keeping the command prompt window on the screen always
            {
                int n=0;
                cout<<"Enter the value of N"<<"\n";
                cin>>n;
                chess_block **Chess_Board=NULL;
                Chess_Board=PrepareTheChessBoard(n);
                if(Chess_Board == NULL)
                {
                    return 0;
    
                }
                ArrangeQueensOnBoard(Chess_Board,n);
                PrintPositionsOfQueens(Chess_Board,n);
                DestroyTheChessBoard(Chess_Board,n);
                Chess_Board=NULL;
            } 
    
            return 0;
        }
     
    10 December 2011
    qubytewaspinator
6 answers
  • Sie haben nicht lange genug gewartet. Der Code funktioniert.

    Ihr Programmierstil orientiert sich stark an "C". Sie sollten sich ein gutes Buch über C ++ durcharbeiten. Aber selbst wenn Sie dies nicht tun, können Sie vieles tun, um es sogar im Stil zu verbessern, wie es geschrieben wurde.

    • Idiomatisch sollten Sie boolesche Variablen nicht gegen wahr und falsch testen. Es ist legal und die Existenz eines nativen booleschen Typs bedeutet, dass es nicht gefährlich ist wie in C . Aber anstelle von if (condition == true) können Sie einfach if (condition) sagen, und anstelle von if (condition == false) können Sie if (!condition) oder if (not condition) sagen. Das Schlüsselwort "not" steht nur in C ++ und ist weniger häufig zu finden, es gibt jedoch andere verbale Begriffe wie "und" anstelle von & amp; & amp; ... sowie "oder" anstelle von || Von Anfang an. Sie sind Standard und ich finde sie angenehmer und einfacher zu sehen, wenn ich Code in einer proportionalen Schriftart bearbeite. Wenn Sie bool und true / false verwenden, haben Sie bereits ein C ++ - Buy-In. Warum verwenden Sie sie nicht?

    • Ungarische Notation-Präfixe sind schrecklich missverstanden. Ihre ordnungsgemäße Verwendung hängt von der Erstellung neuer abstrakter Typen ab ... keine robotergestützte Codierung der Low-Level-Implementierungstypen . Anstelle von int nRowMax; int nColumnFirst; würden Sie also etwas wie typedef int Row; typedef int Column; und sagen und deklarieren Row rowMax; Column columnFirst;, ob Sie das stilted verglichen mit "maxRow" und "firstColumn" oder kurzen Variablennamen wie "r" und "" finden "c" ist eine Frage der persönlichen Präferenz ... und Sie können den ganzen Tag mit Menschen darüber diskutieren. NO ONE sollte jedoch vor jeder einzelnen Integer-Variablen n setzen, es ist dumm und war zu Beginn noch nicht einmal richtig Ungarisch.

    (Anmerkung: Ich bevorzuge Dinge wie rowMax bis maxRow. Wenn ich mich in einer Routine mit einer einzelnen Row-Variablen befinde, kann ich damit anfangen, sie einfach "row" zu nennen, und dann mache ich mir nur die Mühe es gibt differenzierende Suffixe basierend aufEs ist vom Kontext benötigt. Dieser Prozess ist eine einfachere Transformation: Angenommen, ich beginne mit Row row und dann funktioniert das eine Weile, bis mir klar wird, dass ich eine "entfernte" und eine "lokale" Zeile brauche. Ich packe einfach "Local" an und bekomme rowLocal und muss es nicht wie localRow zurückholen. Etwas über "Rowness" zu sagen, gefällt mir auch ästhetisch ... ich mag es, wie ich es vorziehen würde, wie die Substantive vor den Adjektiven stehen.)

    • Vermeiden Sie es gemäß dem vorherigen Punkt, Boolean-Variablen mit b vorzustellen. Was ich gerne tun möchte, ist, dass boolesche Variablen mit Stämmen beginnen, wie "hat", "ist", "war", "sollte" usw. Dies führt zu einer englischen Lesbarkeit der bedingten Logik, wie if (shouldDeleteFile) { ... }, denke ich Die Qt-API-Richtlinien enthalten einige interessante Philosophien zu diesem und anderen Punkten: http: //doc.qt. nokia.com/qq/qq13-apis.html#theartofnaming

    • Sie hatten einen Konstruktor für Ihre chess_block, wodurch bQueen auf false gesetzt wurde . Ihr Code musste jedoch noch die von Ihnen dynamisch zugewiesenen Arrays durchlaufen, um bQueen auf false zu setzen. Das ist nur einer der vielen Gründe, new und delete in C ++ (und deren Array-Formen new[] und delete[]) zu verwenden.

    • Don Verschleiern Sie nicht Ihre Algorithmen. Zum Beispiel haben Sie eine for-Schleife verwendet, die einen Zähler immer inkrementiert und dann versucht, den Effekt des kommenden Inkrements durch Subtraktion "rückgängig zu machen". Es gibt andere Arten von Schleifen ... während und / oder. Wenn Sie den Zähler nicht immer inkrementieren möchten (und manchmal von ihm subtrahieren möchten), machen Sie diese Logik klarer, indem Sie den Inkrementierungsteil herausfiltern.

    • Wenn Sie Code auf StackOverflow buchen, versuchen Sie, den Code so einzustellen, dass keine horizontale Bildlaufleiste angezeigt wird. Es ist wirklich frustrierend, im Web zu lesen. Wenn möglich, isolieren Sie Ihr Problem auf Proben, die ohne passen können

    10 December 2011
    tfinniga
  • Ihr zweiter for(int nColumn... dekrementiert nColumn innerhalb der Schleife. Das eröffnet Ihnen unendlich viele Loops. Wenn Sie die Board-Positionen ausdrucken, die in dieser Schleife ausprobiert werden, sollten Sie die Wiederholung sehen und von dort aus herausfinden können.

    10 December 2011
    Jason
  • Ich habe kommentiert, aber hier sind meine Beobachtungen zu Ihrem Code:

    Es ist effizienter, das Board als ein Array von N Ints darzustellen, wo B [i] ist die Position der Königin in der i'ten Spalte. Dies schließt natürlich den Fall aus, in dem sich zwei Königinnen in derselben Spalte befinden.

    Backtracking wird am besten mit einem rekursiven Algorithmus durchgeführt, andernfalls müssen Sie Ihren eigenen Stack für die Aufzeichnung der Suche codieren history.

    Schlechte Schreibweise und riesige Funktionen machen es anderen schwer, Ihren Code zu verstehen. Vielleicht machen sie es Ihnen auch schwerer, zu debuggen? Bei kleineren Funktionen können Sie auch Teile Ihres Codes einzeln testen, wenn Sie den Verdacht haben, dass etwas beschädigt ist.

    Halten Sie sich an Features von C oder C ++ und versuchen Sie, die beiden (malloc from C, Strukturkonstruktoren, Bool-Typ und Cin / Cout von C ++). Vermeiden Sie Windows-spezifischen Code, wenn dies nicht unbedingt erforderlich ist, und halten Sie sich stattdessen an Standard-C oder C ++ (_tmain, stdafx).

    10 December 2011
    Paul Hankin
  • Ich bin nicht sicher, wonach Sie suchen, aber es gibt eine explizite Lösung für das n-Queens-Problem :) Es liegt an einem Papier, das ich scheinbar nicht mehr finde.

    Wie auch immer, hier ist eine Implementierung der expliziten Lösung. Sie gibt eine Liste ganzer Zahlen zurück, die die Positionen der Damen darstellen (eine in jeder Zeile):

     std::vector<int> solve(int n) {
        std::vector<int> result;
        if (n == 1) {
            result.push_back(1);
            return result;
        }
        if (n < 4) {
            // Impossible, return empty vector.
            return result;
        }
    
        if (n % 2 == 0) {
            // Explicit solution according to paper.
            if (n % 6 == 2) {
                for (int j = 1; j <= n/2; j++) {
                    result.push_back(1 + ((2 * (j-1) + n/2 - 1) % n));
                }
                for (int j = n/2; j > 0; j--) {
                    result.push_back(n - ((2*(j-1) + n/2 - 1) % n));
                }
            }
            else {
                for (int j = 1; j <= n/2; j++) {
                    result.push_back(2 * j);
                }
                for (int j = 1; j <= n/2; j++) {
                    result.push_back(2 * j - 1);
                }
            }
        }
        else {
            // If odd, place in corner and solve even.
            result = solve(n - 1);
            result.push_back(n);
        }
    
        return result;  
    }
     
    10 December 2011
    Dino
  • Ich kann Ihr Programm bestätigen DO 30 Jahre lang arbeiten, aber nehmen Sie viel Zeit in Anspruch. Bitte warten Sie die Ergebnisse ab. (Ich habe die Gültigkeit des Ergebnisses nicht geprüft.)

    Die Komplexität dieser Art von Algorithmus ist exponentiell (oder möglicherweise zu exponentiell). Das bedeutet, dass der Zeitaufwand die Toleranz des Benutzers leicht erreichen würde.

    Neben den Vorschlägen anderer Benutzer sollten Sie in C ++ statt new anstelle von malloc das wird den Konstruktor aufrufen. Und Sie können std::vector anstelle eines unformatierten Zeigers verwenden.

    Übrigens: E / A-Druck wie auf dem Bildschirm kostet viel Zeit (viel mehr) als Ihren echten Algorithmus in Ihrem Code). Drucken Sie nicht so oft, auch wenn Sie debuggen.

    10 December 2011
    nohillsideDanny Miller
  • N Queens hat eine deterministische Lösung für O (n), die 1969 in einer Ausgabe des Mathematics Magazine von Hoffman, Loessi und Moore veröffentlicht wurde. Hier ist ein Link zu einem Applet (www.apl.jhu.edu/~hall/java/NQueens.java), das eine spätere Version des gleichen Ansatzes implementiert. Im Jahr 2001 hatte ich einen Schüler in einer meiner Klassen, der das 10.000.000-Queens-Problem in etwa einer Minute auf einem PC dieser Zeit (300 MHz Pentium II) gelöst hatte
    12 December 2011
    Richard Povinelli