Solve a Holy Knight's tour

Solve a Holy Knight's tour
You are encouraged to solve this task according to the task description, using any language you may know.

Night's tours are similar to Hidato. When learning to play chess coaches torture (instruct) their charges by taking a chess board, placing some pennies on some squares and requiring that a Knight's tour is constructed which avoids squares with a penny on. The purpose of this task is to produce a solution to such problems. At least demonstrate you program by solving the following:

Example 1

  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

Extra credit is available for other interesting examples.

Ruby

This solution uses HLPsolver from here <lang ruby> require 'HLPsolver'

ADJACENT = [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]

boardy = <<EOS , . . 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

EOS t0 = Time.now HLPsolver.new(boardy).solve puts " #{Time.now - t0} sec" </lang>

Which produces:

Problem:
           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         

Solution:
           8 33 14            
          13     7 32         
        9 34 31 22 15  6 29   
    35 12 21       30    16   
    10    36       23 28  5   
     1 20 11 24 27  4 17      
           2 19    25         
             26  3 18         

 0.008917049 sec