import random

def mossa(numero, posizione):
	x,y = posizione
	cambio = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)] 
	x += cambio[numero][0]
	y += cambio[numero][1]
	if 0 <= x <= 7 and 0 <= y <= 7:
		return [x,y]
	else:
		return posizione
		
def mosse_possibili(posizione, matrice):
	mosse = []
	for i in range(8):
		temp = mossa(i,posizione)
		if (temp != posizione) and (matrice[temp[0]][temp[1]] == 0):
			mosse.append(temp)
	return mosse

def aggiorna_accesso(matrice):
	return [[len(mosse_possibili([i,j], matrice)) for j in range(8)] for i in range(8)]

def gioco(start):
	matrice = [[0 for j in range(8)] for i in range(8)]
	accesso = aggiorna_accesso(matrice)
	current = start[:]
	for i in range(1,64):
		if len(mosse_possibili(current, matrice)) == 0:
			print "Il giro si ferma dopo ", i, " movimenti"
			break
		else:
			accesso = aggiorna_accesso(matrice)
			matrice[current[0]][current[1]] = i
			possibili = mosse_possibili(current, matrice)
			appetibilita = [accesso[mossa[0]][mossa[1]] for mossa in possibili]
			minimo = min(appetibilita)
			appetibili = []
			for j in range(len(appetibilita)):
				if appetibilita[j] == minimo: 
					appetibili.append(j)
			scelta = random.randint(0,len(appetibili)-1)
			current = possibili[appetibili[scelta]][:]
	else:
		matrice[current[0]][current[1]] = 64
		print "Il cavallo ha compiuto tutti i 64 passi"
	return 1

start = [0,0]
gioco(start)