      INTEGER II(0:81),JJ(0:81),KK(0:81),MSK1(0:9)
      INTEGER II1(0:8),JJ1(0:8),KK1(0:8)
      INTEGER II2(0:81),JJ2(0:81),KK2(0:81)
      INTEGER MSKROW(0:8,0:9),MSKCOL(0:8,0:9),MSKSEC(0:8,0:9)
      INTEGER ISDK(0:8,0:8)
      N=1
      DO 10 I=1,9
        MSK1(I)=N
        N=2*N
10    CONTINUE
      WRITE(*,*)
      WRITE(*,*) ' ================================================='
      WRITE(*,*)
      WRITE(*,*) '         MSSudoku - A simple Sudoku solver'
      WRITE(*,*)
      WRITE(*,*) '         Copyright: Matti K. Sinisalo'
      WRITE(*,*)
      WRITE(*,*) '         Programmed in Rovaniemi 3.11.2005'
      WRITE(*,*)
      WRITE(*,*) ' ================================================='
      WRITE(*,*)
      WRITE(*,*) ' This program solves typical 9x9 Sudoku problems'
      WRITE(*,*)
      WRITE(*,*) ' Give me the rows of your Sudoku.'
      WRITE(*,*) ' Use form: 005036000 (0 = not defined)'
      WRITE(*,*)
      DO 20 I=0,8
        WRITE(*,*) 'Row ',I+1,'?'
        READ(*,30) (ISDK(I,J),J=0,8)
20    CONTINUE
30    FORMAT(9I1)

      WRITE(*,*)
      WRITE(*,*) ' Your problem:'
      WRITE(*,*)

      DO 40 I=0,8
         WRITE(*,50) (ISDK(I,J),J=0,8)
40    CONTINUE
50    FORMAT(2X,9I1)
C
C  NOLLATAAN MASKIEN ALKUARVOT
C
      DO 60 I=0,8
        MSKROW(I,0)=0
        MSKCOL(I,0)=0
        MSKSEC(I,0)=0
60    CONTINUE
C
C  TUTKITAAN VAPAAT RUUDUT
C
      NFREE=0
      DO 70 I=0,8
        DO 80 J=0,8
          I1=I/3
          J1=J/3
          K=3*I1+J1
          IF(ISDK(I,J).NE.0)THEN
            MSKROW(I,0)=IOR(MSKROW(I,0),MSK1(ISDK(I,J)))
            MSKCOL(J,0)=IOR(MSKCOL(J,0),MSK1(ISDK(I,J)))
            MSKSEC(K,0)=IOR(MSKSEC(K,0),MSK1(ISDK(I,J)))
          ELSE
            II(NFREE)=I
            JJ(NFREE)=J
            KK(NFREE)=K
            NFREE=NFREE+1
          END IF
80      CONTINUE
70    CONTINUE

      DO 90 I=0,8
        II1(I)=0
        JJ1(I)=0
        KK1(I)=0
90    CONTINUE
      DO 92 I=0,NFREE-1
        II1(II(I))=II1(II(I))+1
        JJ1(JJ(I))=JJ1(JJ(I))+1
        KK1(KK(I))=KK1(KK(I))+1
        II2(I)=II1(II(I))
        JJ2(I)=JJ1(JJ(I))
        KK2(I)=KK1(KK(I))
92    CONTINUE

      INFR=-1
C
C  ETEENPAIN, SANOI MUMMU LUMIHANGESSA
C
100   INFR=INFR+1
      IF(INFR.GE.NFREE)THEN
C
C      TULOSTETAAN RATKAISU
C
        WRITE(*,*)
        WRITE(*,*) ' Solution found: '
        WRITE(*,*)
        DO 110 III=0,8
          WRITE(*,120) (ISDK(III,JJJ),JJJ=0,8)
110     CONTINUE
120     FORMAT(2X,9I1)
        WRITE(*,*)
        GOTO 200
      END IF
      I=II(INFR)
      J=JJ(INFR)
      K=KK(INFR)
      ISDK(I,J)=0
      GOTO 300
C
C  TAAKSEPAIN
C
200   INFR=INFR-1
      IF(INFR.EQ.-1)GOTO 900
      I=II(INFR)
      J=JJ(INFR)
      K=KK(INFR)
      GOTO 300
C
C  SEURAAVA VALINTA VIIMEISELLE LUVULLE
C
300   ISDK(I,J)=ISDK(I,J)+1
      IF(ISDK(I,J).GT.9)GOTO 200
      MASKNO=MSK1(ISDK(I,J))
      IF(IAND(MSKROW(I,II2(INFR)-1),MASKNO).NE.0)GOTO 300
      IF(IAND(MSKCOL(J,JJ2(INFR)-1),MASKNO).NE.0)GOTO 300
      IF(IAND(MSKSEC(K,KK2(INFR)-1),MASKNO).NE.0)GOTO 300
      MSKROW(I,II2(INFR))=IOR(MSKROW(I,II2(INFR)-1),MASKNO)
      MSKCOL(J,JJ2(INFR))=IOR(MSKCOL(J,JJ2(INFR)-1),MASKNO)
      MSKSEC(K,KK2(INFR))=IOR(MSKSEC(K,KK2(INFR)-1),MASKNO)

      GOTO 100

900   WRITE(*,*)
      WRITE(*,*) ' No more solutions. '
      WRITE(*,*)
      STOP
      END

