Åtta damer
En klassisk schackgåta är hur man placerar åtta damer(vilket är det maximala antalet damer som kan samexistera) på ett schackbräde utan att någon av pjäserna kan slå ut varandra.Det är också en vanlig algoritm att implementera när man lär sig rekursionsdriven programmering.
Se även
- Schack
- Schackpjäsen dam
- n-dams problemet
Visa oss din egen implementation här (gärna i olika programspråk).
Här är en implementation i Haskell, queens 8 8 ger alla möjliga lösningar (92 stycken):
queens r 0 = [[]] queens r c = [ x:rs | rs queens r (c-1), x [1..r], ok x rs]where ok x rs = x `notElem` rs && diag (-) x rs && diag (+) x rs diag f x [] = True diag f x (y: ys) = let x = f x 1 in x < 1 || x > r || (x /= y && diag f x ys)
Algoritmen fungerar så här, rekursivt: givet en lösning för r (c-1), generera alla möjliga lösningar för r c.
Här kommer en intressant tabell med antal lösningar för olika brädesstorlekar (genererad med programmet):
Artikeln skriven 2009-01-16 av Learning4sharing
Inga kategorier för denna artikel än...Intresserad av fler artiklar?
AlNicklas Lundblad
Sveriges Socialdemokratiska Ungdomsförbund
Politisk broiler
De Geerhallen
Finspongssamlingen
YouTube
Pilsner Urquell
Kulturnatten