Damenproblem (Kleinprojekte)
Das Damenproblem ist eine schachmathematische Aufgabe. Es sollen jeweils acht Damen auf einem Schachbrett so aufgestellt werden, dass keine zwei Damen einander nach den Schachregeln schlagen können. Die Figurenfarbe wird dabei ignoriert und es wird angenommen, dass jede Figur jede andere angreifen könnte. Anders ausgedrückt, es sollen sich keine zwei Damen die gleiche Zeile, Spalte oder Diagonale teilen. Im Mittelpunkt steht die Frage nach der Anzahl der möglichen Lösungen.
Schreiben Sie ein Programm, welches Ihnen für ein bestimmte Anzahl Damen die möglichen Lösungen ausgibt. Bei sechs Damen auf einem 6x6 Schachbrett ist eine Lösung [1, 3, 5, 0, 2, 4]. Das heisst die Damen stehen auf den Feldern A2, B4,C6, D1, E3, F5.
Erweitern Sie ihr Programm, dass symmetrische Lösungen nicht mehrfach gezählt werden.
0 Kommentare
1 Lösung(en)
def bedroht(pos,teilloesung):
# falls das Brett noch leer war
if teilloesung==[]: return 0
# vertikale Koordinate ist bereits vergeben
if pos in teilloesung: return 1
# diagonal
xtest = pos
ytest = len(teilloesung)
# teste alle bereits gesetzten Damen
for dame in range(len(teilloesung)):
xdame = teilloesung[dame]
ydame = dame
if abs(ytest-ydame)==abs(xtest-xdame):
return 1
return 0
def loesen(n,loesung):
global antwort
# wenn alle n Damen in der Liste sind
if len(loesung)==n:
antwort.append(loesung)
return
# jede mögliche x-Position
for x in range(n):
if not bedroht(x,loesung):
loesen(n,loesung+[x])
return
def damen(anzahl):
global antwort
antwort = []
loesen(anzahl,[])
for i in range(len(antwort)):
print '%3d: '%(i+1),antwort[i]
# Symmetrische Lösungen berücksichtigen:
# Bei einem quadratische Spielbrett gibt es acht
# symmetrisch äquivalente Lösungen:
# Drehung um 0°
# Drehung um 90°
# Drehung um 180°
# Drehung um 270°
# Spiegelung und Drehung 0°
# Spiegelung und Drehung 90°
# Spiegelung und Drehung 180°
# Spiegelung und Drehung 270°
def drehung_90(l):
n = len(l)-1
# Liste lnew mit 0 füllen
lnew = [0]*len(l)
for x in range(len(l)):
lnew[n-l[x]]=x
return lnew
def drehung_180(l):
lnew = drehung_90(l)
lnew = drehung_90(lnew)
return lnew
def drehung_270(l):
lnew = drehung_180(l)
lnew = drehung_90(lnew)
return lnew
def spiegelung(l):
# Werte kopieren
lnew = l[:]
# Reihenfolge umkehren
lnew.reverse()
return lnew
def spiegelung_drehung_90(l):
lnew = spiegelung(l)
lnew = drehung_90(lnew)
return lnew
def spiegelung_drehung_180(l):
lnew = spiegelung(l)
lnew = drehung_180(lnew)
return lnew
def spiegelung_drehung_270(l):
lnew = spiegelung(l)
lnew = drehung_270(lnew)
return lnew
def eindeutige_damen(anzahl):
global antwort
antwort = []
loesen(anzahl,[])
eindeutige_loesung = []
while antwort != []:
# Das erste Element ist sicher eine Lösung
loesung = antwort[0]
# Reduzieren der Antworten um das erste Element
antwort = antwort[1:]
eindeutige_loesung.append(loesung)
# Lösung auf Symmetrien überprüfen
for f in [drehung_90,drehung_180,drehung_270,
spiegelung,spiegelung_drehung_90,
spiegelung_drehung_180,spiegelung_drehung_270]:
symmetrische_loesung = f(loesung)
# Falls eine symmetrische Lösung zur eindeutigen Lösung vorkommt,
# wird diese aus der Antwortliste entfernt
if symmetrische_loesung in antwort:
antwort.remove(symmetrische_loesung)
for i in range(len(eindeutige_loesung)):
print "%3d:"%(i+1),eindeutige_loesung[i]
Verifikation/Checksumme:
damen(6)
1: [1, 3, 5, 0, 2, 4]
2: [2, 5, 1, 4, 0, 3]
3: [3, 0, 4, 1, 5, 2]
4: [4, 2, 0, 5, 3, 1]
Bei Berücksichtigung der symmetrischen Lösungen, gibt
es für sechs Damen nur eine Lösung.
Aktionen
Neue Lösung hinzufügen
Bewertung
Durchschnittliche Bewertung:
Meta
| Zeit: | 2-4 |
| Schwierigkeit: | k.A. |
| Webcode: | k998-inzt |
| Autor: | Martin Guggisberg (Universität Basel / PH FHNW) |