First imagine that the board is numbered (0,0) in the lower left hand corner, (7,0) in the upper left corner, and (7,7) in the upper right hand corner, when you orient the board playing black. (In fact the orientation doesn't matter, but this way we can be concrete.) Drop the knight on (2, 2) and flip that square accordingly. Then make the following 41 moves, flipping 3 squares per move:
1: (2, 1), (2, 0), (3, 0)
2: (3, 1), (3, 2), (4, 2)
3: (4, 1), (4, 0), (5, 0)
4: (6, 0), (7, 0), (7, 1)
5: (6, 1), (5, 1), (5, 2)
6: (6, 2), (7, 2), (7, 3)
7: (6, 3), (5, 3), (5, 4)
8: (6, 4), (7, 4), (7, 5)
9: (6, 5), (5, 5), (5, 6)
10: (6, 6), (7, 6), (7, 7)
11: (6, 7), (5, 7), (5, 6)
12: (4, 6), (4, 5), (4, 4)
13: (4, 3), (3, 3), (2, 3)
14: (1, 3), (1, 2), (1, 1)
15: (0, 1), (0, 2), (0, 3)
16: (0, 4), (1, 4), (2, 4)
17: (3, 4), (3, 5), (3, 6)
18: (3, 7), (2, 7), (1, 7)
19: (0, 7), (0, 6), (0, 5)
20: (1, 5), (2, 5), (2, 6)
21: (3, 6), (4, 6), (4, 7)
22: (4, 6), (3, 6), (2, 6)
23: (1, 6), (1, 5), (1, 4)
24: (1, 5), (1, 6), (2, 6)
25: (1, 6), (1, 5), (1, 4)
26: (1, 5), (2, 5), (3, 5)
27: (3, 6), (4, 6), (5, 6)
28: (4, 6), (3, 6), (3, 5)
29: (2, 5), (1, 5), (1, 6)
30: (1, 5), (1, 4), (0, 4)
31: (1, 4), (1, 5), (1, 6)
32: (1, 5), (1, 4), (0, 4)
33: (1, 4), (1, 3), (1, 2)
34: (1, 1), (1, 0), (0, 0)
35: (0, 1), (1, 1), (2, 1)
36: (1, 1), (1, 2), (1, 3)
37: (1, 2), (1, 1), (2, 1)
38: (1, 1), (0, 1), (0, 2)
39: (1, 2), (1, 1), (1, 0)
40: (0, 0), (0, 1), (0, 2)
41: (0, 1), (0, 0), (1, 0)
This solution is due to Michael Birken. He describes his approach as follows.
"I used a greedy search that started the tour in the middle and advanced it on both ends. The queue was sorted by total number of flips, by path length and by entropy (where entropy--a.k.a. disorder--is a function that estimates the number of islands that the tour failed to cover).
"The search naturally turns into two phases. In the first phase, after the seed position of the knight is chosen randomly, a partial tour is formed around the seed, creating a blob of flipped squares. The search will never get a chance to backtrack into the blob; so, it is important that the blob is as compact as possible with the fewest number of unflipped islands. The second phase is the backtracking phase where the search explores the remaining unflipped squares that are outside of the blob. If the program could run for an indefinite amount of time, then there would only be the backtracking phase, but in reality, little search can be done directly around the seed."
This is a very clever solution, but note that certain squares are hit many times. For example, (1,5) is hit 9 times. I wonder if you can do better.
