
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


#lang racket
(require "hidato-family-solver.rkt")
 
(define knights-neighbour-offsets
  '((+1 +2) (-1 +2) (+1 -2) (-1 -2) (+2 +1) (-2 +1) (+2 -1) (-2 -1)))
 
(define solve-a-knights-tour (solve-hidato-family knights-neighbour-offsets))
 
(displayln
 (puzzle->string
  (solve-a-knights-tour
   #(#(_ 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 _ _)))))
 
(newline)
 
(displayln
 (puzzle->string
  (solve-a-knights-tour
   #(#(- - - - - 1 - 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)
     #(- - 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 0 - - - -)
     #(- - - - - 0 - 0 - - - - -)
     #(- - - - - 0 - 0 - - - - -)))))