! =====================================================================
! Trouver toutes les solutions des 8 Reines sur un echiquier.
! Il existe 92 solutions differentes.
! Les Reines sont placees dans perm(1 a 8) calcul par force brute.
! Si tous les perm(1 a 8) sont <>
! On dispose donc d'une Reine par colonne.
! Il suffit de tester les diagonales.
! On associe a chaque case un indice qui identifie les 2 diagonales.
! Diagonales pente +1 dans sol(x, y, diagonale 1)
! Diagonales pente -1 dans sol(x, y, diagonale 2)
! Subroutine diag_init () Liste des diagonales dans sol(8, 8, 2)
! On teste les conflits de diagonales dans Subroutine diagonale()
! =====================================================================
! Compilation par gfortran queen.f
! Pour creer un fichier resultat lancer par :
! ./a.out | cat > Fic_result.txt
! =====================================================================

        program queen_8
        implicit none
        integer perm(8)
        integer x, y, i, k, m
        integer z1, z2, z3, z4, z5, z6, z7, z8
        integer ierr
        integer c_cur

	common /circperm/ perm
	
	! Init des diagonales
	call diag_init()
	! Init compteur solutions
	c_cur = 0

! Recherche des solutions permutees par force brute
! Toutes les valeurs de perm(1 a 8) doivent etre <>
101	do z1 = 1, 8
	  perm(1) = z1
	  do z2	= 1, 8
	    perm(2) = z2
	    do z3 = 1, 8
	      perm(3) = z3
	      do z4 = 1, 8
	        perm(4) = z4
	        do z5 = 1, 8
	          perm(5) = z5
	          do z6 = 1, 8
	            perm(6) = z6
	            do z7 = 1, 8
	              perm(7) = z7
	              do z8 = 1, 8
	                perm(8) = z8
	                
	                ! On verifie l'absence de nombre duplique dans perm
	                do i = 1, 7
	                  do k = (i+1), 8
	                    if (perm(i) .eq. perm(k)) go to 100
	                  enddo
	                enddo
	                
	                ! les 8 nombres dans perm sont <>
	                ! perm (i) contient la position de la reine "i" en y
	                ! On place les Reines dans board (x, y)
	                call set_queen ()
	                ! On teste les conflits en diagonale
	                call diagonale (ierr)
	                if (ierr .eq. 0) then
	                  ! Solution trouvee, on imprime
	                  c_cur = c_cur+1
	                  print 3, c_cur
	                  print 1, (m, m = 1, 8)
	                  print 2, (perm(m), m = 1, 8)
	                  call print_board()
	                endif
100	                continue

	              enddo
	            enddo
	          enddo
	        enddo
	      enddo
	    enddo
	  enddo
	enddo
	
	stop 999

1	format ('Reines X = ', 8i2)
2	format ('Reines Y = ', 8i2)
3	format ('Solution      ======================', i3)

	end

c =======================================	
	subroutine set_queen()
	! placer les 8 reines en fonction de perm
	
	integer board (8, 8), perm (8)
	integer x, y, i, k
	
	common /board/ board
	common /circperm/ perm
	
	do x = 1, 8
	  do y = 1, 8
	    board (x, y) = 0
	  enddo
	  board (x, perm (x)) = 1
	enddo
	return
	end
c =======================================
	subroutine diagonale(err)
	! Rechercher si prise en diagonale
	
        integer sol(8, 8, 2), perm(8)
        integer x, y, x1, y1, err
        integer d1x, d1y

	common /circperm/ perm
	common /diag/ sol

	! Mode erreur implicite			
	err = 1

	do x = 1, 7
	  y = perm(x)
	  d1x = sol(x, y, 1)
	  d2x = sol(x, y, 2)
	  
	  do x1 = (x+1), 8
	    y1 = perm(x1)
	    if (d1x .eq. sol(x1, y1, 1)) return
	    if (d2x .eq. sol(x1, y1, 2)) return
	  enddo    
	enddo
	
	! Aucune erreur trouvee
	err = 0
	return
	
	end
