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 gioco(start):
	matrice = [[0 for j in range(8)] for i in range(8)]
	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:
			matrice[current[0]][current[1]] = i
			possibili = mosse_possibili(current, matrice)
			scelta = random.randint(0,len(possibili)-1)
			current = possibili[scelta][:]
	else:
		matrice[current[0]][current[1]] = 64
		print "Il cavallo ha compiuto tutti i 64 passi"
	return matrice

start = [0,0]
gioco(start)