Log In
Home
November 15, 2001
Offline
Läser Algoritmer och Datastrukturer.
Har ett problem att lösa med 8 vita drottningar på schackbräde.
Detta skall lösas med pseudokod.Några förslag?
June 18, 2001
Offline
Beskriv problemet...
August 2, 2001
Offline
Triviala sätt prova gör en uttömmande sökning och pröva alla positioner men komplexiteten blir urusel.
Pröva placera damen i varje position på raden i tur och ordning.
Kan damen stå ohotad i den positionen placera den på raden under.
int queenpos[8]
queenpos[0] ger var på rad 1 som damen ska in.
queenpos[2] ger var på rad 3 som damen ska in osv.
När körningen är klar
testRow(int row)
for i=0 i < 8 ; i++ {
queenpos[row]=i
if PosOK() {
if row == 7 //färdig
skriv ut lösningen och avbryt ingen idé att fortsätta när vi hittat en möjlig lösning
else
testRow(row+1)
}
}
PosOK funktion som retunerar sant om damen kan placeras där utågende från färg samt ifall den kan ta någon annan pjäs.
Börja med anropet testRow(0)
Prövar alla möjliga kombinationer tills den finner en lösning som funkar.
EDIT: Konstig mening.
[ Detta Inlägg ändrades av: _paul_ den 2001-11-26 21:33 ]
[ Detta Inlägg ändrades av: _paul_ den 2001-11-26 21:34 ]
[ Detta Inlägg ändrades av: _paul_ den 2001-11-26 21:40 ]
August 2, 2001
Offline
Jerry:
Det är ett klassikt problem som går ut på hur man ska placera ut 8 damer på ett schackbräde utan att de kan ta/"käka upp varandra".
June 18, 2001
Offline
Så här, eller?
[0] [0] [0] [#] [0] [0] [0] [0]
[0] [0] [0] [0] [0] [#] [0] [0]
[0] [0] [0] [0] [0] [0] [0] [#]
[0] [#] [0] [0] [0] [0] [0] [0]
[0] [0] [0] [0] [0] [0] [#] [0]
[#] [0] [0] [0] [0] [0] [0] [0]
[0] [0] [#] [0] [0] [0] [0] [0]
[0] [0] [0] [0] [#] [0] [0] [0]
_________________
P4 1,4, ASUS P4T, PoV GF2 MX200, SB live(!), 2*64 RDRAM, Iiyama 19"
[ Detta Inlägg ändrades av: Jerry den 2001-11-26 21:47 ]
August 2, 2001
Offline
Jo jag tror åtminstone det var det här problemet nule menade. Snabbt jobbat av dig 
November 15, 2001
Offline
Funderar på att göra en backtracking eller en rekursiv lösning. Någon som har ett tips på pseudokod till dessa lösningar. (Eller kod)
June 18, 2001
Offline
Pos dam i kolumn 1, rad 1
Pos dam2 i kolumn 2, första raden där det inte står någon annan dam och där prev_damRad - dam2Rad = prev_damKolumn - dam2Kolumn. (då står de nämligen i samma diagonal)
Fortsätt så tills du inte kan placera ut en dam på nästföljande kolumn längre, då går du tillbaka ett steg och flyttar den damen till nästa möjliga rad. Finns det ingen annan rad, gå tillbaka till den före osv.
// skapa ett bräde först sedan...
k=0;
funkt(board, 1, 0);
funkt(Board[][] board, j,k)
i=1;
while(i<=8)
{
for(int p = 0; p < k; p++)
{
if(!(dam[p].X - i == dam[p].Y - j) && !(dam.[p].X == i)) {antalOk++;}
}
if(antalOk == p) //Inget hot => ok att placera ut.
{
board[i][j] = dam[k];
dam[k].X = 1;
dam[k].Y = 1;
funkt(board, j+1,k+1); // låter nästa dam placeras ut.
}
i++;
}
Nu får du själv komma på hur du ska göra om den inte hittar någon plats att ställa damen på.
Hm...något rörig kod..
_________________
P4 1,4, ASUS P4T, PoV GF2 MX200, SB live(!), 2*64 RDRAM, Iiyama 19"
[ Detta Inlägg ändrades av: Jerry den 2001-11-27 21:39 ]
1 Guest(s)
