
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


*        Knight's tour             20/03/2017
KNIGHT   CSECT
         USING  KNIGHT,R13         base registers
         B      72(R15)            skip savearea
         DC     17F'0'             savearea
         STM    R14,R12,12(R13)    save previous context
         ST     R13,4(R15)         link backward
         ST     R15,8(R13)         link forward
         LR     R13,R15            set addressability
         MVC    PG(20),=CL20'Knight''s tour ..x..'
         L      R1,NN              n
         XDECO  R1,XDEC            edit
         MVC    PG+14(2),XDEC+10   n
         MVC    PG+17(2),XDEC+10   n
         XPRNT  PG,L'PG            print buffer
         LA     R0,1               1
         ST     R0,X               x=1
         ST     R0,Y               y=1
         SR     R0,R0              0
         ST     R0,TOTAL           total=0
LOOP     EQU    *                  do loop
         L      R1,X                 x
         BCTR   R1,0                 -1
         MH     R1,NNH               *n
         L      R0,Y                 y
         BCTR   R0,0                 -1
         AR     R1,R0                (x-1)*n+y-1
         SLA    R1,1                 ((x-1)*n+y-1)*2
         LA     R0,1                 1
         STH    R0,BOARD(R1)         board(x,y)=1
         L      R2,TOTAL             total
         LA     R2,1(R2)             total+1
         STH    R2,DISP(R1)          disp(x,y)=total+1
         ST     R2,TOTAL             total=total+1
         L      R1,X                 x
         L      R2,Y                 y
         BAL    R14,CHOOSEMV         call choosemv(x,y)
         C      R0,=F'0'           until(choosemv(x,y)=0)
         BNE    LOOP               loop
         LA     R2,KN*KN           n*n  
       IF C,R2,NE,TOTAL THEN       if total<>n*n then
         XPRNT  =C'error!!',7        print error
       ENDIF    ,                  endif
         LA     R6,1               i=1
       DO WHILE=(C,R6,LE,NN)       do i=1 to n
         MVC    PG,=CL128' '         init buffer
         LA     R10,PG               pgi=0
         LA     R7,1                 j=1
       DO WHILE=(C,R7,LE,NN)         do j=1 to n
         LR     R1,R6                  i
         BCTR   R1,0                   -1
         MH     R1,NNH                 *n
         LR     R0,R7                  j
         BCTR   R0,0                   -1
         AR     R1,R0                  (i-1)*n+j-1
         SLA    R1,1                   ((i-1)*n+j-1)*2
         LH     R2,DISP(R1)            disp(i,j)
         XDECO  R2,XDEC                edit
         MVC    0(4,R10),XDEC+8        output
         LA     R10,4(R10)             pgi+=4
         LA     R7,1(R7)               j++
       ENDDO    ,                    enddo j
         XPRNT  PG,L'PG              print buffer
         LA     R6,1(R6)             i++
       ENDDO    ,                  enddo i
         L      R13,4(0,R13)       restore previous savearea pointer
         LM     R14,R12,12(R13)    restore previous context
         XR     R15,R15            return_code=0
         BR     R14                exit
*------- ----   ----------------------------------------
CHOOSEMV EQU    *                  choosemv(xc,yc)
         ST     R14,SAVEACMV       save return point
         ST     R1,XC              store xc
         ST     R2,YC              store yc
         MVC    MM,=F'9'           m=9
         L      R1,XC              xc
         LA     R1,1(R1)
         L      R2,YC              yc
         LA     R2,2(R2)
         BAL    R14,TRYMV          call trymv(xc+1,yc+2)
         L      R1,XC              xc
         LA     R1,1(R1)
         L      R2,YC              yc
         SH     R2,=H'2'
         BAL    R14,TRYMV          call trymv(xc+1,yc-2)
         L      R1,XC              xc
         BCTR   R1,0
         L      R2,YC              yc
         LA     R2,2(R2)
         BAL    R14,TRYMV          call trymv(xc-1,yc+2)
         L      R1,XC              xc
         BCTR   R1,0
         L      R2,YC              yc
         SH     R2,=H'2'
         BAL    R14,TRYMV          call trymv(xc-1,yc-2)
         L      R1,XC              xc
         LA     R1,2(R1)
         L      R2,YC              yc
         LA     R2,1(R2)
         BAL    R14,TRYMV          call trymv(xc+2,yc+1)
         L      R1,XC              xc
         LA     R1,2(R1)
         L      R2,YC              yc
         BCTR   R2,0
         BAL    R14,TRYMV          call trymv(xc+2,yc-1)
         L      R1,XC              xc
         SH     R1,=H'2'
         L      R2,YC              yc
         LA     R2,1(R2)
         BAL    R14,TRYMV          call trymv(xc-2,yc+1)
         L      R1,XC              xc
         SH     R1,=H'2'
         L      R2,YC              yc
         BCTR   R2,0
         BAL    R14,TRYMV          call trymv(xc-2,yc-1)
         L      R4,MM              m
       IF C,R4,EQ,=F'9' THEN       if m=9 then
         LA     R0,0                 return(0)
       ELSE     ,                  else
         MVC    X,NEWX               x=newx
         MVC    Y,NEWY               y=newy
         LA     R0,1                 return(1)
       ENDIF    ,                  endif
         L      R14,SAVEACMV       restore return point
         BR     R14                return
