Source code in the ada programming language

generic
   Size: Integer;
package Knights_Tour is
 
   subtype Index is Integer range 1 .. Size;
   type Tour is array  (Index, Index) of Natural;
   Empty: Tour := (others => (others => 0));
   
   function Get_Tour(Start_X, Start_Y: Index; Scene: Tour := Empty) return Tour;
   -- finds tour via backtracking
   -- either no tour has been found, i.e., Get_Tour returns Scene
   -- or the Result(X,Y)=K if and only if I,J is visited at the K-th move
   -- for all X, Y, Scene(X,Y) must be either 0 or Natural'Last,
   --   where Scene(X,Y)=Natural'Last means "don't visit coordiates (X,Y)!"
 
   function Count_Moves(Board: Tour) return Natural;
   -- counts the number of possible moves, i.e., the number of 0's on the board
   
   procedure Tour_IO(The_Tour: Tour; Width: Natural := 4);
   -- writes The_Tour to the output using Ada.Text_IO;
      
end Knights_Tour;


with Ada.Text_IO, Ada.Integer_Text_IO;
 
package body Knights_Tour is
 
 
   type Pair is array(1..2) of Integer;
   type Pair_Array is array (Positive range <>) of Pair;
 
   Pairs: constant Pair_Array (1..8)
     := ((-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1));
   -- places for the night to go (relative to the current position)
   
   function Count_Moves(Board: Tour) return Natural is
      N: Natural := 0;
   begin
      for I in Index loop
	 for J in Index loop
	    if Board(I,J) < Natural'Last then 
	       N := N + 1; 
	    end if;
	 end loop;
      end loop;
      return N;
   end Count_Moves;
   
   function Get_Tour(Start_X, Start_Y: Index; Scene: Tour := Empty) 
		    return Tour is
      Done: Boolean;
      Move_Count: Natural := Count_Moves(Scene);
      Visited: Tour;

      -- Visited(I, J) = 0: not yet visited
      -- Visited(I, J) = K: visited at the k-th move
      -- Visited(I, J) = Integer'Last: never visit
 
      procedure Visit(X, Y: Index; Move_Number: Positive; Found: out Boolean) is
         XX, YY: Integer;
      begin
         Found := False;
         Visited(X, Y) := Move_Number;
         if Move_Number = Move_Count then
            Found := True;
         else
            for P in Pairs'Range loop
               XX := X + Pairs(P)(1);
               YY := Y + Pairs(P)(2);
               if (XX in Index) and then (YY in Index)
                                and then Visited(XX, YY) = 0 then
                  Visit(XX, YY, Move_Number+1, Found); -- recursion
                  if Found then
                     return; -- no need to search further
                  end if;
               end if;
            end loop;
            Visited(X, Y) := 0; -- undo previous mark
         end if;
      end Visit;
 
   begin
      Visited := Scene;
      Visit(Start_X, Start_Y, 1, Done);
      if not Done then
         Visited := Scene;
      end if;
      return Visited;
   end Get_Tour;
  
   procedure Tour_IO(The_Tour: Tour; Width: Natural := 4) is
   begin
      for I in Index loop
         for J in Index loop
	    if The_Tour(I, J) < Integer'Last then
	       Ada.Integer_Text_IO.Put(The_Tour(I, J), Width);
	    else
	       for W in 1 .. Width-1 loop
		  Ada.Text_IO.Put(" ");
	       end loop;
	       Ada.Text_IO.Put("-"); -- deliberately not visited
	    end if;
         end loop;
         Ada.Text_IO.New_Line;
      end loop;
   end Tour_IO;
 
end Knights_Tour;


with Knights_Tour, Ada.Command_Line;

procedure Test_Knight is

   Size: Positive := Positive'Value(Ada.Command_Line.Argument(1));

   package KT is new Knights_Tour(Size => Size);

begin
   KT.Tour_IO(KT.Get_Tour(1, 1));
end Test_Knight;


   
   function Warnsdorff_Get_Tour(Start_X, Start_Y: Index; Scene: Tour := Empty) 
			       return Tour;
   -- uses Warnsdorff heurisitic to find a tour faster
   -- same interface as Get_Tour


   function Warnsdorff_Get_Tour(Start_X, Start_Y: Index;  Scene: Tour := Empty)
			       return Tour is
      Done: Boolean;
      Visited: Tour; -- see comments from Get_Tour above
      Move_Count: Natural := Count_Moves(Scene);
 
      function Neighbors(X, Y: Index) return Natural is
         Result: Natural := 0;
      begin
         for P in Pairs'Range loop
            if X+Pairs(P)(1) in Index and then Y+Pairs(P)(2) in Index and then
              Visited(X+Pairs(P)(1),  Y+Pairs(P)(2)) = 0 then
               Result := Result + 1;
            end if;
         end loop;
         return Result;
      end Neighbors;
 
      procedure Sort(Options: in out Pair_Array) is
         N_Bors: array(Options'Range) of Natural;
         K: Positive range Options'Range;
         N: Natural;
         P: Pair;
      begin
         for Opt in Options'Range loop
            N_Bors(Opt) := Neighbors(Options(Opt)(1), Options(Opt)(2));
         end loop;
         for Opt in Options'Range loop
            K := Opt;
            for Alternative in Opt+1 .. Options'Last loop
               if N_Bors(Alternative) < N_Bors(Opt) then
                  K := Alternative;
               end if;
            end loop;
            N           := N_Bors(Opt);
            N_Bors(Opt) := N_Bors(K);
            N_Bors(K)   := N;
            P            := Options(Opt);
            Options(Opt) := Options(K);
            Options(K)   := P;
         end loop;
      end Sort;
 
      procedure Visit(X, Y: Index; Move: Positive; Found: out Boolean) is
         Next_Count: Natural range 0 .. 8 := 0;
         Next_Steps: Pair_Array(1 .. 8);
         XX, YY: Integer;
      begin
         Found := False;
         Visited(X, Y) := Move;
         if Move = Move_Count then
            Found := True;
         else
            -- consider all possible places to go
            for P in Pairs'Range loop
               XX := X + Pairs(P)(1);
               YY := Y + Pairs(P)(2);
               if (XX in Index) and then (YY in Index)
                 and then Visited(XX, YY) = 0 then
                  Next_Count := Next_Count+1;
                  Next_Steps(Next_Count) := (XX, YY);
               end if;
            end loop;
 
            Sort(Next_Steps(1 .. Next_Count));
 
            for N in 1 .. Next_Count loop
               Visit(Next_Steps(N)(1), Next_Steps(N)(2), Move+1, Found);
               if Found then
                  return; -- no need to search further
            end if;
            end loop;
 
            -- if we didn't return above, we have to undo our move
            Visited(X, Y) := 0;
         end if;
      end Visit;
 
   begin
      Visited := Scene;
      Visit(Start_X, Start_Y, 1, Done);
      if not Done then
         Visited := Scene;
      end if;
      return Visited;
   end Warnsdorff_Get_Tour;


with Knights_Tour, Ada.Command_Line;

procedure Test_Fast is

   Size: Positive := Positive'Value(Ada.Command_Line.Argument(1));

   package KT is new Knights_Tour(Size => Size);

begin
   KT.Tour_IO(KT.Warnsdorff_Get_Tour(1, 1));
end Test_Fast;