somehow both super easy and really hard

knights_tour.py

import turtle
import random

t = turtle.Turtle()
s = turtle.Screen()

n = 30 # width of board, in cells, must be even
width = 10 # width of cell, in turtle units
dot_size = 0 # dot size

t.speed(0)

visited_squares = []

def draw_chessboard():
	t.pu()
	t.goto(0,0)
	t.pd()
	
	for i in range(n/2):
		t.fd(width*n)
		t.right(90)
		t.fd(width)
		t.right(90)
		t.fd(width*n)
		t.left(90)
		t.fd(width)
		t.left(90)
	
	t.fd(width*n)
	t.left(90)

	for i in range(n/2):
		t.fd(width*n)
		t.left(90)
		t.fd(width)
		t.left(90)
		t.fd(width*n)
		t.right(90)
		t.fd(width)
		t.right(90)
	
	t.fd(width*n)
	t.right(90)
	t.pu()
	board_move(random.randint(1,n),random.randint(1,n))
	t.pd()

def board_move(x,y):
	t.goto((width/2)+(width*(x-1)),(-width/2)-(width*(y-1)))
	t.dot(dot_size)

def board_pos():
	q = width/2
	x,y = t.pos()
	
	rx = ((x-q)/width)+1
	ry = ((y+q)/(-width))+1

	return rx,ry

def count_movable_squares(x,y):
	m = 0
	xl = [-2,-1,1,2,2,1,-1,-2]
	yl = [1,2,2,1,-1,-2,-2,-1]
	p = zip(xl,yl)

	for i,j in p:
		a, b = x+i, y+j

		if (a >= 1) and (a <= n) and (b >= 1) and (b <= n) and (a,b) not in visited_squares:
			m += 1
	
	return m

def get_movable_squares(x,y):
	s = []
	xl = [-2,-1,1,2,2,1,-1,-2]
	yl = [1,2,2,1,-1,-2,-2,-1]
	p = zip(xl,yl)

	for i,j in p:
		a, b = x+i, y+j

		if (a >= 1) and (a <= n) and (b >= 1) and (b <= n) and (a,b) not in visited_squares:
			s.append((a,b))
	
	return s


def knights_tour():
	global visited_squares
	visited_squares.append(board_pos())

	while True:
		i,j = board_pos()
		movable_squares = get_movable_squares(i,j)
		movable_counts = {(x,y) : count_movable_squares(x,y) for x,y in movable_squares}
		min_moves = min(movable_counts.values())
		move_to = board_pos()

		for p in movable_squares:
			if movable_counts[p] == min_moves:
				move_to = p
				break
		
		board_move(*move_to)
		visited_squares.append(move_to)

draw_chessboard()
while True:
	try:
		knights_tour()
	except:
		break