The knight's next tour

Question

We've all heard of the Knight's Tour puzzle: find a route for a knight that passes through all the squares on a chess board. But let's be honest, it's a little bit boring. So, let's give the knight a bit of a challenge.

Task

Write a program that takes the knight through all the squares on an arbitrary-sized, arbitrary-shaped chess board. It should take the chess board as input and output the set of moves and the starting position. In the event of an impossible board, it should output the set of moves and starting position for a tour with the longest possible length. Note: the knight doesn't need to take a round trip; assume (s)he has another way to get home.

Chess pieces are small, so your code needs to be small enough for the knight to carry around.

Input

The input will be a string-based or array-based representation of a chess board, where a non-blank / truthy value is a square, and a blank / falsy value is an empty space. For simplicity's sake I will use #s and s arranged in a grid for the examples.

Output

The output will be two large integers, followed by a series of 4-bit integers, or your language's equivalent. The two large integers will represent the starting co-ordinates, and the following numbers will represent a move like so:

 7 0
6   1
  K
5   2
 4 3

where K is the position before the move, and the number is the position after the move.

Examples

As there are a lot of possible solutions to the Knight's Tour puzzle, I will only provide example outputs. There may be more outputs.

###
# #
###
0 0 3 0 5 2 7 4 1

^{New challenge: Come up with more examples}

Answer 1

Mathematica, 151 bytes

Needs@"Combinatorica`"
{Reverse@#[[1]]-1,3-Floor[1.2Arg[Complex@@@Differences@#]]}&[#[[HamiltonianPath@MakeGraph[#,Norm[#-#2]^2==5&]]]&@Position[#,1]]&

Obviously, HamiltonianPath@MakeGraph[#,Norm[#-#2]^2==5&] does all the work.

Input is a 2D (0,1)-matrix like {{0,0,1},{1,1,1},{1,0,1},{1,1,1}}.

Output looks like this: {{2, 0}, {5, 3, 0, 5, 2, 7, 4, 1}}

I don't know a lot about Mathematica golf, so feel free to point out improvements. Is there a better way to save individual results than using a billion pure functions?

Saved a byte; thanks, CatsAreFluffy.