C Eight Queens Problem
C
C Converted to Fortran by Larry Lefebvre
C
C
      INTEGER    PICKED(8), I
C 
      LOGICAL    ROWCHK(8), DIAGSUM(16), DIAGDIF(15)
C
      DO 1000 I = 1,8,1
         ROWCHK(I) = .FALSE.
         PICKED(I) = 0
1000  CONTINUE
C
      DO 1010 I = 1,16,1
         DIAGSUM(I) = .FALSE.
1010  CONTINUE
C
      DO 1020 I = 1,15,1
         DIAGDIF(I) = .FALSE.
1020  CONTINUE
C
      PRINT *,'Working ...'
      PRINT *,' '
      CALL FIND_SOLUTIONS (ROWCHK, DIAGSUM, DIAGDIF, PICKED)
      PRINT *,' '
      PRINT *,'Thats all folks!'
C
      END
C
C
C
      SUBROUTINE FIND_SOLUTIONS (ROWCHK, DIAGSUM, DIAGDIF, PICKED)
C
      INTEGER    PICKED(8), I
      INTEGER    START, SOLNUM, ROW, COL
C 
      LOGICAL    ROWCHK(8), DIAGSUM(16), DIAGDIF(15)
      LOGICAL    FOUND, DONE
C
      START              = 1
      SOLNUM             = 0
      COL                = 2
      PICKED(1)          = START
      ROWCHK(START)      = .TRUE.
      DIAGSUM(1+START)   = .TRUE.
      DIAGDIF(1-START+7) = .TRUE.
      DONE               = .FALSE.
C
9010  CONTINUE
         ROW = 1
9000     CONTINUE
         FOUND = .FALSE.
            IF (COL .GT. 0) THEN
               IF ((.NOT. ROWCHK(ROW)) .AND. (.NOT. DIAGSUM(COL+ROW))
     +              .AND. (.NOT. DIAGDIF(COL-ROW+7))) THEN
                  PICKED(COL)        = ROW
                  FOUND              = .TRUE.
                  ROWCHK(ROW)        = .TRUE.
                  DIAGSUM(COL+ROW)   = .TRUE.
                  DIAGDIF(COL-ROW+7) = .TRUE.
               ELSE
                  ROW = ROW + 1
               ENDIF
               CALL CONTROL_BACK_UPS (ROW, COL, ROWCHK, DIAGSUM,
     +                             DIAGDIF, PICKED, FOUND, SOLNUM)
            ELSE
               FOUND = .TRUE.
               DONE  = .TRUE.
            ENDIF
         IF (.NOT. FOUND) THEN
            GOTO 9000
         ENDIF
         COL = COL + 1
      IF (.NOT. DONE) THEN
         GOTO 9010
      ENDIF
C
      RETURN
      END
C
C
C
      SUBROUTINE CONTROL_BACK_UPS (ROW, COL, ROWCHK, DIAGSUM,
     +                             DIAGDIF, PICKED, FOUND, SOLNUM)
C
      INTEGER    SOLNUM, ROW, COL, PICKED(8)
C 
      LOGICAL    ROWCHK(8), DIAGSUM(16), DIAGDIF(15), FOUND
C
      IF ((COL .EQ. 8) .AND. (FOUND)) THEN
         CALL DISPLAY_SOLUTION (PICKED, SOLNUM)
         COL   = 9
         FOUND = .FALSE.
         CALL BACK_UP (ROW, COL, ROWCHK, DIAGSUM, DIAGDIF, PICKED)
      ELSE IF (ROW .GT. 8) THEN
         CALL BACK_UP (ROW, COL, ROWCHK, DIAGSUM, DIAGDIF, PICKED)
      ENDIF
C
      RETURN
      END
C
C
C
      SUBROUTINE DISPLAY_SOLUTION (PICKED, SOLNUM)
C
      INTEGER    PICKED(8), SOLNUM, I, J
C
      CHARACTER * 17 LINEVAR
C
      SOLNUM = SOLNUM + 1
      LINEVAR = ' '
C
      PRINT *,' '
      PRINT *,' '
C
      DO 1030 I = 1,8,1
         DO 1040 J = 1,8,1
            IF (PICKED(J) .EQ. I) THEN
               LINEVAR((J*2)-1:(J*2)) = 'Q '
            ELSE
               LINEVAR((J*2)-1:(J*2)) = '+ '
            ENDIF
1040     CONTINUE
         PRINT *,LINEVAR
1030  CONTINUE
C
      PRINT *,'That is solution number ',SOLNUM
C
      RETURN
      END
C
C
C
      SUBROUTINE BACK_UP (ROW, COL, ROWCHK, DIAGSUM, DIAGDIF, PICKED)
C
      INTEGER    ROW, COL, PICKED(8)
C
      LOGICAL    ROWCHK(8), DIAGSUM(16), DIAGDIF(15)
C
9020  CONTINUE
         COL = COL - 1
         IF (COL .GT. 0) THEN
            ROW                = PICKED(COL)
            PICKED(COL)        = 0
            ROWCHK(ROW)        = .FALSE.
            DIAGSUM(COL+ROW)   = .FALSE.
            DIAGDIF(COL-ROW+7) = .FALSE.
            IF (ROW .LT. 8) THEN
               ROW = ROW + 1
            ELSE
               ROW = 99
            ENDIF
         ENDIF
      IF ((ROW .LE. 8) .OR. (COL .EQ. 0)) THEN
         GOTO 9030
      ELSE
         GOTO 9020
      ENDIF
9030  CONTINUE
C
      RETURN
      END