variant 8 queens probleem

[Verwijderd]

Hey,

Ik ben momenteel bezig met een exhaustief backtracking algoritme dat een oplossing geeft voor een variant op het 8 queens probleem.

Het komt er op neer dat ik een aantal vast bepaalde koninginnen per kolom moet zetten. Maar op zo een manier dat als alle koninginnen geplaatst zijn. Ze mekaar zo weinig mogelijk bedreigen per rij, en enkel per rij.

bvb : 0 koninginnen = 0 bedreiging
1 koninginnen = 1 bedreiging
2 koninginnen = 2 bedreiging

Mijn probleem is niet de bedreiging bepalen, maar hoe dat ik meer dan 1 kongingen kan zetten per kolom in mijn recursief algortime.

Dit is het recursief algoritme voor 1 koningin per kolom :

public void findAllSolutions() {
findAllSolutions(1);
}
private void findAllSolutions(int n) {
if (n > dim)
newSolution();
else {
for (int r = 1; r <= dim; r++) {
putQueen(r,n);
findAllSolutions(n+1);
removeQueen(r,n);
}
}
}
}
private void newSolution() {
System.out.println(toString());
}

Hoe kan ik dit uitbreiden zodat ik bvb kan zeggen : 3 koningen op 1ste kolom
2 koningen op 2de kolom
5 koningen op 3de kolom

En dan dat aantal per kolom permuteren zodat ik alle mogelijke schikkingen krijg voor de n koninginnen per kolom? Let er wel op dat als er staat n per kolom, dat er ook altijd n moeten staan en niet minder mogen staan.

Op elke kolom moet minstens wel 1 koningen geplaatst worden.

Alvast bedankt!

Mvg

[Woy]

Welkom op GoT,

Lees even het volgende door: code tags. Daardoor is je code voorbeeld een stuk beter te lezen.

Verder hoef je niet te groeten onder je post: Wij tweakers doen elkaar permanent de groeten

[MicroWhale]

*laat maar*

[ Voor 97% gewijzigd door MicroWhale op 27-03-2009 13:35 ]

[Verwijderd]

Ik heb het even aangepast

Java:

public void findAllSolutions() {
   findAllSolutions(1);
}

private void findAllSolutions(int n) {
    if (n > dim)
      newSolution();
    else {
        for (int r = 1; r <= dim; r++) {
           putQueen(r,n);
           findAllSolutions(n+1);
           removeQueen(r,n);
        }
    }
}


private void newSolution() {
   System.out.println(toString());
}

[Verwijderd]

Mag ik nog even zeuren over de edit knop?
Verder kan ik je niet helpen aan een oplossing,maar ben wel benieuwd na hoe je het op kan lossen,zodat ik je code weer eens kan bekijken om er van te leren

[Woy]

Ik snap je vraag ook niet helemaal.

Je wilt recursief een bord vullen voor een variatie van het queens probleem. Bij jou versie kunnen er blijkbaar meerdere koninginnen per column staan ( Hierdoor krijg je dus altijd "bedreigingen" ).

Op wat voor manier wil je je bord nu opbouwen? Weet je van te voren hoeveel koninginnen er in een column moeten komen? Of heb je alleen een totaal aantal koninginnen wat je moet plaatsen?