
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


V moves = [
    [-1, -2], [1, -2], [-1, 2], [1, 2],
    [-2, -1], [-2, 1], [2, -1], [2, 1]
]
 
F solve(&pz, sz, sx, sy, idx, cnt)
   I idx > cnt
      R 1
 
   L(i) 0 .< :moves.len
      V x = sx + :moves[i][0]
      V y = sy + :moves[i][1]
      I sz > x & x > -1 & sz > y & y > -1 & pz[x][y] == 0
         pz[x][y] = idx
         I 1 == solve(&pz, sz, x, y, idx + 1, cnt)
            R 1
         pz[x][y] = 0
   R 0
 
F find_solution(pz, sz)
   V p = [[-1] * sz] * sz
   V idx = 0
   V x = 0
   V y = 0
   V cnt = 0
   L(j) 0 .< sz
      L(i) 0 .< sz
         I pz[idx] == ‘x’
            p[i][j] = 0
            cnt++
         E I pz[idx] == ‘s’
            p[i][j] = 1
            cnt++
            x = i
            y = j
         idx++
 
   I 1 == solve(&p, sz, x, y, 2, cnt)
      L(j) 0 .< sz
         L(i) 0 .< sz
            I p[i][j] != -1
               print(‘ #02’.format(p[i][j]), end' ‘’)
            E
               print(‘   ’, end' ‘’)
         print()
   E
      print(‘Cannot solve this puzzle!’)
 
find_solution(‘.xxx.....x.xx....xxxxxxxxxx..x.xx.x..xxxsxxxxxx...xx.x.....xxx..’, 8)
print()
find_solution(‘.....s.x..........x.x.........xxxxx.........xxx.......x..x.x..x..xxxxx...xxxxx..xx.....xx..xxxxx...xxxxx..x..x.x..x.......xxx.........xxxxx.........x.x..........x.x.....’, 13)