C++ / Bitmasken

[oli_f]

Habe ein Problem. Vielleicht kann mir ja jemand helfen:

Ich habe ein Schachbrett mit 5x5 Feldern.
Als erstes habe ich mit solchen Konstrukten Steine auf dem Brett das durch ein int dargestellt wird gesetzt:

Code: Alles auswählen

int _board = 0;
_board |= 1 << x * 5 + y;

Ich möchte nun eine Dame auf 2,2 setzen und schauen ob sie einen anderen Stein bedroht:

Code: Alles auswählen

int queen = 0;
queen |= 1 << 2 * 5 + 2;
/* Algoritmus um alle bedroten Bits auf 1 zu setzen*/
if( _board & queen == 0 )
  soSomething();

Nur leider scheint das nicht zu funktionieren.
Und zwar geht wohl schon die oberste Methode um die Bits auf _board zu setzten schief.
Sieht jemand meinen das Problem?

[Joghurt]

Hat "int" bei dir auch 32 Bit? Nimm "long", um sicher zu sein. Das setzen des Bits sieht sonst OK aus.

[oli_f]

hmm ich benutzte sogar long ...

ich poste mal einbisschen mehr, vielleicht hat ja jemand kurz zeit.

Der ganze Code ist unter http://rafb.net/paste/results/jqdH9d98.html zu finden

also es handelt sich um das n-queen problem (auf einem nxn grossen Feld n Damen platzieren so dass sich keine schlagen kann. gesucht anzahl lösungen)

ich speichere zuerst in einem Array für jedes mögliche feld die bedrohten Felder falls dort eine Dame stehen würde (der Algorithmus an sich funktionierte mit Arrays statt Bitmasken) :

Code: Alles auswählen

for ( int x = 0; x < _size; x++ )                                // 1.Dimension des Schachfeldes
           for ( int y  = 0; y < _size;  y++ )                   // 2  "                "     "
           {
                _queensCache[ x*_size+y ] = 0;             // Leeren

                int j = y-x;                                                 // Laufvariable für diagonale Felder
                int k = x+y;                                               // "                     "    "               "
                for ( int i = 0; i < _size; i++ )
                {
                        _queensCache[ x*_size+y ] |= ( 1 << x * _size + i );               // Horizontal         
                                                                                                  bedrohte Felder markieren
                        _queensCache[ x*_size+y ] |= ( 1 << i * _size + y );              // Vertikale

                        if ( j >= 0 && j < _size )
                                _queensCache[ x*_size+y ] |= ( 1 << i * _size + j );         // Diagonale
                        if ( k >= 0 && k < _size )
                                _queensCache[ x*_size+y ] |= ( 1 << i * _size + k );        // Diagonale

                        j++;
                        k--;
                }
           }

Danach führe ich eine Backtrack Funktion aus:

Code: Alles auswählen

   if( number == _size-1 )        //Schauen ob schon alle Damen gesetzt wurden
   {
      _solutions++;
      return;
   }

   for( int i = 0; i < _size; i++ ) 
   {
      if( _board & _queensCache[ number*_size+i ] == 0  )    // Die Spalte bleibt immer die
                                                                  selbe, nämlich die Anzahl der bereits gesetzten
                                                                  Damen, da in jede Spalte eine Dame kommt. Die 
                                                                  Zeilen werden der Reihe nach durchgetestet mit
                                                                  einer AND Verknüpfung der Bedrohten Felder 
                                                                  mit dem aktuellen _board.
       {
              _board |= ( 1 << number * _size + i );   // Die dame setzen
              solve( number+1 );                               // nächste Suchtiefe
              _board ^= ( 1 << number * _size + i );  // Dame entfernen = Backtrack
       }
   }

[jack herer]

Ich verstehe Dein Programm zwar momentan nicht, aber in dein if muß wohl noch ne Klammer, da & eine höhere Priorität hat als ==.

Code: Alles auswählen

if( ( _board & _queensCache[ number*_size+i ] ) == 0  )

]

[oli_f]

genau habs gerade vorhin entdeckt und jetzt funktioniert's!

merci trozdem!

jetzt muss ich mir nur noch überlegen wie ichs bei grösseren brettern mache denn 32 bit reichen leider nur für 5x5 Felder!

[Joghurt]

Für 8x8 könntest du GCC's long long nehmen.

[gms]

mit bitset kommst du länger aus
http://www.sgi.com/tech/stl/bitset.html

[oli_f]

ja soweit war ich schon nur leider ist es mir nicht gelungen ein bitset-array zu erstellen!
ich denke das hängt damit zusammen, dass der [] Operator schon zum Auslesen von einem einzelnen Bit benutzt wird!
Wenn ich davon ein Array machen könte wäre es genial!

[gms]