c =======================================
	subroutine diag_init()
	! Creer les indices des diagonales
	! sol (x, y, 1) = diagonale pente +1
	! sol (x, y, 2) = diagonale pente -1
	
        integer sol(8, 8, 2)

	common /diag/ sol
	
	! ====== 1
	sol(1, 1, 1) = 1
	sol(1, 2, 1) = 2
	sol(1, 3, 1) = 3
	sol(1, 4, 1) = 4
	sol(1, 5, 1) = 5
	sol(1, 6, 1) = 6
	sol(1, 7, 1) = 7
	sol(1, 8, 1) = 8
	! ====== 2
	sol(2, 1, 1) = 2
	sol(2, 2, 1) = 3
	sol(2, 3, 1) = 4
	sol(2, 4, 1) = 5
	sol(2, 5, 1) = 6
	sol(2, 6, 1) = 7
	sol(2, 7, 1) = 8
	sol(2, 8, 1) = 9
	! ====== 3	
	sol(3, 1, 1) = 3
	sol(3, 2, 1) = 4
	sol(3, 3, 1) = 5
	sol(3, 4, 1) = 6
	sol(3, 5, 1) = 7
	sol(3, 6, 1) = 8
	sol(3, 7, 1) = 9
	sol(3, 8, 1) = 10
	! ====== 4
	sol(4, 1, 1) = 4
	sol(4, 2, 1) = 5
	sol(4, 3, 1) = 6
	sol(4, 4, 1) = 7
	sol(4, 5, 1) = 8
	sol(4, 6, 1) = 9
	sol(4, 7, 1) = 10
	sol(4, 8, 1) = 11
	! ====== 5
	sol(5, 1, 1) = 5
	sol(5, 2, 1) = 6
	sol(5, 3, 1) = 7
	sol(5, 4, 1) = 8
	sol(5, 5, 1) = 9
	sol(5, 6, 1) = 10
	sol(5, 7, 1) = 11
	sol(5, 8, 1) = 12
	! ====== 6
	sol(6, 1, 1) = 6
	sol(6, 2, 1) = 7
	sol(6, 3, 1) = 8
	sol(6, 4, 1) = 9
	sol(6, 5, 1) = 10
	sol(6, 6, 1) = 11
	sol(6, 7, 1) = 12
	sol(6, 8, 1) = 13
	! ====== 7
	sol(7, 1, 1) = 7
	sol(7, 2, 1) = 8
	sol(7, 3, 1) = 9
	sol(7, 4, 1) = 10
	sol(7, 5, 1) = 11
	sol(7, 6, 1) = 12
	sol(7, 7, 1) = 13
	sol(7, 8, 1) = 14
	! ====== 8
	sol(8, 1, 1) = 8
	sol(8, 2, 1) = 9
	sol(8, 3, 1) = 10
	sol(8, 4, 1) = 11
	sol(8, 5, 1) = 12
	sol(8, 6, 1) = 13
	sol(8, 7, 1) = 14
	sol(8, 8, 1) = 15
	! ====== ****
	! ====== 1
	sol(1, 1, 2) = 1
	sol(1, 2, 2) = 2
	sol(1, 3, 2) = 3
	sol(1, 4, 2) = 4
	sol(1, 5, 2) = 5
	sol(1, 6, 2) = 6
	sol(1, 7, 2) = 7
	sol(1, 8, 2) = 8
	! ====== 2
	sol(2, 1, 2) = 9
	sol(2, 2, 2) = 1
	sol(2, 3, 2) = 2
	sol(2, 4, 2) = 3
	sol(2, 5, 2) = 4
	sol(2, 6, 2) = 5
	sol(2, 7, 2) = 6
	sol(2, 8, 2) = 7
	! ====== 3	
	sol(3, 1, 2) = 10
	sol(3, 2, 2) = 9
	sol(3, 3, 2) = 1
	sol(3, 4, 2) = 2
	sol(3, 5, 2) = 3
	sol(3, 6, 2) = 4
	sol(3, 7, 2) = 5
	sol(3, 8, 2) = 6
	! ====== 4
	sol(4, 1, 2) = 11
	sol(4, 2, 2) = 10
	sol(4, 3, 2) = 9
	sol(4, 4, 2) = 1
	sol(4, 5, 2) = 2
	sol(4, 6, 2) = 3
	sol(4, 7, 2) = 4
	sol(4, 8, 2) = 5
	! ====== 5
	sol(5, 1, 2) = 12
	sol(5, 2, 2) = 11
	sol(5, 3, 2) = 10
	sol(5, 4, 2) = 9
	sol(5, 5, 2) = 1
	sol(5, 6, 2) = 2
	sol(5, 7, 2) = 3
	sol(5, 8, 2) = 4
	! ====== 6
	sol(6, 1, 2) = 13
	sol(6, 2, 2) = 12
	sol(6, 3, 2) = 11
	sol(6, 4, 2) = 10
	sol(6, 5, 2) = 9
	sol(6, 6, 2) = 1
	sol(6, 7, 2) = 2
	sol(6, 8, 2) = 3
	! ====== 7
	sol(7, 1, 2) = 14
	sol(7, 2, 2) = 13
	sol(7, 3, 2) = 12
	sol(7, 4, 2) = 11
	sol(7, 5, 2) = 10
	sol(7, 6, 2) = 9
	sol(7, 7, 2) = 1
	sol(7, 8, 2) = 2
	! ====== 8
	sol(8, 1, 2) = 15
	sol(8, 2, 2) = 14
	sol(8, 3, 2) = 13
	sol(8, 4, 2) = 12
	sol(8, 5, 2) = 11
	sol(8, 6, 2) = 10
	sol(8, 7, 2) = 9
	sol(8, 8, 2) = 1
	
	return
	end
! ==================================================	
	subroutine print_board ()
! Pour un placement des Reines comme suit :	
! Reines X =  1 2 3 4 5 6 7 8
! Reines Y =  1 5 8 6 3 7 2 4
! Sortie console
!   A B C D E F G H 
!  |=|=|=|=|=|=|=|=|
! 1|*| | | | | | | |1
! 2| | | | | | |*| |2
! 3| | | | |*| | | |3
! 4| | | | | | | |*|4
! 5| |*| | | | | | |5
! 6| | | |*| | | | |6
! 7| | | | | |*| | |7
! 8| | |*| | | | | |8
!  |=|=|=|=|=|=|=|=|
!   A B C D E F G H 	

	integer board (8, 8)
	integer i, xp, yp
	character*1 lig(17)
	
	common /board/ board
	
	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) = '*'
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
