[C] 8 Koninginnen probleem

[lamain]

Beste Tweakers,

Voor een schoolopdracht moeten we het 8 koninginnen probleem oplossen, we zijn beginnend c programmeurs, dus het bevatten van diagonaal door een 2d array gaan is lastig.

Voor de oplossing moet er diagonaal gecheckt worden of er niet meer dan 2 koninginnen in 1 rij staan. Dit is ons gelukt, maar we hebben het gevoel dat de code onnodig lang is. De code wordt namelijk 1.2 miljoen keer aangeroepen en snelheid is dus gewenst.

Elke keer als we bij de test lus aankomen voor een geldige plaatsing hebben we dus een 8x8 array bord[i][j]. Deze is gevuld met 0 voor de lege plekken en een 1 voor de koningin (8 totaal dus).
Size = 8

C:

    
      for(n=0; n<SIZE; n++){
        for(i=n, j=0; i<SIZE, j<SIZE-n; i++,j++){
            buffer = buffer + bord[i][j];
            buffer2 = buffer2 + bord[j][i]; 
        }
        if(buffer > 1)
            return 0;
        if(buffer2 > 1)
            return 0;
        buffer = 0;
        buffer2 = 0;
    }

Hier tellen we diagonaal van linksboven naar rechtsonder. Alle vakjes van elke rij worden opgeteld in een buffer en daarna wordt er gekeken of het totaal groter dan 1 is, vervolgens wordt het buffer 0 en wordt de volgende rij bekeken.

C:

    
        for(n=0; n<SIZE; n++){
        for(i=0, j = SIZE-1-n; i<SIZE-n,j>-1; i++,j--){
            buffer = buffer + bord[j][i];
        }
        if(buffer > 1)
            return 0;
        buffer = 0;
    }
    for(n=0; n<SIZE; n++){
        for(i=n, j=SIZE-1; i<SIZE, j>=n; i++, j--){
                buffer = buffer + bord[j][i];
        }
        if(buffer > 1){
            return 0;
        }
        buffer = 0;
    }
    return 1;
}
 

Hier wordt het array gecheckt van rechtsboven naar linksonder. We konden geen verband vinden tussen het boven deel en het onder deel (dus array[i][j] array[j][i] maken werkt niet) dus hebben we 2 keer een geneste for gebruikt voor beide delen.

Onze vraag is dus, kunnen we de diagonale (rechtboven naar linksonder) code combineren? En is het mogelijk om het totaal nog compacter te krijgen?

Met vriendelijke groeten,

Peter(lamain) en Chris(Chris_NL)

[ZpAz]

Als je een twee d array hebt kan je vanuit een willekeurige positie bepalen wat de aanliggende posities zijn.

Iemand op x,y 5,5 heeft rechts als buurman 6,5 en links als buurman 4,5. Schuin rechts boven hem staat 6,6 en schuin links onder hem staat 4,4. Dit geld voor elke positie (behalve de randen) dus voor x en/of y of een waarde met 1 ophogen of een waarde met 1 verlagen.

Vanuit daar kan je met een aantal ifjes kijken of er twee koninginnen naast elkaar staan, en in een loopje doe je dit dan voor elke positie.

[Lone Gunman]

is het gebruiken van een 2d array een vereiste? anders zou je misschien gebruik kunnen maken van een array van 8 bytes, waarbij iedere bit aangeeft of de positie bezet is of niet. Een rij controleren is dan kijken of er meer dan 1 bit geset is (kan op verschillende manieren), een kolom controleren kan bv met een loop + bitmask en diagonalen met een loop en een bitmask dat je shift. Als je het slim aanpakt kan je denk ik zelfs meerdere kolommen of diagonalen tegelijk controleren.

[ Voor 11% gewijzigd door Lone Gunman op 23-10-2013 20:08 ]

[pedorus]

