8 Damen Problem Algorithmus



  • Hallo,

    erkennt jemand hier einen Fehler. Ich finde ihn naemlich nicht. Ich pruefe ob die Damen waagrecht, senkrecht oder diagonal geschmissen werden kann.

    bool Chess::detectConflicts(char arr[8][2])
    {
    	//waagrecht
    	for(int i = 0 ;i < 8 ;i++)
    	{
    		for(int j = 0 ; j < 8 ;j++)
    		{
                 if((arr[i][1] == arr[j][1]) && (i!=j))
    			 { 
    				 return false;
    			 }
    		}
        }
    
    	//senkrecht
        for(int i = 0 ;i < 8 ;i++)
    	{
    		for(int j = 0 ; j < 8 ;j++)
    		{
                 if((arr[i][0] == arr[j][0]) && (i!=j))
    			 { 
    				 return false;
    			 }
    		}
        }
    
    	//diagonal
        int steigung_x = 0;
    	int steigung_y = 0;
    	int steigung = 0;
    
        for(int i = 0 ;i < 8 ;i++)
    	{
    		for(int j = 0 ; j < 8 ;j++)
    		{  
    			if(i!=j)
    			{
    				steigung_y = arr[i][0] - arr[j][0];
    				steigung_x = arr[i][1] - arr[j][1];
    				if(steigung_x == 0 ) continue;
    				steigung = steigung_y / steigung_x; 
    				if(steigung == 1 || steigung == -1)
    				{ 
    					return false;
    				}
    			}
    		}
        }
    
    	return true;
    }
    


  • hallo.

    ich hatte recht: backtracking.

    blurry333 schrieb:

    geschmissen

    du meinst geschlagen?

    wenn du schon einen namespace Chess hast, dann mach dir auch eine klasse, die ein schach-spielbrett repräsentiert. dann merkst du auch, dass ein schachbrett nicht 8x2 felder gross ist.

    danach ist das ganze relativ simpel:
    -mit backtracking (ruhig echt rekursiv) damen auf den nächsten files (spalten) einfügen
    -prüfen ob die neue dame eine andere dame schlagen kann
    -wenn nicht, dann eine ebene tiefer gehen (sprich, eine neue dame auf einem neuen file)
    -wenn ja, dann soweit zurückgehen mit den ebenen, bis du weiter probieren kannst (die ebenen beim backtracking merken sich natürlich den zustand. wenn auf einem file alle felder ausprobiert wurden, muss man eben noch weiter zurück gehen)

    gruss.

    ps.: ist das der algorithmus, den man dich am vorstellungsgespräch hat implementieren lassen?



  • Zeile 41 ist krank.


  • Mod

    Wie ist meine Implementierung so?

    #include <iostream>
    #include <map>
    #include <cassert>
    
    int main()
    {
    	bool diagonal_dsc[15]{};
    	bool diagonal_asc[15]{};
    	bool row[8]{};
    	bool col[8]{};
    
    	auto set_occupied = [&]( std::size_t x, std::size_t y, bool b )
    	{
    		diagonal_dsc[x + y] = b;
    		diagonal_asc[x + 7 - y] = b;
    		row[y] = col[x] = b;
    	};
    
    	std::map<std::size_t, std::size_t> queens;
    
    	for (std::size_t x = 0; x != 8 ; ++x)
    		for (;;)
    		{
    			std::size_t y = queens[x];
    			if( !diagonal_dsc[x + y]
    			 && !diagonal_asc[x + 7 - y]
    			 && !row[y] && !col[x] )
    			{
    				set_occupied(x, y, true);
    				break;
    			}
    
    			while( ++queens[x] == 8 )
    			{
    				queens[x] = 0;
    				assert( x && "No solution found - impossible" );
    				--x;
    				set_occupied(x, queens[x], false);
    			}
    		}
    
    	for( auto pos : queens )
    		std::cout << pos.first << ' ' << pos.second << '\n';
    }
    


  • zeile 41 ist zwar krank aber ich deck das vorher schon ab weil es dann waagrecht oder senkrecht waere. Es muss ein anderer Fehler sein !!



  • ist die lambda capture so korrekt? kann ich mir kaum vorstellen, dass du lokale kopien verändern willst.



  • blurry333 schrieb:

    Es muss ein anderer Fehler sein !!

    Stichwort: Ganzzahldivision.

    Es reicht übrigens, wenn du j bei i+1 anfangen lässt. Dann machst du nicht mehr jeden Vergleich zweimal und kannst dir die Abfragen auf Gleichheit sparen.



  • Arcoth schrieb:

    assert( x-- && "No solution found - impossible" );
    

    Blöde Idee. das x-- willst du sicherlich immer ausführen, auch dann wenn assertions deaktiviert wurden.


  • Mod

    asfdlol schrieb:

    ist die lambda capture so korrekt?

    Der Zeiger wird kopiert.
    Komisch! Gerade funktionierte es bei mir, darauf verwette ich einen Daumen. Aber richtig, das muss ein & sein.

    kkaw schrieb:

    Blöde Idee.

    Ja, stimmt. Korrigiert.



  • Arcoth schrieb:

    asfdlol schrieb:

    ist die lambda capture so korrekt?

    Der Zeiger wird kopiert.

    ah, hier zerfallen die arrays auch zu zeigern? das wusste ich nicht. danke, wieder was gelernt.

    edit: ja, ich hab das edit gelesen.


  • Mod

    asfdlol schrieb:

    Arcoth schrieb:

    asfdlol schrieb:

    ist die lambda capture so korrekt?

    Der Zeiger wird kopiert.

    ah, hier zerfallen die arrays auch zu zeigern? das wusste ich nicht. danke, wieder was gelernt.

    Nein, ist falsch, siehe Edit.



  • MFK schrieb:

    blurry333 schrieb:

    Es muss ein anderer Fehler sein !!

    Stichwort: Ganzzahldivision.

    Es reicht übrigens, wenn du j bei i+1 anfangen lässt. Dann machst du nicht mehr jeden Vergleich zweimal und kannst dir die Abfragen auf Gleichheit sparen.

    Reicht es schon aus wenn ich steigung zu float mache ?? Hab das versucht aber es geht trotzdem noch nicht.



  • Das reicht offensichtlich nicht.

    Ich würde da gar keine Division machen. Prüf einfach, ob steigung_x und steigung_y dem Betrag nach gleich sind.


Log in to reply