!=============================================================
! Pour rediriger la sortie vers un fichier                   =
! a.out > fichier ne fonctionne pas                          =
! Il FAUT IMPERATIVEMENT passer par un pipe cat > file       =
! a.out | cat > fichier.txt   ou | est Alt-Gr 6  et non /    =
! Solution obtenue en posant la question suivante a GOOGLE   =
! gfortran a.out > file does not write in file               =
!=============================================================

	implicit none
	integer brd(8, 8), move(64, 2), cav(8, 2)
	integer i, k, x, y
	integer ier, pnt_move, max 
	integer xp, yp, nb, comp_cav, selc_cav
	integer*4 start_time
	integer*8 total, cumul
	real r1, r2, r3
	
	common /board/brd, cav
	common /move/move
	
	max   = 0

	! Initialisation tableaux
	do 100 i = 1, 64
	  move (i, 1) = 0
	  move (i, 2) = 0
100	continue

	do 101 i = 1, 8
	  do 102 k = 1, 8
	    brd (i, k) = 0
102	  continue
101	continue

	call random_seed()
	
	total = 0
	cumul = 0
	! Definir position initiale
			
110	continue
	pnt_move = 1
	x  = 4
	y  = 4
	xp = x
	yp = y
	
	move (pnt_move, 1) = x
	move (pnt_move, 2) = y
	
	call clr_brd (x, y)
		
111	continue
	
	nb = comp_cav (x, y)
	total = total+1

	! calculer les deplacements possibles depuis x - y
	! Valeur de retour = nombre de deplacements possibles
	! Choisir une position au hasard
	! Coordonnees retournees dans x et y
	! Si impossible ier = 1
	
	ier = selc_cav (x, y, nb)
	if ( ier .eq. 0 ) then
	  brd (x, y) = 1
	  pnt_move = pnt_move+1
	  move (pnt_move, 1) = x
	  move (pnt_move, 2) = y
	  if ( pnt_move .gt. max) then
	    max = pnt_move
	  endif

	  if (pnt_move .eq. 64 ) go to 999
	else
	  ! Faire reset de l'echiquier 
	  go to 110
	endif

	go to 111

999	continue

	! Peut-on revenir au point de depart
	! xpn, yp = position initiale, x, y position dernier mouvement
	! si nb = 7 alors on peut repasser par le point de depart
	
	call clr_brd (xp, yp)
	brd (x, y) = 1
	ier = selc_cav (x, y, nb)
	if ( nb .eq. 7) then
	  print 10
	else
	  print 11
	endif
		
	cumul = cumul+total
	print 3, total, cumul
	call print_move (max)
	max = 0
	total = 0
	
	go to 110
	
	stop 999
1	format ('Nbr Solutions = 'i2)
2	format (' |'i2)
3	format ('Solution en ', i20, ' mouvements => Total 'i20)
4	format ('Main_line Rang & X & Y = ', 3i5)
5	format (' Exit rewind')
6	format (' New move = ', 2i2, ' Rang, Max = ', 2i3)
8	format (a1)
9	format ('Time @ init = ', i10)
10	format ('================= Circuit ferme')
11	format ('Circuit ouvert ==============')
12	format ('Circuit ouvert = 210987654321 =')
30	format ('Pointeur rewind < 1 ==> BUG !')
	end

! ==================================================
	subroutine clr_brd(x ,y)
	! Initialiser l'echiquier
	integer brd(8, 8), move(64, 2), cav(8, 2)
	integer i, k, x, y
		
	common /board/brd, cav
	common /move/move
	
	do 100 i = 1, 8
	  do 101 k = 1, 8
	    brd (i, k) = 0
	    brd (i, k) = 0
101	  continue	    
100	continue
	brd (x ,y) = 1
	return
	end

! ==================================================
	subroutine print_move (nb)
	
	! Imprimer sur 2 lignes move (64, 2)
	
	integer brd(8, 8), move(64, 2), cav(8, 2)
	character*1 lig(17)
	character*1 mv1 ( 64 ), mv2 ( 64 ), xx ( 9 ), yy ( 9 )
	integer i, k, m, x, y
	integer nb
	
	common /board/brd, cav
	common /move/move

	print 2, nb
	
	xx (1) = 'A'
	xx (2) = 'B'
	xx (3) = 'C'
	xx (4) = 'D'
	xx (5) = 'E'
	xx (6) = 'F'
	xx (7) = 'G'
	xx (8) = 'H'
	xx (9) = 'x'
	
	
	yy (1) = '1'
	yy (2) = '2'
	yy (3) = '3'
	yy (4) = '4'
	yy (5) = '5'
	yy (6) = '6'
	yy (7) = '7'
	yy (8) = '8'
	yy (9) = 'y'
	
	do 100 i = 1, nb
	  mv1 (i) = xx (move (i, 1))
	  mv2 (i) = yy (move (i, 2))
100	continue

	print 1, (mv1 (i), i=1, nb)
	print 1, (mv2 (i), i=1, nb)
	
	return
1	format (64a1)
2	format ('Move nbr = ', i2)
3	format ('Rang & X & Y = ', 3i5)
	end

! ==================================================	
	integer function selc_cav (x, y, nb)
	! Melanger Random les ier premiers rangs de cav ()
	! ier = nombre de solutions possibles
	
	integer brd(8, 8), move(64, 2), cav(8, 2)
	integer i, m, x, y
	integer xp, yp, nb
	real a
	
	common /board/brd, cav
	
	selc_cav = 0
	xp  = x
	yp  = y
	