Een 8x8 int array is niet bepaald een handige representatie voor dit probleem. Tegenwoordig kun je algoritmes vaak het snelst krijgen door zo min mogelijk geheugen te gebruiken, of het geheugen zo handig mogelijk aan te spreken. 8x8 is toevallig precies 64 bit, wat schitterend in een long long past. Van te voren kun je berekenen op welke plaatsen niet al iets mag staan, wil je succesvol een koningin op positie x kunnen zetten zonder overlap te veroorzaken. Die positie testen is een simpele AND-operatie. Hiermee kun je denk ik binnen 100ms alle 92 oplossingen berekenen op een moderne processor.

Googelen geeft hetzelfde idee, zie bijv.:
http://www.jsomers.com/nqueen_demo/nqueens.html
http://georgovassilis.blo...eens-puzzle-with-bit.html
http://www.cl.cam.ac.uk/~mr10/backtrk.pdf
http://rosettacode.org/wiki/N-queens_problem#C

[Chris_NL]

ZpAz schreef op woensdag 23 oktober 2013 @ 19:08:
Als je een twee d array hebt kan je vanuit een willekeurige positie bepalen wat de aanliggende posities zijn.

Iemand op x,y 5,5 heeft rechts als buurman 6,5 en links als buurman 4,5. Schuin rechts boven hem staat 6,6 en schuin links onder hem staat 4,4. Dit geld voor elke positie (behalve de randen) dus voor x en/of y of een waarde met 1 ophogen of een waarde met 1 verlagen.

Vanuit daar kan je met een aantal ifjes kijken of er twee koninginnen naast elkaar staan, en in een loopje doe je dit dan voor elke positie.

Bedankt voor je reactie. We zullen even kijken of we hier iets mee kunnen.

Lone Gunman schreef op woensdag 23 oktober 2013 @ 20:01:
is het gebruiken van een 2d array een vereiste? anders zou je misschien gebruik kunnen maken van een array van 8 bytes, waarbij iedere bit aangeeft of de positie bezet is of niet. Een rij controleren is dan kijken of er meer dan 1 bit geset is (kan op verschillende manieren), een kolom controleren kan bv met een loop + bitmask en diagonalen met een loop en een bitmask dat je shift. Als je het slim aanpakt kan je denk ik zelfs meerdere kolommen of diagonalen tegelijk controleren.

Bedankt voor je reactie. Helaas is het gebruik van een 2d array een vereiste. We hebben heel erg veel op internet kunnen vinden waar ze het probleem met een 1d array oplossen. Ook de manier die jij beschrijft alleen helaas mag dit dus niet.

pedorus schreef op woensdag 23 oktober 2013 @ 20:09:
Een 8x8 int array is niet bepaald een handige representatie voor dit probleem. Tegenwoordig kun je algoritmes vaak het snelst krijgen door zo min mogelijk geheugen te gebruiken, of het geheugen zo handig mogelijk aan te spreken. 8x8 is toevallig precies 64 bit, wat schitterend in een long long past. Van te voren kun je berekenen op welke plaatsen niet al iets mag staan, wil je succesvol een koningin op positie x kunnen zetten zonder overlap te veroorzaken. Die positie testen is een simpele AND-operatie. Hiermee kun je denk ik binnen 100ms alle 92 oplossingen berekenen op een moderne processor.

Googelen geeft hetzelfde idee, zie bijv.:
http://www.jsomers.com/nqueen_demo/nqueens.html
http://georgovassilis.blo...eens-puzzle-with-bit.html
http://www.cl.cam.ac.uk/~mr10/backtrk.pdf
http://rosettacode.org/wiki/N-queens_problem#C

Bedankt voor het antwoord. Dit hadden we echter zelf ook al gevonden. Het is echt de bedoeling dat we een 2d array gebruiken.

[pedorus]

ZpAz schreef op woensdag 23 oktober 2013 @ 19:08:
Vanuit daar kan je met een aantal ifjes kijken of er twee koninginnen naast elkaar staan, en in een loopje doe je dit dan voor elke positie.

Naast elkaar staan kan sowieso niet, maar een koningin dekt de hele diagonaal/regel/kolom af (itt een koning). Ik snap daarom deze uitleg niet helemaal.

