The running time of a simple backtracking search will depend on the move search order you use.

For example, this order:

moves = [ a, e, f, b, c, g, h, d ]
  where a = (1,-2)
        b = (1,2)
        c = (-1,2)
        d = (-1,-2)
        e = (2,1)
        f = (2,-1)
        g = (-2,1)
        h = (-2,-1)

works great for n = 7, but not 6 or 8.