!     Este programa obtiene todas las disposiciones validas de n reinas
!     (en un tablero de ajedrez n x n).
!     Una posible disposicion esta definida por el vector jp(0:n-1)
!     que contiene una permutacion valida de {0,...,n-1}.
!     Siendo (i,j) las coordenadas {0,...,n-1} de cada casilla del tablero,
!     (i, jp(i)) indica la posicion de cada reina.

      parameter(MXN=16)
      logical PosibleSolucion, EsAceptable
      dimension jp(0:MXN-1)


    1 write(6,'(a,$)') 'Tamano del Tablero : '
      read(5,*) n
      if (n.lt.1.or.n.gt.MXN) goto 1

      nsol=0
      do i=0,n-1
        jp(i) = i;
      enddo

      do
        call DisposicionCorrecta(n,jp,EsAceptable)
        if (EsAceptable) then
          nsol=nsol+1
          write(6,'(//a,i6/)') 'Configuracion No. ',nsol
          call ImprimeTablero(n,jp)
        endif
        call SiguientePermutacion(n,jp,PosibleSolucion)
        if (.not.PosibleSolucion) exit
      enddo

      write(6,'(/a,i6,a,i6,a)') ' Se ha encontrado un total de ',nsol,
     .                          ' configuraciones de ',n,' reinas.'

      read(5,'()')

      end



c_______________________________________________________________________________
!     Dado el vector jp(0:n-1), que contiene una permutacion de n enteros,
!     esta funcion obtiene la siguiente permutacion en orden creciente.
!     Si se han agotado las permutaciones posibles, devuelve el valor FALSE.

      Subroutine SiguientePermutacion(n, jp, PosibleSolucion)
      dimension jp(0:n-1)
      logical   PosibleSolucion

      do i=n-2,0,-1
        if (jp(i).lt.jp(i+1)) exit
      enddo

      if (i.lt.0) then
        PosibleSolucion=.FALSE.
        return
      else
        do j=n-1,i+1,-1
          if (jp(j).gt.jp(i)) exit
        enddo
        call PermutaComponentes(n,jp,i,j)
        i=i+1
        j=n-1
        do while(i.lt.j)
          call PermutaComponentes(n,jp,i,j)
          i=i+1
          j=j-1
        enddo
        PosibleSolucion=.TRUE.
        return
      endif

      end


c_______________________________________________________________________________
!     Dado el vector jp(0:n), esta subrutina permuta sus componentes i y j

      Subroutine PermutaComponentes(n,jp,i,j)
      dimension jp(0:n-1)

      jpc  =jp(i)
      jp(i)=jp(j)
      jp(j)=jpc

      return
      end
    

c_______________________________________________________________________________
!     Esta subrutina analiza si es aceptable la disposicion de n reinas
!     (en un tablero de ajedrez n x n) definida por el vector jp(n].
!     El vector jp(0:n-1) contiene una permutacion valida de {0,...,n-1}.
!     Siendo (i,j) las coordenadas {0,...,n-1} de cada casilla del tablero,
!     (i, jp(i)) indica la posicion de cada reina.

      Subroutine DisposicionCorrecta(n, jp, EsAceptable)
      dimension jp(0:n-1)
      logical   EsAceptable

      do i=0,n-2
        do j=i+1,n-1
          if (iabs(jp(j)-jp(i)).eq.(j-i)) then
             EsAceptable=.FALSE.
             return
          endif
        enddo
      enddo

      EsAceptable=.TRUE.
      return

      end

c_______________________________________________________________________________
!     Esta subrutina imprime un tablero de ajedrez n x n con la disposicion
!     de reinas definida por el vector jp(0:n-1).
!     Siendo (i,j) las coordenadas {0,...,n-1} de cada casilla del tablero,
!     (i, jp(i)) indica la posicion de cada reina.

      Subroutine ImprimeTablero(n,jp)
      dimension jp(0:n-1)

      write(6,'(a,$)') '     '
      do j=0,n-1
        write(6,'(a,$)') '+-'
      enddo
	write(6,'(a)') '+'

      do i=0,n-1
        write(6,'(a,$)') '     '
        do j=0,jp(i)-1
          write(6,'(a,$)') '| '
        enddo
	  write(6,'(a,$)') '|o'
        do j=jp(i)+1,n-1
          write(6,'(a,$)') '| '
        enddo
	  write(6,'(a/a,$)') '|','     '
        do j=0,n-1
          write(6,'(a,$)') '+-'
        enddo
 	  write(6,'(a)') '+'
      enddo

      write(6,'(/)')

      return
      end