Wat ook zou kunnen is een sweep line algorithm, waarbij je iedere positie maar 1 keer checkt op de aanwezigheid van een koningin, zodat je de elementen netjes opeenvolgend afloopt. Je houdt bij welke rijen op dat moment naar schuinboven, schuinonder en rechtdoor worden afgedekt. Dit zou ook heel mooi met bitwise-operaties kunnen, maar ik weet niet of dat wel is toegestaan. Het kan ook prima met arrays.

[NMe]

Pedorus, niet om vervelend te doen, maar voor twee topicstarters die aangeven beginnend programmeur te zijn is het gebruik van bitmasks en een niet elementair simpel algoritme misschien niet de beste approach. Dit is een schoolopdracht die waarschijnlijk gewoon bedoeld is om de basis van loops en arrays duidelijk te maken. Laten we dus vooral de oplossingen voor extra credit even laten liggen.

[Soultaker]

Ik weet niet welk deel van de opdracht vaststaat, maar ik heb het idee dat het praktischer is bij het N-queens probleem om bij te houden per kolom (of rij) op welke rij (of kolom) de koningin staat, dan per vakje bij te houden of 't wel of niet bezit is, zoals je nu doet.

Bijvoorbeeld, een 4x4 bord zoals dit:

  0 1 2 3
0 x . . .
1 . . . x
2 . x . .
3 . . x .

Kun je coderen als:

C:

int rows[4] = { 0, 2, 3, 1 };

Op deze manier heb je sowieso exact één koningin per kolom. (Die array hierboven codeert de coördinaten (0,0), (1,2), (2,3), (3,1), maar omdat het kolomnummer precies overeenkomt met de index in de array, hoef je die niet expliciet op te slaan.)


Om te controleren dat er geen twee koningen op dezelfde rij staan, hoef je alleen maar te checken dat elke waarde maar één keer voorkomt in de array.

Nu de diagonalen. Als je een koningin hebt op (x1,y1) en een andere op (x2,y2), dan staan die op dezelfde diagonaal indien |x1 - x2| == |y1 - y2|. De koninginnen kun je makkelijk paarsgewijs tegen elkaar checken (de exacte code mag je zelf schrijven), en wat helemaal handig is, is dat je bij het plaatsen van een nieuwe koningin alleen tegen de vorige koninginnen hoeft te checken.

[ Voor 8% gewijzigd door Soultaker op 23-10-2013 21:46 ]

[pedorus]

NMe schreef op woensdag 23 oktober 2013 @ 21:16:
Laten we dus vooral de oplossingen voor extra credit even laten liggen.

offtopic:
zesjescultuur ook

Overigens kunnen de loopjes in de TS wel gecombineerd worden met behulp van bord[SIZE - {i of j}]. Maar qua snelheid zal dat waarschijnlijk niet erg uitmaken. Je checkt nu juist door te combineren een diagonaal dubbel bijvoorbeeld.

Verder kun je a = a + x natuurlijk schrijven als a += x. Instant compactheid.

[Coca-Cola]

lamain schreef op woensdag 23 oktober 2013 @ 18:33:
Beste Tweakers,

Voor een schoolopdracht moeten we het 8 koninginnen probleem oplossen, we zijn beginnend c programmeurs, dus het bevatten van diagonaal door een 2d array gaan is lastig.

offtopic:
Toevallig Kosters bij de uni Leiden? (Waarschijnlijk niet, want geen schoolopdracht ) die heeft nogal een voorliefde voor dit probleem

[lamain]

pedorus schreef op woensdag 23 oktober 2013 @ 22:17:
[...]

offtopic:
zesjescultuur ook

Overigens kunnen de loopjes in de TS wel gecombineerd worden met behulp van bord[SIZE - {i of j}]. Maar qua snelheid zal dat waarschijnlijk niet erg uitmaken. Je checkt nu juist door te combineren een diagonaal dubbel bijvoorbeeld.

Verder kun je a = a + x natuurlijk schrijven als a += x. Instant compactheid.

Dank voor de reactie. Dat van de compactheid zullen we zeker doen bedankt!. Het is nu vooral dus het probleem van het diagonaal van rechtsboven naar linksonder checken

