Knights tour (On 8 * 8 Chessboard) using simple backtracking and no heuristic. To make it generate different solution I have randomized the part where it selects the next possible move.

knights_tour_randomized.py

"""
Knights tour (On 8 * 8 Chessboard) using simple backtracking and no heuristic. 
To make it generate different solutions I have randomized the part where it selects the next possible move.
"""
import itertools
import random

N = 8
N2 = N*N

class KnightTourRandomized(object):
    def __init__(self):
        self._path = [[False for j in range(0, N)] for i in range(0, N)]
        self._pm = list(itertools.chain(itertools.product((1, -1), (2, -2)), itertools.product((2, -2), (1, -1))))

    def get_paths(self, max_paths=1):
        """
        Generator that returns different possible solution paths (Mostly it should be different every time 
        but not necessoary).
    
        """

        for i in range(0, max_paths):
            self.reset()
            self.calculate_path()
            yield self.get_path()

    def _is_valid_move(self, x, y):
        return (x>-1 and y>-1 and x<N and y<N and self._path[x][y] == False)

    def reset(self):
        self._path = [[False for j in range(0, N)] for i in range(0, N)]
    
    def recur(self, x, y, movn):
        res = False
        self._path[x][y] = movn
        if movn == 60:
		    print 60, self._path

        if movn == N2:
            return True

        for (xm, ym) in random.sample(self._pm, len(self._pm)):
            if self._is_valid_move(x+xm, y+ym):
                res = res or self.recur(x+xm, y+ym, movn + 1)

        if res == False:
            self._path[x][y] = False
        return res

    def calculate_path(self):
        self.recur(0, 0, 1)
        
    def get_path(self):
        return self._path

obj = KnightTourRandomized()
obj.calculate_path()
print obj.get_path()

Code is running now but I think I may need to search using some heuristic to make it run in less time.