SAVEACMV DS     A                  return point
*------- ----   ----------------------------------------
TRYMV    EQU    *                  trymv(xt,yt)
         ST     R14,SAVEATMV       save return point
         ST     R1,XT              store xt
         ST     R2,YT              store yt
         SR     R10,R10            n=0
         BAL    R14,VALIDMV
       IF LTR,R0,Z,R0 THEN         if validmv(xt,yt)=0 then
         LA     R0,0                 return(0)
         B      RETURTMV
       ENDIF    ,                  endif
         L      R1,XT
         LA     R1,1(R1)           xt+1
         L      R2,YT
         LA     R2,2(R2)           yt+2
         BAL    R14,VALIDMV
       IF C,R0,EQ,=F'1' THEN       if validmv(xt+1,yt+2)=1 then 
         LA     R10,1(R10)           n=n+1;
       ENDIF    ,                  endif
         L      R1,XT
         LA     R1,1(R1)           xt+1
         L      R2,YT
         SH     R2,=H'2'           yt-2
         BAL    R14,VALIDMV
       IF C,R0,EQ,=F'1' THEN       if validmv(xt+1,yt-2)=1 then 
         LA     R10,1(R10)           n=n+1;
       ENDIF    ,                  endif
         L      R1,XT
         BCTR   R1,0               xt-1
         L      R2,YT
         LA     R2,2(R2)           yt+2
         BAL    R14,VALIDMV
       IF C,R0,EQ,=F'1' THEN       if validmv(xt-1,yt+2)=1 then
         LA     R10,1(R10)           n=n+1;
       ENDIF    ,                  endif
         L      R1,XT
         BCTR   R1,0               xt-1
         L      R2,YT
         SH     R2,=H'2'           yt-2
         BAL    R14,VALIDMV
       IF C,R0,EQ,=F'1' THEN       if validmv(xt-1,yt-2)=1 then
         LA     R10,1(R10)           n=n+1;
       ENDIF    ,                  endif
         L      R1,XT
         LA     R1,2(R1)           xt+2
         L      R2,YT
         LA     R2,1(R2)           yt+1
         BAL    R14,VALIDMV
       IF C,R0,EQ,=F'1' THEN       if validmv(xt+2,yt+1)=1 then
         LA     R10,1(R10)           n=n+1;
       ENDIF    ,                  endif
         L      R1,XT
         LA     R1,2(R1)           xt+2
         L      R2,YT
         BCTR   R2,0               yt-1
         BAL    R14,VALIDMV
       IF C,R0,EQ,=F'1' THEN       if validmv(xt+2,yt-1)=1 then
         LA     R10,1(R10)           n=n+1;
       ENDIF    ,                  endif
         L      R1,XT
         SH     R1,=H'2'           xt-2
         L      R2,YT
         LA     R2,1(R2)           yt+1
         BAL    R14,VALIDMV
       IF C,R0,EQ,=F'1' THEN       if validmv(xt-2,yt+1)=1 then
         LA     R10,1(R10)           n=n+1;
       ENDIF    ,                  endif
         L      R1,XT
         SH     R1,=H'2'           xt-2
         L      R2,YT
         BCTR   R2,0               yt-1
         BAL    R14,VALIDMV
       IF C,R0,EQ,=F'1' THEN       if validmv(xt-2,yt-1)=1 then
         LA     R10,1(R10)           n=n+1;
       ENDIF    ,                  endif
       IF C,R10,LT,MM THEN         if n<m then
         ST     R10,MM               m=n
         MVC    NEWX,XT              newx=xt
         MVC    NEWY,YT              newy=yt
       ENDIF    ,                  endif
RETURTMV L      R14,SAVEATMV       restore return point
         BR     R14                return
SAVEATMV DS     A                  return point
*------- ----   ----------------------------------------
VALIDMV  EQU    *                  validmv(xv,yv)
         C      R1,=F'1'           if xv<1  then
         BL     RET0
         C      R1,NN              if xv>nn then
         BH     RET0
         C      R2,=F'1'           if yv<1  then
         BL     RET0
         C      R2,NN              if yv>nn then
         BNH    OK
RET0     SR     R0,R0              return(0)
         B      RETURVMV
OK       LR     R3,R1              xv
         BCTR   R3,0
         MH     R3,NNH             *n
         LR     R0,R2              yv
         BCTR   R0,0
         AR     R3,R0
         SLA    R3,1
         LH     R4,BOARD(R3)       board(xv,yv)
       IF LTR,R4,Z,R4 THEN         if board(xv,yv)=0 then
         LA     R0,1                 return(1)
       ELSE     ,                  else
         SR     R0,R0                return(0)
       ENDIF    ,                  endif
RETURVMV BR     R14                return
*        ----   ----------------------------------------
KN       EQU    8                  n  compile-time
NN       DC     A(KN)              n  fullword
NNH      DC     AL2(KN)            n  halfword
BOARD    DC     (KN*KN)H'0'        dim board(n,n) init 0
DISP     DC     (KN*KN)H'0'        dim  disp(n,n) init 0
X        DS     F
Y        DS     F
TOTAL    DS     F
XC       DS     F
YC       DS     F
MM       DS     F
NEWX     DS     F
NEWY     DS     F
XT       DS     F
YT       DS     F
XDEC     DS     CL12
PG       DC     CL128' '           buffer
         YREGS
         END    KNIGHT