knightsTour

import Queue
class Vertex:
    def __init__(self, key):
        self.id = key
        self.connectedTo = {}
        self.color = 'white'
        self.distance = 0
        self.root = None

    def addNeighbor(self, neighbor, weight=0):
        self.connectedTo[neighbor] = weight

    def getColor(self):
        return self.color

    def setColor(self, c):
        self.color = c

    def getDistance(self):
        return self.distance

    def setDistance(self, d):
        self.distance = d

    def getRoot(self):
        return self.root

    def setRoot(self, r):
        self.root = r

    def __str__(self):
        return str(self.id) + ' ConnectedTo: ' + str([x.id for x in self.connectedTo])

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

    def getWeight(self, neighbor):
        return self.connectedTo[neighbor]

class Graph:
    def __init__(self):
        self.verticies = {}
        self.vertCount = 0

    def addVertex(self, key):
        self.vertCount += 1
        newVertex = Vertex(key)
        self.verticies[key] = newVertex
        return newVertex

    def getVertex(self, key):
        if key in self.verticies:
            return self.verticies[key]
        else:
            return None

    def __contains__(self, key):
        return key in self.verticies

    def addEdge(self, f, t, cost=0):
        if f not in self.verticies:
            nv = self.addVertex(f)
        if t not in self.verticies:
            nv = self.addVertex(t)
        self.verticies[f].addNeighbor(self.verticies[t],cost)

    def getVerticies(self):
        return self.verticies.keys()

    def __iter__(self):
        return iter(self.verticies.values())

    def bfs(self, fromKey, toKey):
        start = self.getVertex(fromKey)

        self.buildBfsTree(start)
        self.traverse(toKey)

    def buildBfsTree(self, start):
        start.setColor('grey')
        start.setDistance(0)
        start.setRoot(None)
        queue = Queue.Queue()

        queue.put(start)

        while not queue.empty():
            curVertex = queue.get()
            for neighbor in curVertex.getConnections():
                if neighbor.getColor() == 'white':
                    neighbor.setColor('grey')
                    neighbor.setRoot(curVertex)
                    neighbor.setDistance(curVertex.getDistance()+1)
                    queue.put(neighbor)
            curVertex.setColor('black')

    def traverse(self, key):
        x = self.getVertex(key)
        while(x.getRoot()):
            print(x.getId())
            x=x.getRoot()

        print(x.getId())


def flatten(x, y, size):
    return x % size + y*size

def genLegalMoves(x, y, size):
    newMoves = []
    legalMoves = [(-1,-2),(-1,2),(-2,-1),(-2,1),(1,-2),(1,2),(2,-1),(2,1)]

    for i in legalMoves:
        newX = x+i[0]
        newY = y+i[1]

        if(legalCoords(newX, size) and legalCoords(newY, size)):
            newMoves.append((newX, newY))
    return newMoves

def legalCoords(x, size):
    if(x >= 0 and x < size):
        return True
    else:
        return False

def constructKnightGraph(size):
    g = Graph()
    for i in range(size):
        for j in range(size):
            nodeKey = flatten(i,j, size)
            newPositions = genLegalMoves(i,j,size)
            for edge in newPositions:
                neighborKey = flatten(edge[0], edge[1], size)
                g.addEdge(nodeKey, neighborKey)
    return g

def knightsTour(depth, path, vertexToExplore, limit):
    vertexToExplore.setColor('grey')
    path.append(vertexToExplore)
    if depth < limit:
        neighborList = list(vertexToExplore.getConnections())
        i=0
        done = False
        while i < len(neighborList) and not done:
            if neighborList[i].getColor() == 'white':
                done = knightsTour(depth+1, path, neighborList[i], limit)
            i+=1
        if not done:
            path.pop()
            vertexToExplore.setColor('white')
    else:
        done = True
    return done

path = []
g = constructKnightGraph(8)
knightsTour(0,path,g.getVertex(0),64)