
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


9!:21]2^34
 
unpack=:verb define
  mask=. +./' '~:y
  board=. (255 0 1{a.) {~ {.@:>:@:"."0 mask#"1 y
)
 
ex1=:unpack ];._2]0 :0
  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
)
 
solve=:verb define
  board=.,:y
  for_move.1+i.+/({.a.)=,y do.
    board=. ;move <@knight"2 board
  end.
)
 
kmoves=: ,/(2 1,:1 2)*"1/_1^#:i.4
 
knight=:dyad define
  pos=. ($y)#:(,y)i.x{a.
  moves=. <"1(#~ 0&<: */"1@:* ($y)&>"1)pos+"1 kmoves
  moves=. (#~ (0{a.)={&y) moves
  moves y adverb def (':';'y x} m')"0 (x+1){a.
)