Solve a Holy Knight's tour: Difference between revisions

From Rosetta Code
Content added Content deleted
No edit summary
(extra problem added)
Line 240: Line 240:
{
{
int wid; string p;
int wid; string p;
p = "* . . . * * * * * . * . . * * * * . . . . . . . . . . * * . * . . * . * * . . . 1 . . . . . . * * * . . * . * * * * * . . . * *"; wid = 8;
//p = "* . . . * * * * * . * . . * * * * . . . . . . . . . . * * . * . . * . * * . . . 1 . . . . . . * * * . . * . * * * * * . . . * *"; wid = 8;
p = "* * * * * 1 * . * * * * * * * * * * . * . * * * * * * * * * . . . . . * * * * * * * * * . . . * * * * * * * . * * . * . * * . * * . . . . . * * * . . . . . * * . . * * * * * . . * * . . . . . * * * . . . . . * * . * * . * . * * . * * * * * * * . . . * * * * * * * * * . . . . . * * * * * * * * * . * . * * * * * * * * * * . * . * * * * * "; wid = 13;
istringstream iss( p ); vector<string> puzz;
istringstream iss( p ); vector<string> puzz;
copy( istream_iterator<string>( iss ), istream_iterator<string>(), back_inserter<vector<string> >( puzz ) );
copy( istream_iterator<string>( iss ), istream_iterator<string>(), back_inserter<vector<string> >( puzz ) );
Line 270: Line 271:
36 23 09
36 23 09
04 35 22
04 35 22

01 05
10 12
02 13 04 09 06
08 11 14
34 03 07 16
7 30 39 28 35 15 56 49 54 51
36 33 17 52
1 38 29 40 27 19 48 55 50 53
32 41 47 18
26 23 20
42 21 44 25 46
24 22
43 45
</pre>
</pre>


Revision as of 12:17, 22 October 2014

Task
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.

Ada

This solution uses the package Knights_Tour from Knight's Tour#Ada. The board is quadratic, the size of the board is read from the command line and the board itself is read from the standard input. For the board itself, Space and Minus indicate a no-go (i.e., a coin on the board), all other characters represent places the knight must visit. A '1' represents the start point. Ill-formatted input will crash the program.

<lang Ada>with Knights_Tour, Ada.Text_IO, Ada.Command_Line;

procedure Holy_Knight is 

  Size: Positive := Positive'Value(Ada.Command_Line.Argument(1));
  package KT is new Knights_Tour(Size => Size);
  Board: KT.Tour := (others => (others => Natural'Last));
  
  Start_X, Start_Y: KT.Index:= 1; -- default start place (1,1)
  S: String(KT.Index);
  I: Positive := KT.Index'First;

begin 

  -- read the board from standard input
  while not Ada.Text_IO.End_Of_File and I <= Size loop
     S := Ada.Text_IO.Get_Line; 
     for J in KT.Index loop
        if S(J) = ' ' or S(J) = '-' then
           Board(I,J) := Natural'Last;
        elsif S(J) = '1' then 
             Start_X := I; Start_Y := J;  Board(I,J) := 1;
        else Board(I,J) := 0;
        end if;
     end loop;
     I := I + 1;
  end loop;

  -- print the board
  Ada.Text_IO.Put_Line("Start Configuration (Length:" 
                         & Natural'Image(KT.Count_Moves(Board)) & "):");
  KT.Tour_IO(Board, Width => 1);
  Ada.Text_IO.New_Line;

  -- search for the tour and print it
  Ada.Text_IO.Put_Line("Tour:");
  KT.Tour_IO(KT.Warnsdorff_Get_Tour(Start_X, Start_Y, Board));

end Holy_Knight;</lang>

Output:
>holy_knight 8 < standard_problem.txt
Start Configuration (Length: 36):
--000---
--0-00--
-0000000
000--0-0
0-0--000
1000000-
--00-0--
---000--

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


Extra Credit

The Holy_Knight program can immediately be used to tackle "more interesting" problems, such as those from New Knight's Tour Puzzles and Graphs. Here is one sample solution: 

>holy_knight 13 < problem10.txt
Start Configuration (Length: 56):
-----1-0-----
-----0-0-----
----00000----
-----000-----
--0--0-0--0--
00000---00000
--00-----00--
00000---00000
--0--0-0--0--
-----000-----
----00000----
-----0-0-----
-----0-0-----

Tour:
   -   -   -   -   -   1   -  27   -   -   -   -   -
   -   -   -   -   -  56   -   2   -   -   -   -   -
   -   -   -   -  24   3  28  55  26   -   -   -   -
   -   -   -   -   -  54  25   4   -   -   -   -   -
   -   -  50   -   -  23   -  29   -   -   6   -   -
  51  20  47  22  53   -   -   -   5  30   9  32   7
   -   -  52  49   -   -   -   -   -  33  36   -   -
  19  48  21  46  17   -   -   -  37  10  31   8  35
   -   -  18   -   -  45   -  11   -   -  34   -   -
   -   -   -   -   -  16  41  38   -   -   -   -   -
   -   -   -   -  42  39  44  15  12   -   -   -   -
   -   -   -   -   -  14   -  40   -   -   -   -   -
   -   -   -   -   -  43   -  13   -   -   -   -   -


C++

<lang cpp>

  1. include <vector>
  2. include <sstream>
  3. include <iostream>
  4. include <iterator>
  5. include <stdlib.h>
  6. include <string.h>

using namespace std;

struct node { 

   int val;
   unsigned char neighbors;

};

class nSolver { public: 

   nSolver()
   {

dx[0] = -1; dy[0] = -2; dx[1] = -1; dy[1] = 2; dx[2] = 1; dy[2] = -2; dx[3] = 1; dy[3] = 2; dx[4] = -2; dy[4] = -1; dx[5] = -2; dy[5] = 1; dx[6] = 2; dy[6] = -1; dx[7] = 2; dy[7] = 1; 

   }

   void solve( vector<string>& puzz, int max_wid )
   {

if( puzz.size() < 1 ) return; wid = max_wid; hei = static_cast<int>( puzz.size() ) / wid; int len = wid * hei, c = 0; max = len; arr = new node[len]; memset( arr, 0, len * sizeof( node ) );

for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ ) { if( ( *i ) == "*" ) { max--; arr[c++].val = -1; continue; } arr[c].val = atoi( ( *i ).c_str() ); c++; }

solveIt(); c = 0; for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ ) { if( ( *i ) == "." ) { ostringstream o; o << arr[c].val; ( *i ) = o.str(); } c++; } delete [] arr; 

   }

private: 

   bool search( int x, int y, int w )
   {

if( w > max ) return true;

node* n = &arr[x + y * wid]; n->neighbors = getNeighbors( x, y );

for( int d = 0; d < 8; d++ ) { if( n->neighbors & ( 1 << d ) ) { int a = x + dx[d], b = y + dy[d]; if( arr[a + b * wid].val == 0 ) { arr[a + b * wid].val = w; if( search( a, b, w + 1 ) ) return true; arr[a + b * wid].val = 0; } } } return false; 

   }

   unsigned char getNeighbors( int x, int y )
   {

unsigned char c = 0; int a, b; for( int xx = 0; xx < 8; xx++ ) { a = x + dx[xx], b = y + dy[xx]; if( a < 0 || b < 0 || a >= wid || b >= hei ) continue; if( arr[a + b * wid].val > -1 ) c |= ( 1 << xx ); } return c; 

   }

   void solveIt()
   {

int x, y, z; findStart( x, y, z ); if( z == 99999 ) { cout << "\nCan't find start point!\n"; return; } search( x, y, z + 1 ); 

   }

   void findStart( int& x, int& y, int& z )
   {

z = 99999; for( int b = 0; b < hei; b++ ) for( int a = 0; a < wid; a++ ) if( arr[a + wid * b].val > 0 && arr[a + wid * b].val < z ) { x = a; y = b; z = arr[a + wid * b].val; } 

   }

   int wid, hei, max, dx[8], dy[8];
   node* arr;

};

int main( int argc, char* argv[] ) { 

   int wid; string p;
   //p = "* . . . * * * * * . * . . * * * * . . . . . . . . . . * * . * . . * . * * . . . 1 . . . . . . * * * . . * . * * * * * . . . * *"; wid = 8;
   p = "* * * * * 1 * . * * * * * * * * * * . * . * * * * * * * * * . . . . . * * * * * * * * * . . . * * * * * * * . * * . * . * * . * * . . . . . * * * . . . . . * * . . * * * * * . . * * . . . . . * * * . . . . . * * . * * . * . * * . * * * * * * * . . . * * * * * * * * * . . . . . * * * * * * * * * . * . * * * * * * * * * * . * . * * * * * "; wid = 13;
   istringstream iss( p ); vector<string> puzz;
   copy( istream_iterator<string>( iss ), istream_iterator<string>(), back_inserter<vector<string> >( puzz ) );
   nSolver s; s.solve( puzz, wid );
   int c = 0;
   for( vector<string>::iterator i = puzz.begin(); i != puzz.end(); i++ )
   {

if( ( *i ) != "*" && ( *i ) != "." ) { if( atoi( ( *i ).c_str() ) < 10 ) cout << "0"; cout << ( *i ) << " "; 

       }

else cout << " "; if( ++c >= wid ) { cout << endl; c = 0; } 

   }
   cout << endl << endl;
   return system( "pause" );

} </lang>

Output:
   17 14 29
   28    18 15
   13 16 27 30 19 32 07
25 02 11       06    20
12    26       31 08 33
01 24 03 10 05 34 21
      36 23    09
         04 35 22

              01    05
              10    12
           02 13 04 09 06
              08 11 14
     34       03    07       16
7 30 39 28 35          15 56 49 54 51
     36 33                17 52
1 38 29 40 27          19 48 55 50 53
     32       41    47       18
              26 23 20
           42 21 44 25 46
              24    22
              43    45

Icon and Unicon

This is a Unicon-specific solution: <lang unicon>global nCells, cMap, best record Pos(r,c)

procedure main(A) 

   puzzle := showPuzzle("Input",readPuzzle())
   QMouse(puzzle,findStart(puzzle),&null,0)
   showPuzzle("Output", solvePuzzle(puzzle)) | write("No solution!")

end

procedure readPuzzle() 

   # Start with a reduced puzzle space
   p := [[-1],[-1]]
   nCells := maxCols := 0
   every line := !&input do {
       put(p,[: -1 | -1 | gencells(line) | -1 | -1 :])
       maxCols <:= *p[-1]
       }
   every put(p, [-1]|[-1])
   # Now normalize all rows to the same length
   every i := 1 to *p do p[i] := [: !p[i] | (|-1\(maxCols - *p[i])) :]
   return p

end

procedure gencells(s) 

   static WS, NWS
   initial {
       NWS := ~(WS := " \t")
       cMap := table()     # Map to/from internal model
       cMap["#"] := -1;  cMap["_"] :=  0
       cMap[-1]  := " "; cMap[0]   := "_"
       }

   s ? while not pos(0) do {
           w := (tab(many(WS))|"", tab(many(NWS))) | break
           w := numeric(\cMap[w]|w)
           if -1 ~= w then nCells +:= 1
           suspend w
           }

end

procedure showPuzzle(label, p) 

   write(label," with ",nCells," cells:")
   every r := !p do {
       every c := !r do writes(right((\cMap[c]|c),*nCells+1))
       write()
       }
   return p

end

procedure findStart(p) 

   if \p[r := !*p][c := !*p[r]] = 1 then return Pos(r,c)

end

procedure solvePuzzle(puzzle) 

   if path := \best then {
       repeat {
           loc := path.getLoc()
           puzzle[loc.r][loc.c] := path.getVal()
           path := \path.getParent() | break
           }
       return puzzle
       }

end

class QMouse(puzzle, loc, parent, val) 

   method getVal(); return val; end
   method getLoc(); return loc; end
   method getParent(); return parent; end
   method atEnd(); return nCells = val; end

   method visit(r,c)
       if /best & validPos(r,c) then return Pos(r,c)
   end

   method validPos(r,c)
       v := val+1
       xv := (0 <= puzzle[r][c]) | fail
       if xv = (v|0) then {  # make sure this path hasn't already gone there
           ancestor := self
           while xl := (ancestor := \ancestor.getParent()).getLoc() do
               if (xl.r = r) & (xl.c = c) then fail
           return
           }
   end

initially 

   val := val+1
   if atEnd() then return best := self
   QMouse(puzzle, visit(loc.r-2,loc.c-1), self, val)
   QMouse(puzzle, visit(loc.r-2,loc.c+1), self, val)
   QMouse(puzzle, visit(loc.r-1,loc.c+2), self, val)
   QMouse(puzzle, visit(loc.r+1,loc.c+2), self, val)
   QMouse(puzzle, visit(loc.r+2,loc.c+1), self, val)
   QMouse(puzzle, visit(loc.r+2,loc.c-1), self, val)
   QMouse(puzzle, visit(loc.r+1,loc.c-2), self, val)
   QMouse(puzzle, visit(loc.r-1,loc.c-2), self, val)

end</lang>

Sample run: 

->hkt <hkt.in
Input with 36 cells:
                                    
                                    
           _  _  _                  
           _     _  _               
           _  _  _  _  _  _  _      
        _  _  _        _     _      
        _     _        _  _  _      
        1  _  _  _  _  _  _         
              _  _     _            
                 _  _  _            
                                    
                                    
Output with 36 cells:
                                    
                                    
          19  4 13                  
          12    18  5               
          25 20  3 14 17  6 31      
       21  2 11       32    16      
       26    24       15 30  7      
        1 22 27 10 35  8 33         
             36 23    29            
                28  9 34            
                                    
                                    
->

Perl 6

Using the Warnsdorff algorithm from Solve_a_Hidato_puzzle. <lang perl6>my @adjacent = 

              [ -2, -1],  [ -2, 1],
     [-1,-2],                       [-1,+2],
     [+1,-2],                       [+1,+2],
              [ +2, -1],  [ +2, 1];

solveboard q:to/END/; 

   . 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
   END</lang>
Output:
   25 14 27
   36    24 15
   31 26 13 28 23  6 17
35 12 29       16    22
30    32        7 18  5
 1 34 11  8 19  4 21
       2 33     9
         10  3 20
84 tries

Racket

This solution uses the module "hidato-family-solver.rkt" from Solve a Numbrix puzzle#Racket. The difference between the two is essentially the neighbourhood function.

It solves the tasked problem, as well as the "extra credit" from #Ada.

<lang racket>#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 - - - - -)))))</lang>
Output:
 _ 13 30 23  _  _  _  _
 _ 24  _ 14 31  _  _  _
 _ 29 12 25 22 15 32  7
11 26 21  _  _  6  _ 16
28  _ 10  _  _ 33  8  5
 1 20 27 34  9  4 17  _
 _  _  2 19  _ 35  _  _
 _  _  _ 36  3 18  _  _

  _   _   _   _   _   1   _  51   _   _   _   _   _
  _   _   _   _   _  50   _   2   _   _   _   _   _
  _   _   _   _  56   3  52  49  54   _   _   _   _
  _   _   _   _   _  48  55   4   _   _   _   _   _
  _   _  46   _   _   5   _  53   _   _  24   _   _
 45   8  11   6  47   _   _   _  23  30  19  28  21
  _   _  44   9   _   _   _   _   _  25  22   _   _
 43  10   7  12  41   _   _   _  31  18  29  20  27
  _   _  42   _   _  13   _  17   _   _  26   _   _
  _   _   _   _   _  40  37  32   _   _   _   _   _
  _   _   _   _  36  33  14  39  16   _   _   _   _
  _   _   _   _   _  38   _  34   _   _   _   _   _
  _   _   _   _   _  35   _  15   _   _   _   _   _

REXX

This REXX program is essentially a modified   knight's tour   REXX program with support to place pennies on the chessboard.
Also supported is the specification of the size of the chessboard and the placement of the knight (initial position). <lang rexx>/*REXX pgm solves the holy knight's tour problem for a NxN chessboard.*/ blank=pos('//',space(arg(1),0))\==0 /*see if pennies are to be shown.*/ parse arg ops '/' cent /*obtain the options and pennies.*/ parse var ops N sRank sFile . /*boardsize, starting pos, pennys*/ if N== | N==',' then N=8 /*Boardsize specified? Default. */ if sRank== then sRank=N /*starting rank given? Default. */ if sFile== then sFile=1 /* " file " " */ NN=N**2; NxN='a ' N"x"N ' chessboard' /* [↓] r=Rank, f=File.*/ @.=; do r=1 for N; do f=1 for N; @.r.f=' '; end /*f*/; end /*r*/ 

                                      /*[↑]  blank the  NxN chessboard.*/

cent=space(translate(cent,,',')) /*allow use of comma (,) for sep.*/ cents=0 /*number of pennies on chessboard*/ 

      do  while  cent\=             /* [↓]  possibly place pennies.  */
      parse var cent cr cf x '/' cent /*extract where to place pennies.*/
      if x=   then x=1              /*if # not specified, use 1 penny*/
      if cr=  then iterate          /*support the "blanking" option. */
        do cf=cf for x                /*now, place  X  pennies on board*/
        @.cr.cf='¢'                   /*mark board position with penny.*/
        end   /*cf*/                  /* [↑]  places X pennies on board*/
      end     /*while cent¬= */     /* [↑]  allows of placing  X  ¢s.*/
                                      /* [↓]  traipse through the board*/
 do r=1  for N;  do f=1  for N;   cents=cents+(@.r.f=='¢');   end;   end
                                      /* [↑]  count number of pennies. */

if cents\==0 then say cents 'pennies placed on chessboard.' target=NN-cents /*use this as the number of moves*/ Kr = '2 1 -1 -2 -2 -1 1 2' /*legal "rank" move for a knight.*/ Kf = '1 2 2 1 -1 -2 -2 -1' /* " "file" " " " " */ 

                            do i=1  for words(Kr)  /*legal knight moves*/
                            Kr.i = word(Kr,i);     Kf.i = word(Kf,i)
                            end    /*i*/           /*for fast indexing.*/

!=left(, 9*(n<18)) /*used for indentation of board. */ if @.sRank.sFile==' ' then @.sRank.sFile=1 /*knight's starting pos*/ if @.sRank.sFile\==1 then do sRank=1 for N /*find a starting rank.*/ 

                            do sFile=1  for N   /*  "  "    "     file.*/
                            if @.sRank.sFile==' ' then do  /*got a spot*/
                                                       @.sRank.sFile=1
                                                       leave sRank
                                                       end
                            end   /*sRank*/
                          end     /*sFile*/

if \move(2,sRank,sFile) & , 

  \(N==1)  then say "No holy knight's tour solution for" NxN'.'
           else say "A solution for the holy knight's tour on" NxN':'

_=substr(copies("┼───",N),2); say; say  ! translate('┌'_"┐", '┬', "┼") 

    do   r=N  for N  by -1;           if r\==N  then say ! '├'_"┤";  L=@.
      do f=1  for N;     L=L'│'centre(@.r.f,3)   /*preserve squareness.*/
      end      /*f*/
    if blank then L=translate(L,,'¢') /*blank out the pennies ?        */
    say ! L'│'                        /*show a  rank of the chessboard.*/
    end        /*r*/                  /*80 cols can view 19x19 chessbrd*/

say  ! translate('└'_"┘", '┴', "┼") /*show the last rank of the board*/ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────MOVE subroutine─────────────────────*/ move: procedure expose @. Kr. Kf. N target; parse arg #,rank,file; b=' ' 

        do t=1  for 8;      nr=rank+Kr.t;      nf=file+Kf.t
        if @.nr.nf==b  then do;                @.nr.nf=#     /*Kn move.*/
                            if #==target       then return 1 /*last mv?*/
                            if move(#+1,nr,nf) then return 1
                            @.nr.nf=b          /*undo the above move.  */
                            end                /*try different move.   */
        end   /*t*/

return 0 /*the tour not possible.*/</lang> output when the following is used for input:
, 3 1 /1,1 3 /1,7 2 /2,1 2 /2,5 /2,8 /3,8 /4,2 /4,4 2 /5,4 2 /5,6 /6,1 /7,1 2 /7,4 /7,7 1 /8,1 2 /8,6 3 

26 pennies placed on chessboard.
A solution for the knight's tour on a  8x8  chessboard:

          ┌───┬───┬───┬───┬───┬───┬───┬───┐
          │ ¢ │ ¢ │26 │35 │ 4 │ ¢ │ ¢ │ ¢ │
          ├───┼───┼───┼───┼───┼───┼───┼───┤
          │ ¢ │ ¢ │ 3 │ ¢ │25 │16 │ ¢ │ 6 │
          ├───┼───┼───┼───┼───┼───┼───┼───┤
          │ ¢ │27 │36 │17 │34 │ 5 │24 │15 │
          ├───┼───┼───┼───┼───┼───┼───┼───┤
          │37 │ 2 │33 │ ¢ │ ¢ │ ¢ │ 7 │22 │
          ├───┼───┼───┼───┼───┼───┼───┼───┤
          │28 │ ¢ │18 │ ¢ │ ¢ │23 │14 │ 9 │
          ├───┼───┼───┼───┼───┼───┼───┼───┤
          │ 1 │38 │29 │32 │13 │ 8 │21 │ ¢ │
          ├───┼───┼───┼───┼───┼───┼───┼───┤
          │ ¢ │ ¢ │12 │19 │ ¢ │31 │10 │ ¢ │
          ├───┼───┼───┼───┼───┼───┼───┼───┤
          │ ¢ │ ¢ │ ¢ │30 │11 │20 │ ¢ │ ¢ │
          └───┴───┴───┴───┴───┴───┴───┴───┘

output when the following is used for input:
, 3 1 /1,1 3 /1,7 2 /2,1 2 /2,5 /2,8 /3,8 /4,2 /4,4 2 /5,4 2 /5,6 /6,1 /7,1 2 /7,4 /7,7 1 /8,1 2 /8,6 3 // 

26 pennies placed on chessboard.
A solution for the knight's tour on a  8x8  chessboard:

          ┌───┬───┬───┬───┬───┬───┬───┬───┐
          │   │   │26 │35 │ 4 │   │   │   │
          ├───┼───┼───┼───┼───┼───┼───┼───┤
          │   │   │ 3 │   │25 │16 │   │ 6 │
          ├───┼───┼───┼───┼───┼───┼───┼───┤
          │   │27 │36 │17 │34 │ 5 │24 │15 │
          ├───┼───┼───┼───┼───┼───┼───┼───┤
          │37 │ 2 │33 │   │   │   │ 7 │22 │
          ├───┼───┼───┼───┼───┼───┼───┼───┤
          │28 │   │18 │   │   │23 │14 │ 9 │
          ├───┼───┼───┼───┼───┼───┼───┼───┤
          │ 1 │38 │29 │32 │13 │ 8 │21 │   │
          ├───┼───┼───┼───┼───┼───┼───┼───┤
          │   │   │12 │19 │   │31 │10 │   │
          ├───┼───┼───┼───┼───┼───┼───┼───┤
          │   │   │   │30 │11 │20 │   │   │
          └───┴───┴───┴───┴───┴───┴───┴───┘

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.005 sec

Tcl

Works with: Tcl version 8.6

<lang tcl>package require Tcl 8.6

oo::class create HKTSolver { 

   variable grid start limit
   constructor {puzzle} {

set grid $puzzle for {set y 0} {$y < [llength $grid]} {incr y} { for {set x 0} {$x < [llength [lindex $grid $y]]} {incr x} { if {[set cell [lindex $grid $y $x]] == 1} { set start [list $y $x] } incr limit [expr {$cell>=0}] } } if {![info exist start]} { return -code error "no starting position found" } 

   }
   method moves {} {

return { -1 -2 1 -2 -2 -1 2 -1 -2 1 2 1 -1 2 1 2 } 

   }
   method Moves {g r c} {

set valid {} foreach {dr dc} [my moves] { set R [expr {$r + $dr}] set C [expr {$c + $dc}] if {[lindex $g $R $C] == 0} { lappend valid $R $C } } return $valid 

   }

   method Solve {g r c v} {

lset g $r $c [incr v] if {$v >= $limit} {return $g} foreach {r c} [my Moves $g $r $c] { return [my Solve $g $r $c $v] } return -code continue 

   }

   method solve {} {

while {[incr i]==1} { set grid [my Solve $grid {*}$start 0] return } return -code error "solution not possible" 

   }
   method solution {} {return $grid}

}

proc parsePuzzle {str} { 

   foreach line [split $str "\n"] {

if {[string trim $line] eq ""} continue lappend rows [lmap {- c} [regexp -all -inline {(.)\s?} $line] { string map {" " -1} $c }] 

   }
   set len [tcl::mathfunc::max {*}[lmap r $rows {llength $r}]]
   for {set i 0} {$i < [llength $rows]} {incr i} {

while {[llength [lindex $rows $i]] < $len} { lset rows $i end+1 -1 } 

   }
   return $rows

} proc showPuzzle {grid name} { 

   foreach row $grid {foreach cell $row {incr c [expr {$cell>=0}]}}
   set len [string length $c]
   set u [string repeat "_" $len]
   puts "$name with $c cells"
   foreach row $grid {

puts [format " %s" [join [lmap c $row { format "%*s" $len [if {$c==-1} list elseif {$c==0} {set u} {set c}] }]]] 

   }

}

set puzzle [parsePuzzle { 

 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

}] showPuzzle $puzzle "Input" HKTSolver create hkt $puzzle hkt solve showPuzzle [hkt solution] "Output"</lang>

Output:
Input with 36 cells
     __ __ __            
     __    __ __         
     __ __ __ __ __ __ __
  __ __ __       __    __
  __    __       __ __ __
   1 __ __ __ __ __ __   
        __ __    __      
           __ __ __      
Output with 36 cells
     13  6 15            
      8    12 31         
      5 14  7 16 27 32 29
   9  2 11       30    26
   4    22       17 28 33
   1 10  3 18 21 34 25   
        36 23    19      
           20 35 24
Retrieved from "https://rosettacode.org/wiki/Solve_a_Holy_Knight%27s_tour?oldid=247405"