Landkarte mit 4 Farben

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
Antworten
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

Hallo Leute

Ich habe einen Weg gesucht die Länder auf einer Landkarte mit 4 Farben einzufärben, ohne das ein Nachbarland dieselbe Farbe hat. Das scheint jetzt zu klappen, allerdings bin ich beim testen auf etwas merkwürdig gestossen(Zeile 54).
Ich rufe eine (mittlerweile unnötige)Procedure auf die einen Parameter verlangt, diesen Parameter zu übergeben hatte ich vergessen, aber es kommt keine Fehlermeldung.
Frage: Wieso nicht?

Die fragliche Zeile ist: if Rest == 0: return
Die Procedure: def Rest(L):

Code: Alles auswählen

import copy,sys

Farben = range(1,5) # 4 Farben, 1..4, 0=noch ohne Farbe
AnzahlLaender = 14 # zum testen

Laender = []
for i in range(AnzahlLaender):
   Laender.append([0,[]]) # [0]=Farbe [1]=Nachbarlaender

""" 0=Island  1=Irland  2 = GB  3=Norwegen  4=Schweden
 5=Finnland  6=Daenemark  7=Deutschland  8=Niederlande
 9=Luxemburg 10=Belgien 11= Frankreich 12= Spanien 13= Schweiz """

# Nachbarlaender, zumindest farblich
Laender[0][1]  = [1,2,3]
Laender[1][1]  = [0,2]
Laender[2][1]  = [0,1,3,11,8,10]
Laender[3][1]  = [4,0,2,6]
Laender[4][1]  = [3,5,6]
Laender[5][1]  = [4]
Laender[6][1]  = [3,4,7]
Laender[7][1]  = [6,10,13,11,9,8]
Laender[8][1]  = [1,7,10,9]
Laender[9][1]  = [7,8,10,11]
Laender[10][1] = [7,8,9,11]
Laender[11][1] = [10,12,7,13,9]
Laender[12][1] = [11]
Laender[13][1] = [7,11]

# alle Laender haben [ungleiche] Farbe
def Bingo(L):
   for i in range(len(L)):
      if L[i][0] == 0: return False
   for i in range(AnzahlLaender):
      print i,'=',L[i][0]
   sys.exit()

# Farbe der Nachbarlaender checken
def FarbeOK(L,LandNr,Farbe):
   for i in L[LandNr][1]:
      if L[i][0] == Farbe: return False
   return True

# Anzahl Laender ohne Farbe
def Rest(L):
   r = 0      
   for i in range(len(L)):
      if L[i][0] == 0: r = r + 1
   return r

# rekursive Suche
def Faerben(L):
   Bingo(L) # Check ob Weg gefunden
   if Rest == 0: return # Irrweg
   for LandX in range(AnzahlLaender):
      if L[LandX][0] == 0:
         for Farbe in Farben:
            if FarbeOK(L,LandX,Farbe):
               L2 = copy.deepcopy(L)
               L2[LandX][0] = Farbe
               Faerben(L2)

# Jedes Land wird als Anfang getestet
for LandX in range(AnzahlLaender):
   for Farbe in Farben:
      L = copy.deepcopy(Laender)
      L[LandX][0] = Farbe
      Faerben(L)

Ist es weil der übergebene Parameter dieselbe Bezeichnung hat und er als global interpretiert wird ?

Danke für einen Hinweis...
BlackJack

salznase hat geschrieben:Ich rufe eine (mittlerweile unnötige)Procedure auf die einen Parameter verlangt, diesen Parameter zu übergeben hatte ich vergessen, aber es kommt keine Fehlermeldung.
Frage: Wieso nicht?

Die fragliche Zeile ist: if Rest == 0: return
Du rufst die Funktion gar nicht auf, sondern vergleichst die Funktion selbst mit 0. Das ergibt immer `False`.
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

@BlackJack

Für Python ist es also ein normaler Vergleich: Funktion-Adresse(Hex-Zahl) / Zahl
Danke, wusste nicht daß das so geht... :oops: ich nutze sonst Pascal, der Compiler würde da meckern...
BlackJack

Die Funktionsadresse eher nicht. Funktionen sind auch Objekte und eine Funktion und eine Zahl sind ganz offensichtlich ungleich.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

salznase hat geschrieben:Für Python ist es also ein normaler Vergleich: Funktion-Adresse(Hex-Zahl) / Zahl
Nein, für Python ist das ein ganz normaler Vergleich zwischen zwei Objekten: einem Funktionsobjekt und einem Zahlenobjekt.
salznase hat geschrieben:ich nutze sonst Pascal, der Compiler würde da meckern...
Ich glaube auch nicht das Pascal sowas (zumindest in dieser Form) überhaupt unterstützt.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

