
Chess coaches have been known to inflict a kind of torture on beginners by taking a chess board, placing pennies on some squares and requiring that a Knight's tour be constructed that avoids the squares with pennies.

This kind of knight's tour puzzle is similar to   Hidato.

The present task is to produce a solution to such problems. At least demonstrate your program by solving the following:



Example

  0 0 0 
  0   0 0 
  0 0 0 0 0 0 0
0 0 0     0   0
0   0     0 0 0
1 0 0 0 0 0 0
    0 0   0
      0 0 0

Note that the zeros represent the available squares, not the pennies.

Extra credit is available for other interesting examples.



Related tasks

 A* search algorithm
 Knight's tour
 N-queens problem
 Solve a Hidato puzzle
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


puzzle = "  0 0 0 
  0   0 0 
  0 0 0 0 0 0 0
0 0 0     0   0
0   0     0 0 0
1 0 0 0 0 0 0
    0 0   0
      0 0 0";
puzzle = StringSplit[puzzle, "\n"];
puzzle = StringTake[#, {1, -1, 2}] & /@ puzzle;
pos0 = Join @@ Table[{i, #} & /@ StringPosition[puzzle[[i]], "0"][[All, 1]], {i, Length@puzzle}];
pos1 = Join @@ Table[{i, #} & /@ StringPosition[puzzle[[i]], "1"][[All, 1]], {i, Length@puzzle}];
 
allpoints = Join[pos1, pos0];
validmoves = Select[Subsets[allpoints, {2}], Differences /* Norm /* EqualTo[Sqrt[5]]];
g = Graph[UndirectedEdge @@@ validmoves];
e = VertexList[g];
order = FindShortestTour[g][[2]]
Graphics[{Red, Disk[#, 0.2] & /@ e, Black, BlockMap[Arrow, e[[order]], 2, 1]}]