# Program to four-color a given planar map using backtracking search. # Michael L. Scott, February 2010. winSize = 512 # display pictures in window this long on a side from graphics import * from random import randint from subprocess import Popen, PIPE import sys class GotIt(Exception): # used to announce a solution def __init__(self, value): self.assignments = value class Tile: def __init__(self, id, pts, nbrs): self.index = id self.neighbors = nbrs self.polygon = Polygon(pts) self.polygon.setFill(color_rgb(randint(0, 255), randint(0, 255), randint(0, 255))) self.polygon.setWidth(3) def colorMe(self, remainingTiles, assignments): # I recommend you put the heart of your (recursive) algorithm here. # Parameter remainingTiles is a list of tiles that have not yet # been given a color. It should not include self. # Parameter assignments is a list, indexed by tile index, that # indicates the color currently assigned to the tile with that # index (or None if it doesn't have a color yet). When you find # a valid four-coloring, raise exception GotIt. pass # YOUR CODE HERE def setColor(self, color): self.polygon.setFill(color) class Map: def __init__(self, s = 0, n = 100, m = 40): # construct the command used to invoke the external java program: cmd = ("java -jar Map.jar -a 2 -n " + str(n) + " -m " + str(m) + " -s " + str(s)) # issue the command: MAP = Popen(cmd, shell=True, stdout=PIPE).stdout line = MAP.readline() # discard header line line = MAP.readline().rstrip() # numTiles, xmin, ymin, xmax, ymax words = line.split() numTiles = int(words[0]) self.tiles = [] for i in range(numTiles): coords = MAP.readline().rstrip().split() # readline grabs one line of external program output. # rstrip deletes the carriage return at the end of the line. # split breaks it apart into individual numbers # The following two assignments use "list comprehensions" -- # shorthand notation that initializes an entire list in one # (kinda cryptic) expression. pts = [Point(int(coords[2*j]), int(coords[2*j+1])) for j in range(len(coords) / 2)] nbrs = [int(j) for j in MAP.readline().rstrip().split()] self.tiles.append(Tile(i, pts, nbrs)) def display(self, w): # draw map on screen for t in self.tiles: t.polygon.draw(w) def undisplay(self): # erase map from screen for t in self.tiles: t.polygon.undraw() def fourcolor(self): # This should invoke your recursive search routine. try: pass # YOUR CODE HERE except GotIt as e: for t in self.tiles: t.setColor(e.assignments.pop(0)) # main program: def run(s): global m global w w = GraphWin("Map", 512, 512) w.setCoords(sys.maxint * -1.02, -sys.maxint, sys.maxint, sys.maxint * 1.02) # graphics package offsets line drawing up and left; # the 1.02's leave room for that seed = s m = Map(seed) try: while True: print seed, m.display(w) w.getMouse() print "...", m.fourcolor() w.getMouse() m.undisplay() seed += 1 m = Map(seed) except KeyboardInterrupt: print "done" w.close() # Close any previous instance of the mapping window: try: w.close() except: pass run(0) # call main program