1 1 1 1 1 1 1 2
1 1 1 1 1 1 2 2
1 1 1 1 1 2 2 2
1 1 1 1 2 2 2 2
1 1 1 2 2 2 2 2
1 1 2 2 2 2 2 2
1 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2

Zoals hier boven te zien kunnen we nu als het ware alleen de 1nen checken en daarna de 2en . Er moet toch simpelweg een logischer verband tussen de rechtsboven naar linksonder rijen zitten?

Als je kijkt naar de rijen van linksboven naar rechtsonder kan je zeggen dat de coördinaten van de te checken rijen zijn :

0,0 1,0 2,0 3,0 4,0 5,0 6,0 7,0
1,1 2,1 3,1 4,1 5,1 6,1 7,1
2,2 3,2 4,2 5,2 6,2 7,2
3,3 4,3 5,3 6,3 7,3
4,4 5,4 6,4 7,4
5,5 6,5 7,5
6,6 7,6
7,7

Dan kun je dus een loop maken waar for lus 1 telkens van 0 tot N telt en for lus 2 van N tot 7 telt. Om de andere helft van het array te pakken kun je dus array i j array j i maken.

Dit verband zit dus niet tussen de rechtsboven naar linksonder diagonaal. We kunnen dit voor zo ver wij weten alleen verwerken in 2 losse lussen voor beide helften. Dit maakt de code langer en qua tijd aanzienlijk langer. Het idee is dus om een lus te maken die zowel de linker als rechter helft kan bekijken.

Coca-Cola schreef op woensdag 23 oktober 2013 @ 23:45:
[...]

offtopic:
Toevallig Kosters bij de uni Leiden? (Waarschijnlijk niet, want geen schoolopdracht ) die heeft nogal een voorliefde voor dit probleem

offtopic:
Bedankt voor het compliment , maar nee we doen hbo aan Hanzehogeschool.

[pedorus]

Over die loopjes: Stel even n=1, want n=0 is een apart geval waarbij je dubbel checkt. Je checkt nu al:

[i][j]: 1,0 2,1 3,2 4,3 5,4 6,5 7,6
[j][i]: 0,1 1,2 2,3 3,4 4,5 5,6 6,7

Voor de andere diagonaal zou je dan tegelijkertijd kunnen checken, zoals ik zeg:

[SIZE-i][j]: 6,0 5,1 4,2 3,3 2,4 1,5 0,6
[SIZE-j][i]: 7,1 6,2 5,3 4,4 3,5 2,6 1,7

Zo heb je maar 1 inner for-loop nodig voor beide richtingen, in plaats van de 3 inner loopjes met i die je nu hebt. Misschien helpt het om met bijvoorbeeld excel of op papier het uit te tekenen anders.

Maar verwacht hier geen snelheidsverbeteringen van, want dat zou wel eens tegen kunnen vallen ivm allerlei optimalisaties die de compiler en processor doen. En normaal evalueer je niet steeds het gehele bord, maar slechts het nieuwe/veranderde deel. Hoewel: meten=weten.

[ Voor 5% gewijzigd door pedorus op 24-10-2013 00:45 ]

[Verwijderd]

Tip: diagonalen alleen naar de linkerkant checken.

Doorgaans vul je je bord van links naar rechts. Dat betekent dat als je een queen neerzet, er alleen aan de linkerkant collissions kunnen ontstaan. Dat versimpelt de code een stuk.

[Lone Gunman]

Wat pedorus zegt kun je misschien makkelijker uitwerken als je bedenkt dat je eigenlijk aan het spiegelen bent over de x en y assen.

Je verdeelt je bord in 4 kwadranten, nl. linksboven, rechtsboven, linksonder en rechtsonder. Ieder kwadrant heeft 7 diagonalen van lengte 2 t/m lengte 8 (de hoekpunten tel je niet mee).
Daarna implementeer je een enkel kwadrant en die ga je spiegelen over de x en y as zoals pedorus in zijn post heeft uitgewerkt. In de binnenste loop krijg je dan 4 buffer variabelen, een per kwadrant.