funktioniert ähnlich wie in deinem Beispiel:

Code: Alles auswählen

#define BOARDSIZE 100
std::bitset<BOARDSIZE*BOARDSIZE> mybitset();

mybitset.set(x*BOARDSIZE+y);

[edit]
std::bitset<BOARDSIZE> mybitset();
gändert auf:
std::bitset<BOARDSIZE*BOARDSIZE> mybitset();
[/edit]

[oli_f]

ich wollte eigentlich sagen dass ich BOARDSIZE * BOARDSIZE bitsets der grösse BOARDSIZE*BOARDSIZE brauche, da ich ja am anfang für jedes feld die jeweils bedrohten Felden cachen will.

also habe ich das so probiert:

Code: Alles auswählen

const int _size = 6;

bitset<_size*_size> _queensCache[_size*_size];

aber das gibt einen Fehler beim compillieren!

[gms]

kompiliert bei mir fehlerfrei:

Code: Alles auswählen

#include <bitset>

int main() {
  const int _size=6;
  std::bitset<_size*_size> _queenscache[_size*_size];

  return 0;
}

[oli_f]

merci für deine geduld

ich hatte das #include <bitset> vergessen da ich irgendwie gedacht habe: ah es ist ja in der standard library und die habe ich ja schon drinn .....

jedenfalls geht das programm jetzt aber es ist immer noch etwa gleich lahm
werd's dann später einmal weiterschreiben.

[Joghurt]

jedenfalls geht das programm jetzt aber es ist immer noch etwa gleich lahm
werd's dann später einmal weiterschreiben.

Denk dran, dass du die erste Dame nur im oberen linken Quadranten platzierst, dann braucht du die rotierten Lösungen nicht einzeln rausfiltern.

[oli_f]

genau so handhabe ich es mitlerweile....

aber das problem ist wohl, dass ich immer das ganze board mit der gesammten gecachten Damenbedrohungsliste (<- tolles Wort) bitwise AND verknüpfe. eigentlich müsste ich nur die zu setzende Position in den Damenbedrohungslisten der bereits gesetzten Damen zu testen.
Das gäbe ne Menge einsparungen...

[Dookie]

Hi oli_f,

am einfachsten legst du ein bitfeld an, in dem du alle bedrohten damenfelder der gesetzten damen oderst, dann brauchst du nur das eine Bitfeld mit dem Bitfeld der neuen Dame anden.


Gruß

Dookie

[oli_f]

nur gibt's da ein problem:
beim backtracking weiss ich nicht ob ein feld einfach oder mehrfach bedroht ist. ich kann also nicht wissen ob ich ein von der dame die ich wieder wegnehme bedrohtes Feld auch wirklich nachher nicht mehr bedroht ist!

So oder so C++ macht mir gerade ziemlich freude

[oli_f]

hopla ganz neue Situation:

habe irgendwo per zufall gelesen man solle g++ mit dem flag -O3 aufrufen und schau an so kompilliert läuft das Program bestimmt 10x schneller!!!
Nur verstehe ich das ganze nicht! anscheinend soll dieses Flag den Kompiler dazu anhalten kleine Funktionen automatisch als inline zu behandeln. Nur habe ich in meiner solve Funktion nur einen Funktionsaufruf, nämlich ruft sie sich selber auf wenn eine neue Dame platziert werden soll. Aber diese Funktion ist nicht wirklich klein und ausserdem wird sie ja dauernd rekursiv von sich selber aufgerufen?? Verwirrt...

[Joghurt]

habe irgendwo per zufall gelesen man solle g++ mit dem flag -O3 aufrufen und schau an so kompilliert läuft das Program bestimmt 10x schneller!!!

-O3 schaltet ein Menge optimierungen ein.
Du kannst auch noch -march=pentium4 (z.B.) angeben, dann wird auch speziell für diesen Prozessor kompiliert/optimiert.

Was optimiert wird, kannst du in der info-Page nachlesen.
Online hier: http://gcc.gnu.org/onlinedocs/gcc-3.4.3 ... ze-Options

[BeS]

Hallo,
warum machst du das überhaupt so umständlich?
Es reicht doch wenn du einen normalen array mit der größe einer Seitenlänge des Schachbretts nimmst, da schreibst du dann als int Wert rein an welcher Stelle der Zeile/Spalte (eines von beiden repräsentiert dein 1-dim-array) die Dame steht. Auf diese Weise kannst du durch eine einfache Formel auch überprüfen ob eine Dame in den vorherigen Feldern dich schon bedroht. Zusammen mit einem sauberen backtracking kannst du dann einfach alle Kombinationen durchspielen.

Ich habe das ganze vor einiger Zeit mal in C geschrieben, wenn es dich genauer interessiert, dann kannst du es dir auf meiner Homepage ansehen.