
Task
Problem: you have a standard 8x8 chessboard, empty but for a single knight on some square. Your task is to emit a series of legal knight moves that result in the knight visiting every square on the chessboard exactly once. Note that it is not a requirement that the tour be "closed"; that is, the knight need not end within a single move of its start position.

Input and output may be textual or graphical, according to the conventions of the programming environment. If textual, squares should be indicated in algebraic notation. The output should indicate the order in which the knight visits the squares, starting with the initial position. The form of the output may be a diagram of the board with the squares numbered according to visitation sequence, or a textual list of algebraic coordinates in order, or even an actual animation of the knight moving around the chessboard.

Input: starting square

Output: move sequence



Related tasks
 A* search algorithm
 N-queens problem
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


 
! **********************************************************************
! *                                                                    *
! *     IL GIRO DEL CAVALLO - come collocare un cavallo su di una      *
! *                           scacchiera n*n passando una sola volta   *
! *                           per ogni casella.                        *
! *                                                                    *
! **********************************************************************
! ----------------------------------------------------------------------
!                   Inizializzazione dei parametri
! ----------------------------------------------------------------------
 
PROGRAM KNIGHT
 
!$INTEGER
!$KEY
 
DIM H[25,25],A[8],B[8],P0[8],P1[8]
 
!$INCLUDE="PC.LIB"
 
PROCEDURE INIT_SCACCHIERA
! **********************************************************************
! *         Routine di inizializzazione scacchiera                     *
! **********************************************************************
     FOR I1=1 TO 8 DO
         U=X+A[I1]  V=Y+B[I1]
         IF (U>0 AND U<=N) AND (V>0 AND V<=N) THEN
             H[U,V]=H[U,V]-1
         END IF
     END FOR
END PROCEDURE
 
PROCEDURE MOSTRA_SCACCHIERA
! *********************************************************************
! *         Routine di visualizzazione della scacchiera               *
! *********************************************************************
     LOCATE(5,1)  COLOR(0,7) PRINT(" Mossa num.";NMOS) COLOR(7,0)
     L2=N
     FOR I2=1 TO N DO
         PRINT
         FOR L1=1 TO N DO
             IF H[L1,L2]>0 THEN COLOR(15,0) END IF
             WRITE("####";H[L1,L2];)
             COLOR(7,0)
         END FOR
         L2=L2-1
     END FOR
END PROCEDURE
 
PROCEDURE AGGIORNA_SCACCHIERA
! *********************************************************************
! *        Routine di Aggiornamento Scacchiera                        *
! *********************************************************************
     B=1
     FOR I1=1 TO 8 DO
         U=X+A[I1] V=Y+B[I1]
         IF (U>0 AND U<=N) AND (V>0 AND V<=N) THEN
             IF H[U,V]<=0 THEN
                 H[U,V]=H[U,V]+1 B=0
             END IF
         END IF
      END FOR
      IF B=1 THEN Q1=0 END IF
END PROCEDURE
 
PROCEDURE MOSSA_MAX_PESO
! *********************************************************************
! *         Cerca la prossima mossa con il massimo peso               *
! *********************************************************************
     M1=0  RO=1
     FOR W=1 TO 8 DO
         U=Z1+A[W] V=Z2+B[W]
         IF (U>0 AND U<=N) AND (V>0 AND V<=N) THEN
              IF H[U,V]<=0 AND H[U,V]<=M1 THEN
                  IF H[U,V]=M1 THEN
                      RO=RO+1 P0[RO]=W
                   ELSE
                      M1=H[U,V] Q1=1  T1=U T2=V RO=1 P0[1]=W
                  END IF
              END IF
         END IF
     END FOR
END PROCEDURE
 
PROCEDURE MOSSA_MIN_PESO
! *********************************************************************
! *          Cerca la prossima mossa con il minimo peso               *
! *********************************************************************
     M1=-9 RO=1
     FOR W=1 TO 8 DO
        U=Z1+A[W]  V=Z2+B[W]
        IF (U>0 AND U<=N) AND (V>0 AND V<=N) THEN
              IF H[U,V]<=0 AND H[U,V]>=M1 THEN
                   IF H[U,V]=M1 THEN
                        RO=RO+1 P0[RO]=W
                     ELSE
                        M1=H[U,V] Q1=1  T1=U T2=V RO=1 P0[1]=W
                   END IF
              END IF
        END IF
     END FOR