Danke nochmal, BlackJack und Leonidas.


Für das einfärben von Flächen mit wenigen Farben gibt es sogar eine Wikipedia-Seite: http://de.wikipedia.org/wiki/Vier-Farben-Satz
(Irgendeinen Code dazu hatte ich leider noch nirgendwo gesehen)
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

Hi

Beim Testen musste ich feststellen das es gar nicht so einfach ist, eine Fläche mit nur 4 Farben einzufärben(selbst, nicht mit dem Programm) ohne das sich Flächen mit gleicher Farbe berühren.

Probiert das mal mit dieser Grafik( http://www.lupi.ch/Schools/4farb2.jpg ), habe es 2 mal probiert, für ein paar Felder hätte ich eine 5. Farbe nehmen müssen.
Gibt es sowas als Python-Game? :wink:
Nirven
User
Beiträge: 130
Registriert: Mittwoch 10. Mai 2006, 08:18
Wohnort: Bremerhaven

Stimmt, gar nicht so einfach ohne den richtigen Ansatz. Wenn man in der Mitte anfängt, und versucht nur drei Farben zu benutzen (geht natürlich nicht, aber soweit möglich), dann funktioniert es.

Aber wie man das einem Programm allgemeingültig klar machen will... geht nur über viiiiieeel probieren, oder?
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

@Nirven - Hallo
Wenn man in der Mitte anfängt, und versucht nur drei Farben zu benutzen (geht natürlich nicht, aber soweit möglich), dann funktioniert es.
Du hast es geschafft beim 1 mal? Cool.
Aber wie man das einem Programm allgemeingültig klar machen will... geht nur über viiiiieeel probieren, oder?
Das Programm im ersten Beitrag kann das, allerdings muß man von jedem Feld die Nachbarn eingeben(das dauert).
Das Feld müsste automatisch generiert werden(Rechtecke oder Kreiselemente wie hier: http://upload.wikimedia.org/wikipedia/c ... mple-2.png ) und die Nachbarflächen gleich registriert werden.
Ich hätte aber Probleme bei der GUI-Programmierung mit Python, kenne mich so gut wie überhaupt nicht aus, bin zu verwöhnt von Lazarus/Delphi.

ciao
Nirven
User
Beiträge: 130
Registriert: Mittwoch 10. Mai 2006, 08:18
Wohnort: Bremerhaven

Ne, drittes mal. Die ersten beiden Male habe ich aussen angefangen und war ziemlich schnell in einer Sackgasse. Aus der Mitte ging es dann recht einfach durch den regelmäßigen Aufbau. Nur am Rand musste man dann aufpassen.

Jo, über probieren. Wäre ich so auch nicht draufgekommen, was ich mich aber frage ist, ob man einem Programm beibringen kann da "logisch" ranzugehen? Oder zumindestens etwas überlegt, vielleicht mit einer Grundstrategie, anstelle puren Ratens.

Btw: Die Abfrage nach dem Rest in Zeile 54 verstehe ich nicht ganz. Wenn allen Ländern eine Farbe zugewiesen ist (nirgends 0), dann steigt das Programm doch in "Bingo(L)" schon aus. Und Rest ist doch eigentlich die serlbe Abfrage (gibt es irgendwo die Farbe 0?).
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

@Nirven
was ich mich aber frage ist, ob man einem Programm beibringen kann da "logisch" ranzugehen? Oder zumindestens etwas überlegt, vielleicht mit einer Grundstrategie, anstelle puren Ratens.
Ich habe dieses Programm mal "übersetzt" in Pascal um z.B. Geschwindigkeit mal zu vergleichen, da habe ich das halbe Feld(57Felder) mal eingetragen: 0.005Sek(mit 2.5GHz) bis zur Lösung inkl. Lösungzeigen. Eine Strategie rauszubekommen mag reizvoll sein, angesichts der Zeiten kanns aber kaum was bringen...
Btw: Die Abfrage nach dem Rest in Zeile 54 verstehe ich nicht ganz. Wenn allen Ländern eine Farbe zugewiesen ist (nirgends 0), dann steigt das Programm doch in "Bingo(L)" schon aus. Und Rest ist doch eigentlich die serlbe Abfrage (gibt es irgendwo die Farbe 0?).
Du hast recht! Ich hatte diesen Teil mitgepostet weil ich da was (für mich) komisches entdeckt hatte. Die Procedure Rest hatte ich am Anfang genutzt und dann einen besseren Weg gefunden.

Schönen Abend noch...
Antworten