The choices won't make sense unless I tell you the exact algorithm. First the list of neighbours in order of preference is as follows:

    [1,2], [-1,2], [1,-2], [-1,-2],
    [2,1], [-2,1], [2,-1], [-2,-1],

Where, for instance, [1,2] means 1 left and 2 down (if that is within the board. I then resort this list from fewest ways to reach a neighbour up. The sort is stable - ties will resolve in the above order.

The choice to backtrack is made when you move into square (1,2) (where move 64 will be) before the last move, or when there are 2 or more required moves (a required move is to move into a space other than (1,2) which can only be reached one other way, or to move to a space with no other ways of moving into it). If there is a required move, you only try it. If there isn't, then you try your neighbours in the order given above, exiting on success.

Here is the reasoning process used in generating the above solution (walk through the reasoning and compare with where the numbers go):

At call 1, depth 1, pos (0, 0)
At call 2, depth 2, pos (1, 2)
  Backtrack to depth 2, position (0, 0)
At call 3, depth 2, pos (2, 1)
At call 4, depth 3, pos (0, 2)
At call 5, depth 4, pos (1, 0)
At call 6, depth 5, pos (3, 1)
At call 7, depth 6, pos (5, 0)
At call 8, depth 7, pos (7, 1)
At call 9, depth 8, pos (6, 3)
At call 10, depth 9, pos (7, 5)
At call 11, depth 10, pos (6, 7)
At call 12, depth 11, pos (4, 6)
At call 13, depth 12, pos (2, 7)
At call 14, depth 13, pos (0, 6)
At call 15, depth 14, pos (1, 4)
At call 16, depth 15, pos (2, 6)
At call 17, depth 16, pos (0, 7)
At call 18, depth 17, pos (1, 5)
At call 19, depth 18, pos (0, 3)
At call 20, depth 19, pos (1, 1)
At call 21, depth 20, pos (3, 0)
At call 22, depth 21, pos (4, 2)
At call 23, depth 22, pos (2, 3)
At call 24, depth 23, pos (0, 4)
At call 25, depth 24, pos (1, 6)
At call 26, depth 25, pos (3, 7)
At call 27, depth 26, pos (2, 5)
At call 28, depth 27, pos (1, 7)
At call 29, depth 28, pos (0, 5)
At call 30, depth 29, pos (1, 3)
At call 31, depth 30, pos (0, 1)
At call 32, depth 31, pos (2, 2)
At call 33, depth 32, pos (3, 4)
At call 34, depth 33, pos (5, 5)
At call 35, depth 34, pos (4, 7)
At call 36, depth 35, pos (3, 5)
At call 37, depth 36, pos (5, 6)
At call 38, depth 37, pos (7, 7)
At call 39, depth 38, pos (6, 5)
At call 40, depth 39, pos (5, 7)
At call 41, depth 40, pos (7, 6)
At call 42, depth 41, pos (6, 4)
At call 43, depth 42, pos (7, 2)
At call 44, depth 43, pos (6, 0)
At call 45, depth 44, pos (5, 2)
At call 46, depth 45, pos (4, 4)
At call 47, depth 46, pos (3, 6)
At call 48, depth 47, pos (2, 4)
At call 49, depth 48, pos (1, 2)
  Backtrack to depth 48, position (2, 4)
At call 50, depth 48, pos (4, 3)
At call 51, depth 49, pos (5, 1)
At call 52, depth 50, pos (7, 0)
At call 53, depth 51, pos (6, 2)
At call 54, depth 52, pos (7, 4)
At call 55, depth 53, pos (6, 6)
At call 56, depth 54, pos (5, 4)
At call 57, depth 55, pos (7, 3)
At call 58, depth 56, pos (6, 1)
At call 59, depth 57, pos (4, 0)
At call 60, depth 58, pos (3, 2)
At call 61, depth 59, pos (2, 0)
At call 62, depth 60, pos (1, 2)
  Backtrack to depth 60, position (2, 0)
At call 63, depth 60, pos (4, 1)
At call 64, depth 61, pos (5, 3)
At call 65, depth 62, pos (4, 5)
At call 66, depth 63, pos (3, 3)
At call 67, depth 64, pos (1, 2)
SOLVED in 67 calls!

Erm, um. This means that the moves that confused you were generally not the backtracks. The condition to always go to the neighbour which can be reached in the fewest other ways forces most choices...

Cheers,
Ben