END PROCEDURE
 
BEGIN
     A[1]=1     A[2]=2   A[3]=2   A[4]=1
     A[5]=-1    A[6]=-2  A[7]=-2  A[8]=-1
     B[1]=2     B[2]=1   B[3]=-1  B[4]=-2
     B[5]=-2    B[6]=-1  B[7]=1   B[8]=2
 
     CLS
     PRINT("            ***    LA GALOPPATA DEL CAVALIERE    ***")
     PRINT
     PRINT("Inserire la dimensione della scacchiera (max. 25)";)
     INPUT(N)
     PRINT("Inserire la caselle di partenza (x,y) ";)
     INPUT(X1,Y1)
     NMOS=1  A1=1  N1=N*N  ESCAPE=FALSE
! ----------------------------------------------------------------------
!                  Set della scacchiera
! ----------------------------------------------------------------------
     WHILE NOT ESCAPE DO
          FOR I=1 TO N DO
             FOR J=1 TO N DO
                H[I,J]=0
             END FOR
          END FOR
          FOR I=1 TO N DO
             FOR J=1 TO N DO
                X=I  Y=J
                INIT_SCACCHIERA
             END FOR
          END FOR
 
! ----------------------------------------------------------------------
!                       Effettua la prima mossa
! ----------------------------------------------------------------------
          X=X1  Y=Y1  H[X,Y]=1   L=2
          AGGIORNA_SCACCHIERA
          Q1=1  Q2=1
! -----------------------------------------------------------------------
!                        Trova la prossima mossa
! -----------------------------------------------------------------------
          WHILE Q1<>0 AND Q2<>0 DO
               Q1=0 Z1=X Z2=Y
               MOSSA_MIN_PESO
               IF RO<=1 THEN
                   C1=T1    C2=T2
                ELSE
! ------------------------------------------------------------------------
!                         Esamina tutti i vincoli
! ------------------------------------------------------------------------
                   FOR K=1 TO RO DO
                     P1[K]=P0[K]
                   END FOR
                   R1=RO
                   IF A1=1 THEN M2=-9 ELSE M2=0 END IF
                   FOR K=1 TO R1 DO
                      F1=P1[K]   Z1=X+A[F1]   Z2=Y+B[F1]
                      IF A1=1 THEN
                          MOSSA_MAX_PESO
                          IF M1<=M2 THEN
                              !$NULL
                            ELSE
                              M2=M1 C1=Z1 C2=Z2
                           END IF
                        ELSE
                           MOSSA_MIN_PESO
                           IF M1>=M2 THEN
                               !$NULL
                             ELSE
                               M2=M1  C1=Z1  C2=Z2
                            END IF
                        END IF
                   END FOR
! ------------------------------------------------------------------------
!          Prossima mossa trovata:aggiorna la scacchiera
! ------------------------------------------------------------------------
               END IF
               IF Q1<>0 THEN
                     X=C1  Y=C2 H[X,Y]=L
                     AGGIORNA_SCACCHIERA
                     IF L=N1 THEN Q2=0 END IF
                END IF
                L=L+1
                MOSTRA_SCACCHIERA
                NMOS=NMOS+1
          END WHILE
! ------------------------------------------------------------------------
!           La ricerca è terminata: visualizza i risultati
! ------------------------------------------------------------------------
          PRINT PRINT
          IF Q2<>1 THEN
              PRINT("*** Trovata la soluzione! ***")
              MOSTRA_SCACCHIERA
              ESCAPE=TRUE
            ELSE
              IF A1=0 THEN
                  PRINT("Nessuna soluzione.")
                  ESCAPE=TRUE
                ELSE
                  BEEP
                  A1=0
              END IF
           END IF
      END WHILE
      REPEAT
         GET(A$)
      UNTIL A$<>""
END PROGRAM
 