De lange diagonalen worden dan wel dubbel berekend, maar dat is verder geen probleem (alleen niet heel netjes )

ps. verder geen idee of het efficienter is, maar misschien maakt het de code makkelijker te lezen/begrijpen.

[ Voor 15% gewijzigd door Lone Gunman op 24-10-2013 01:25 ]

[Raling]

Chris_NL schreef op woensdag 23 oktober 2013 @ 20:27:
[...]

Bedankt voor je reactie. Helaas is het gebruik van een 2d array een vereiste. We hebben heel erg veel op internet kunnen vinden waar ze het probleem met een 1d array oplossen. Ook de manier die jij beschrijft alleen helaas mag dit dus niet.


[...]


Bedankt voor het antwoord. Dit hadden we echter zelf ook al gevonden. Het is echt de bedoeling dat we een 2d array gebruiken.

Sorry als ik iets heel raars zeg, maar het enige verschil tussen het gebruik van een 1d array en de 2d array is toch de manier van uitlezen? Natuurlijk is het minder handig en ook onnodig om een 2d array te gebruiken, maar een 1d array is eigenlijk ook alleen maar op een slimme manier gebruik maken van de eigenschappen van een array en er een 2d array van maken.

[Verwijderd]

edit:
Meh, het is laat.

Nog een idee:

Volgens mij kun je de posities van de koninginnen beschrijven met een 24 bit representatie, zie pedorus, maar dan in plaats van een array van 8 getallen zie je het als een array van 8 keer 3 bits, waarbij 3 het aantal bits is dat je nodig hebt om een kolom aan te geven. Je kunt dus een loopje bouwen dat door 0 t/m 2²⁴ = 16 mln loopt.

Allereerst kun je heel snel door de 8 posities van een koningin wandelen (bitshift telkens 3 bits) en telkens 1 << n doen en het totaal bijhouden via de bitwise OR operatie. Als het resultaat geen 0xFF is, dan heb je twee koninginnen op dezelfde rij en kun je al snel afbreken.

Bepaal daarna de twee diagonalen (x+y, 7-y+x). Deze mogen geen van allen twee keer voorkomen. Dit kan dus allemaal makkelijk en snel met bitmasks. Volgens mij verlies je niets door in plaats van de 15 mogelijke diagonalen 16 bits te gebruiken. Kortom, op 1 t/m 16 de diagonaal / coördinaat, en op 17 t/m 32 diagonaal \. Rag door je koninginnenposities met OR operaties en je houdt dus als resultaat 32 bits over. Als daarvan minder dan 16 bits geset zijn, delen er twee koninginnen een diagonaal, en dat mag niet.

Denk hieraan als je een probleem hebt waarbij iets "uniek" moet zijn, dat is in principe om te zetten naar een bitwise representatie die je kunt OR-ren, XOR-ren, etcetera.

[ Voor 68% gewijzigd door Verwijderd op 24-10-2013 04:24 ]

[lamain]

Iedereen bedankt voor de reacties! Het is gelukt om de code een stuk compacter te krijgen. De code is helaas niet sneller geworden (zoals pedorus al zei).

C:

 
    for(i=0; i<SIZE; i++){
        for(j=0; j<SIZE-i; j++){
            buf1+=bord[j][SIZE2-i-j];
            buf2+=bord[i+j][SIZE2-j];
            buf3+=bord[j][i+j];
            buf4+=bord[i+j][j];
        } 
    if(buf1>1 || buf2>1 || buf3>1 || buf4>1)
        return 0; 
    buf1=buf2=buf3=buf4=0;
    }

Hier boven wordt diagonaal linksboven naar rechtsonder EN rechtsboven naar linksonder gecheckt . Dit is naar mijn mening een aanzienlijk stuk mooier dan wat we eerst hadden.

Nogmaals iedereen bedankt, met jullie hulp konden we even inzien hoe het moest
(ps mocht je nog opmerkingen hebben over het bovenstaande stukje mag dat natuurlijk ook)