
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


import sequtils, strformat
 
const Moves = [[-1, -2], [1, -2], [-2, -1], [2, -1], [-2, 1], [2, 1], [-1, 2], [1, 2]]
 
proc solve(pz: var seq[seq[int]]; sx, sy, idx, count: Natural): bool =
 
  if idx > count: return true
 
  var x, y: int
  for move in Moves:
    x = sx + move[0]
    y = sy + move[1]
    if x in 0..pz.high and y in 0..pz.high and pz[x][y] == 0:
      pz[x][y] = idx
      if pz.solve(x, y, idx + 1, count): return true
      pz[x][y] = 0
 
 
proc findSolution(board: openArray[string]) =
  let sz = board.len
  var pz = newSeqWith(sz, repeat(-1, sz))
 
  var count = 0
  var x, y: int
  for i in 0..<sz:
    for j in 0..<sz:
      case board[i][j]
      of 'x':
        pz[i][j] = 0
        inc count
      of 's':
        pz[i][j] = 1
        inc count
        (x, y) = (i, j)
      else:
        discard
 
  if pz.solve(x, y, 2, count):
    for i in 0..<sz:
      for j in 0..<sz:
        if pz[i][j] != -1:
          stdout.write &"{pz[i][j]:02}  "
        else:
          stdout.write "--  "
      stdout.write '\n'
 
when isMainModule:
 
  const
 
    Board1 = [" xxx    ",
              " x xx   ",
              " xxxxxxx",
              "xxx  x x",
              "x x  xxx",
              "sxxxxxx ",
              "  xx x  ",
              "   xxx  "]
 
    Board2 = [".....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....."]
 
  Board1.findSolution()
  echo()
  Board2.findSolution()