-- PARBERRY_TOUR.e
-- A program to find a knights journey, tour or parberry tour.
-- Copyright (C) 2002 Gerard Whyte
-- Created: 08/03/02
-- Last Modified: 08/03/02
class PARBERRY_TOUR
   creation
      make

   feature {NONE}
   --All features hidden for encapsulation. This is a procedural program.
   --Creation Feature
      make is
         do
			print_time
            knights_journey( 8, 8, 1, 1 )
            io.print("%N")
			print_time            
            knights_tour( 8, 8 )
            io.print("%N")
			print_time            
            --knights_parberry( 1, 6, 6 )
            io.print("Enter q for quit: ")
            io.read_character
         end --make

   --Used to store information.
      row      : ARRAY[INTEGER]
      col      : ARRAY[INTEGER]
      board    : ARRAY2[INTEGER]
      success  : BOOLEAN
      size     : INTEGER
      parberry_conditions : ARRAY2[INTEGER]
      current_board : INTEGER

   -- INITIALISATION FEATURES
      init_board( x, y : INTEGER) is
      --Setup the board.
         do
            !!board.make( 1, x, 1, y )
            board.set_all_with( 0 )
            size := board.upper1*board.upper2 -- board may be rectangular
         end --init_board
         
      print_time is
      	local
      		time : BASIC_TIME
      	do
      		!!time
      		time.update
      		io.print( time.year )
      		io.print( "-" )
      		io.print( time.month )
      		io.print( "-" )
      		io.print( time.day )
      		io.print( "-" )
      		io.print( time.hour )
      		io.print( ":" )
      		io.print( time.minute )
      		io.print( "." )
      		io.print( time.second )
      		io.print( "%N" )
      	end --print_time
   		    		
      init_moves is
      --Setup the Knight's moves.
         local
            i,j,k : INTEGER
         do
            k := 1
            !!row.make( 1, 8 )
            !!col.make( 1, 8 )
            from
               i := -2
            until
               i > 2
            loop
               from
                  j := -2
               until
                  j > 2
               loop
                  if i*i + j*j = 5 then
                     row.put( i, k )
                     col.put( j, k )
                     k := k+1
                  end --if
                  j := j+1
               end --loop2
               i := i+1
            end --loop1
         end --init_moves

      init_parberry( board_num, x, y : INTEGER ) is
      -- Create the parberry_conditions depending on which board it is.
         do
            -- Store the d value for getting the next move from row
            -- and col, so that it'll return it such that, the next
            -- move from x, y using this value for d will satisfy
            -- parberry conditions for the particular square.
            if board_num = 1 then
            -- If it's the first one then set up the squares in the lower
            -- right hand corner to satisfy the conditions

            else
               if board_num = 2 then
               -- The second board, the lower left


               else
                  if board_num = 3 then
                  -- The third board, the top right

                  else
                     if board_num = 4 then
                     -- The fourth board, the top left
                     end --if4
                  end --if3
               end --if2
            end --if1
         end --init_parberry


   --DISPLAYING RESULTS
      display_board is
      --Display the contents of the board.
         local
            loop1 : INTEGER
            loop2 : INTEGER
         do
            from
               loop1 := 0
            until
               loop1 > board.upper1
            loop
               if ( loop1 /= 0 ) then
                  io.print( loop1 )
                  io.print( "  " )
               end --if
               from
                  loop2 := 1
               until
                  loop2 > board.upper2
               loop
                  if ( loop1 = 0 ) then
                     if ( loop2 = 1 ) then
                        io.print( "    " )
                     end --if
                     io.print( " " )
                     io.print( loop2 )
                     io.print( " " )
                  else
                     if ( loop2 = 1 ) then
                           io.print( " " )
                     end --if
                     if board.item( loop2, loop1 ) < 10 then
                        io.print( " ")
                        io.print( board.item( loop2, loop1 ) )
                        io.print( " " )
                     else
                        io.print( board.item( loop2, loop1 ) )
                        io.print( " " )
                     end --if
                  end --if
                  loop2 := loop2 + 1
               end --loop2
               if loop1 = 0 then
                  io.print("%N")
               end --if
               io.print( "%N" )
               loop1 := loop1 + 1
            end --loop1
         end --display_board


   --FEATURES USED TO FIND RELEVANT SOLUTION
      acceptable( x, y : INTEGER) : BOOLEAN is
         do
            result := x >= 1 and x <= board.upper1
                      and y >= 1 and y <= board.upper2
                      and then board.item( x, y ) = 0
         end -- Acceptable

      try_next_move_journey(k, x, y :INTEGER) is
      --Use this to find the next move in a journey.
         local
            d, new_x, new_y : INTEGER
         do
            if k > size then
               success := True
            else
               from
                  d := 0
               until
                  d = 8 or success
               loop
                  d := d+1
                  new_x := x + row.item( d )
                  new_y := y + col.item( d )
                  if acceptable( new_x, new_y ) then
                     board.put( k, new_x, new_y )
                     try_next_move_journey( k+1, new_x, new_y )
                     if not success then
                        board.put( 0, new_x, new_y )
                     end --if3
                  end --if2
               end --loop
            end --if1
         end -- try_next_move_journey

      try_next_move_tour(k, x, y :INTEGER) is
      --Use this to find the next move in a tour.
         local
            d, new_x, new_y : INTEGER
         do
            if k = size then
               if board.item( 2, 3 ) = size then -- if x, y is within move of 2,3
                  if ( x = 1 and then y = 5 )
                     or else ( x = 3 and then ( y = 1 or else y = 5 ) )
                     or else ( x = 4 and then ( y = 2 or else y = 4 ) ) then
                     success := True
                  end --if
               else
                  if board.item( 3, 2 ) = size then --if x,y is within move of 3,4???
                     if ( y = 1 and then x = 5 )
                        or else ( y = 3 and then ( x = 1 or else x = 5 ) )
                        or else ( y = 4 and then ( x = 2 or else x = 4 ) ) then
                        success := True
                     end --if
                  end --if
               end --if
            else
               from
                  d := 0
               until
                  d = 8 or success
               loop
                  d := d+1
                  new_x := x + row.item( d )
                  new_y := y + col.item( d )
                  if acceptable( new_x, new_y ) then
                     board.put( k, new_x, new_y )
                     try_next_move_tour( k+1, new_x, new_y )
                     if not success then
                        board.put( 0, new_x, new_y )
                     end --if3
                  end --if2
               end --loop
            end --if1
         end -- try_next_move_tour

      try_next_move_parberry(k, x, y :INTEGER) is
      --Use this to find the next move in a parberry tour.
         local
            d, new_x, new_y : INTEGER
         do
            if k = size then
               if board.item( 2, 3 ) = size then -- if x, y is within move of 2,3
                  if ( x = 1 and then y = 5 )
                     or else ( x = 3 and then ( y = 1 or else y = 5 ) )
                     or else ( x = 4 and then ( y = 2 or else y = 4 ) ) then
                     success := True
                  end --if
               else
                  if board.item( 3, 2 ) = size then --if x,y is within move of 3,4???
                     if ( y = 1 and then x = 5 )
                        or else ( y = 3 and then ( x = 1 or else x = 5 ) )
                        or else ( y = 4 and then ( x = 2 or else x = 4 ) ) then
                        success := True
                     end --if
                  end --if
               end --if
            else
                  from
                     d := 0
                  until
                     d = 8 or success
                  loop
                     d := d+1
                     if parberry_condition.item(current_board, x, y ) /= 0 then
                        --Set the next move to be the correct sqaure for
                        --parberry conditions to be ok.
                        d := parberry_condition.item( x, y )
                     end --if
                     new_x := x + row.item( d )
                     new_y := y + col.item( d )
                     if acceptable( new_x, new_y ) then
                        board.put( k, new_x, new_y )
                        try_next_move_tour( k+1, new_x, new_y )
                        if not success then
                           board.put( 0, new_x, new_y )
                        end --if3
                     end --if2
                  end --loop
            end --if1
         end -- try_next_move_parberry

   --VARIOUS DIFFERENT FEATURES FOR USE IN MAKE, DEPENDING ON WHICH
   --PROGRAM YOU WANT TO RUN.
      knights_journey( width, height, x0, y0 : INTEGER ) is
      --Find a journey.
         do
            success := false
            init_board( width, height )
            init_moves -- set row & col for a knight move
            board.put( 1, x0, y0 ) -- start at (x0,y0)
            try_next_move_journey( 2, x0, y0 ) -- Try next move from the current square
            if not success then
               io.put_string( "No Solution%N" )
            else
               io.print( "Knights Journey%N%N" )
               display_board
            end
         end --knights_journey

      knights_tour( width, height : INTEGER ) is
      --Find a tour.
         do
            success := false
            init_board( width, height )
            init_moves -- set row & col for a knight move
            board.put( 1, 1, 1 ) -- start at (1, 1)
            board.put( size, 2, 3 ) -- end at (2, 3)
            try_next_move_tour( 2, 1, 1 ) -- Try next move from the current square
            if not success then
               io.put_string( "No Solution for (2, 3)%N%N%N" )
               board.put( 0, 2, 3 )
               board.put( size, 3, 2 )
               try_next_move_tour(2, 1, 1 )
               if not success then
                  io.put_string( "No Solution for ( 3, 2 )%N" )
               end --if
            else
               io.print( "Knights Tour%N%N" )
               display_board
            end
         end -- knights_tour

      knights_parberry( board_num, width, height : INTEGER ) is
      --Find a parberry tour.
         do
            success := false
            current_board := board_num
            init_board( width, height ) --Setup board
            init_parberry( board_num, width, height ) --Setup parberry conditions
            init_moves --Setup Knight's moves
            board.put( 1, 1, 1 ) -- start at (1, 1)
            board.put( size, 2, 3 ) -- end at (2, 3) hopefully
            try_next_move_parberry( 2, 1, 1 ) -- Try next move from the current square
            if not success then
               io.put_string( "No Solution for (2, 3)%N%N%N" )
               init_board --Didn't work for ending at (2,3), so reset board
               board.put( size, 3, 2 ) --and then try ending at (3,2)
               try_next_move_parberry(2, 1, 1 )
               if not success then
                  io.put_string( "No Solution for ( 3, 2 )%N" )
               end --if
            else
               io.print( "Knights Parberry Tour%N%N" )
               display_board
            end
         end --knights_parberry
   end --class PARBERRY_TOUR