101	do 100 i = 1, nb
	  call random_number (a)
	  m = a*float (nb) + 1
	  x = cav (m, 1)
	  y = cav (m, 2)
	  if ( brd (x, y) .ne. 1) go to 108
100	continue
	selc_cav = 1
108	return
	
1	format ('Random = ', 2i5)		
	end	

! ==================================================
	integer function c1_8 ( v )
	integer cxy_1_8, v
	
	if ((v.lt. 1) .or. (v .gt. 8)) then
	  c1_8 = 0
	else
	  c1_8 = 1
	endif
	
	return
	end
	
! ==================================================
	integer function cxy_1_8 (x, y)
	integer x, y, c1_8
	
	cxy_1_8 = c1_8(x) * c1_8(y)
	
	return
	end
	
! ==================================================
	integer function comp_cav (x, y)
	integer board (8, 8), cav (8, 2)
	integer i, x, y
	integer xp, yp, nb
	integer cxy_1_8
	character*1 lig(17)
	
	common /board/board, cav
	
	! Calcul des 2 à 8 deplacements possibles
	! Reset deplacements cavalier
	! comp_cav = nombre de solutions

	i = 1
	nb = 0
	
	! Cas 1
105	continue
	m = 0
	cav (i, 1) = x+2
	cav (i, 2) = y-1
	if (cxy_1_8(cav (i, 1), cav (i, 2)) .eq. 0) then
	  m = 0
	  cav (i, 1) = 0
	  cav (i, 2) = 0
        else
          if (board (cav (i, 1), cav (i, 2)) .eq. 0) m = 1
        endif
        nb = nb+m
        i  = i+m
        
        ! Cas 2
        m = 0
        cav (i, 1) = x+2
	cav (i, 2) = y+1
	if (cxy_1_8(cav (i, 1), cav (i, 2)) .eq. 0) then
	  cav (i, 1) = 0
	  cav (i, 2) = 0
        else
          if (board (cav (i, 1), cav (i, 2)) .eq. 0) m = 1
        endif
        nb = nb+m
        i  = i+m
        
        ! Cas 3
        m = 0
        cav (i, 1) = x-2
	cav (i, 2) = y-1
	if (cxy_1_8(cav (i, 1), cav (i, 2)) .eq. 0) then
	  cav (i, 1) = 0
	  cav (i, 2) = 0
        else
          if (board (cav (i, 1), cav (i, 2)) .eq. 0) m = 1
        endif
        nb = nb+m
        i  = i+m
        
        ! Cas 4
        m = 0
        cav (i, 1) = x-2
	cav (i, 2) = y+1
	if (cxy_1_8(cav (i, 1), cav (i, 2)) .eq. 0) then
	  cav (i, 1) = 0
	  cav (i, 2) = 0
        else
          if (board (cav (i, 1), cav (i, 2)) .eq. 0) m = 1
        endif
        nb = nb+m
        i  = i+m
        
        ! Cas 5
        m = 0
        cav (i, 1) = x+1
	cav (i, 2) = y+2
	if (cxy_1_8(cav (i, 1), cav (i, 2)) .eq. 0) then
	  cav (i, 1) = 0
	  cav (i, 2) = 0
        else
          if (board (cav (i, 1), cav (i, 2)) .eq. 0) m = 1
        endif
        nb = nb+m
        i  = i+m
        
        ! Cas 6
        m = 0
        cav (i, 1) = x+1
	cav (i, 2) = y-2
	if (cxy_1_8(cav (i, 1), cav (i, 2)) .eq. 0) then
	  cav (i, 1) = 0
	  cav (i, 2) = 0
        else
          if (board (cav (i, 1), cav (i, 2)) .eq. 0) m = 1
        endif
        nb = nb+m
        i  = i+m
        
        ! Cas 7
        m = 0
        cav (i, 1) = x-1
	cav (i, 2) = y+2
	if (cxy_1_8(cav (i, 1), cav (i, 2)) .eq. 0) then
	  cav (i, 1) = 0
	  cav (i, 2) = 0
        else
          if (board (cav (i, 1), cav (i, 2)) .eq. 0) m = 1
        endif
          nb = nb+m
          i  = i+m
         
        ! Cas 8
        m = 0
        cav (i, 1) = x-1
	cav (i, 2) = y-2
	if (cxy_1_8(cav (i, 1), cav (i, 2)) .eq. 0) then
	  cav (i, 1) = 0
	  cav (i, 2) = 0
        else
          if (board (cav (i, 1), cav (i, 2)) .eq. 0) m = 1
        endif
        nb = nb+m
        i  = i+m
        
        comp_cav = nb
         	
	return

1	format ('   |12345678  Solutions = ', i2)
2	format ('X = ', 8i1)
3	format ('Y = ', 8i1)

	end

! ==================================================	
	subroutine print_board ()
	integer board (8, 8), cav (8, 2, 1)
	integer i
	integer xp, yp
	character*1 lig(17)
	
	common /board/board, cav
	print 3
	print 1
	do 302 yp = 1, 8
	  lig (1) = '|'
	  do 303 xp = 1, 8
	    lig (xp*2) = ' '
	    lig (1 + xp*2) = '|'
	    if (board (xp, yp) .eq. 1) lig(xp*2) = '*'
	    if (board (xp, yp) .eq. 2) lig(xp*2) = '-'
	    if (board (xp, yp) .eq. 3) lig(xp*2) = '$'
303	  continue
	  print 2, yp, (lig (i), i=1, 17), yp
302	continue
	print 1
	print 3
	
	return
	
3	format ('  A B C D E F G H ')
1	format (' |=|=|=|=|=|=|=|=|')
2	format (i1, 17a1, i1)

	end
