Knights Tour

#Knights tour time
import operator

def valid(n,  m,  tour,  place):
    return place[0] < n and place[0] >= 0 and place[1] < m and place[1] >= 0 and place not in tour

def knights_tour(n,  m,  tour):
    placements = [ [-2,  -1],  [-2,  1], [-1,  -2],  [-1,  2],  [1,  -2],  [1,  2],  [2, -1],  [2, 1]]
    if len(tour) == n * m:
        for place in [map(operator.add,  tour[-1],  i) for i in placements]:
            if place == tour[0]:
                print "Open Tour"
        return tour
    #Find valid placement, greedy
    weighteddegree = 9
    weightedplace = []
    for place in [map(operator.add,  tour[-1],  i) for i in placements]:
        if valid(n,  m,  tour,  place):
            degree = sum([valid(n,  m,  tour,  j) for j in [map(operator.add,  place,  ii) for ii in placements]])
            if degree < weighteddegree:
                weightedplace = place
                weighteddegree = degree

    if weighteddegree < 9:
        tour.append(weightedplace)
        return knights_tour(n,  m,  tour)

    return False

def print_board(n,  m,  tour):
    placements = [ [-2,  -1],  [-2,  1], [-1,  -2],  [-1,  2],  [1,  -2],  [1,  2],  [2, -1],  [2, 1]]
    for y in range(n):
        for x in range(m):
            if [y,  x] in tour:
                print "K",
            else:
                print sum([valid(n,  m,  tour,  j) for j in [map(operator.add,  [y,  x],  ii) for ii in placements]]),
        print

def helper(n,  m):
    for i in range(n):
        for j in range(m):
            print("Knights Tour at " + str(i) + "," + str(j))
            ret = knights_tour(n,  m,  [[i ,  j]])
            print(ret)

def main():
    print("Knights Tour")
    n = int(raw_input("Board Height:"))
    m = int(raw_input("Board Widtht:"))

    while True:
        i = int(raw_input("Start Row:"))
        j = int(raw_input("Start Column:"))
        if i < 0 or j < 0 or i >= n or j >= m:
            print("Invalid start position, note that 0 is a valid column/row.")
        else:
            break

    #helper(n,  m)

    ret = knights_tour(n,  m,  [[i ,  j]])
    print(ret)

main()