'=========================================================================== ' Subject: THE KNIGHT PLACEMENTS Date: 02-09-98 (16:12) ' Author: Peter Raddatz Code: PB ' Origin: lupo@unix.infoserve.net Packet: ALGOR.ABC '=========================================================================== ' THE KNIGHT 'Unless your into CHESS or otherwise LOONEY you will probably 'have very little use for this program, but it was an interesting 'exercise in programming and algorithm development. I wrote it in the 'early '1980's on a CPM machine in interpretated BASIC trying to do one 'better than the standard KNIGHT problem. My CPM machine was WAY 'too slow and I turned the program off after a week or so without 'being any wiser. I've done a little work to spruce up the progr. but 'was too lazy to rework the algorithm into IF/ELSE or SELECT CASE. 'If you want to do that HAVE FUN... 'The basic way this thing works is this way... 'The KNIGHT, standing in the middle of the board can access 8 'squares max. and near the rim as little as 2. The first task was 'to determine all the squares that could be accesssed by any given 'square and then to assign a POINTER to keep track of which of 'the possible squares would be accessed next. Since the object 'was not to step on any squuare twice in ONE attempt to get to h8 'I had to keep track if I already was on that square. If so the 'POINTER was incremented and the next square looked at etc. etc. 'If the pointer could not be incremented any more then I would 'set the present POINTER to 1, back up one square and try to 'increment that POINTER and so on until I wound up on square 64 '( alias h8 ). 'Once on h8 I'd compare if the number of "important" squares 'coverd was higher than the previous one. If so print the path, 'the number of successfull landings on h8 and the max. number of 'squares landed on in one run. Then try to increment the POINTER, 'blah blah blah, same as above. 'Very tideous but effective. 'The code is written in PB, but with minor revisions will work in 'QB and VBDOS. (has mostly to do with INCR VAR instead of 'VAR = VAR + 1). The fastest compiled code seems to be QB 4.5. 'Check out the code. If you can make improvements I would like to 'know. E-mail me at - lupo@unix.infoserve.net - 'Compile it and run it, but be warned this is a VERY, VERY time 'demanding program. I have never had the patience to wait this 'thing out. On my computer, a 486-DX50, it will do approx. '21,000,000 completed passes an hr. or 504,000,000 a day, but 'even at that I have not seen it get half way through. The 'program will seem to pause, but it does not. The number of 'squares currently is simply less than the highest one before. 'While it runs copy down the first 40 fields ( they won't change 'for a while ); this way you can tell the progress. 'Let me know (e-mail) if you ever had enough patience to let this 'thing finish. GOOD LUCK ! '--------------------------- START CODE ----------------------------- COLOR 15, 1 CLS PRINT " THE OBJECT OF THIS EXERCISE IS TO DETERMINE IN HOW MANY DIFFERENT WAYS" PRINT " A KNIGHT CAN GO ON A CHESSBOARD FROM a1 TO h8 AND/OR IF ALL 64 SQUARES" PRINT " CAN BE STEPPED ON WITHOUT STEPPING ON THE SAME SQUARE TWICE IN ONE RUN." PRINT " PROGRAM BY PETER RADDATZ" COLOR 15, 3 LOCATE 25, 30 PRINT " HOW THE KNIGHT JUMPS "; LOCATE 1, 1 COLOR 15, 1 DEFINT A-Z DIM KnightRoute(65), Pointer(64), ChessSquare(64, 8) DIM SquareRow(64), A$(64), BeenThere(64), PossibleSquare(8) DIM MaxSquare(64), L(64) '---------- GIVE THE SQUARES THEIR NAMES FOR I = 1 TO 64 READ A$(I) NEXT DATA a1,b1,c1,d1,e1,f1,g1,h1,a2,b2,c2,d2,e2,f2,g2,h2,a3,b3,c3,d3,e3,f3,g3,h3,a4,b4,c4,d4,e4,f4,g4,h4,a5,b5,c5,d5,e5,f5,g5,h5 DATA a6,b6,c6,d6,e6,f6,g6,h6,a7,b7,c7,d7,e7,f7,g7,h7,a8,b8,c8,d8,e8,f8,g8,h8 '---------- SET RELATIVE ACCESSIBLE SQUARE LOCATIONS PossibleSquare(1) = -17 PossibleSquare(2) = -10 PossibleSquare(3) = 6 PossibleSquare(4) = 15 PossibleSquare(5) = 17 PossibleSquare(6) = 10 PossibleSquare(7) = -6 PossibleSquare(8) = -15 '---------- DETERMINE HOME ROW OF SQUARES FOR I = 1 TO 64 SquareRow(I) = INT((I - 1) / 8) + 1 NEXT '---------- FIND LEGAL ACCESSIBLE SQUARES FOR I = 1 TO 64 FOR K = 1 TO 8 A = I + PossibleSquare(K) IF A <= 0 OR A > 64 GOTO 110 B = ABS(SquareRow(A) - SquareRow(I)) IF B = 0 OR B > 2 GOTO 110 C = INT((ABS(PossibleSquare(K)) + 2) / 8) IF C <> B GOTO 110 FOR J = 1 TO 8 IF ChessSquare(I, J) = 0 THEN ChessSquare(I, J) = A J = 8 END IF NEXT J 110 NEXT K NEXT I '---------- FIND MAXIMUM ACCESSIBLE SQUARES FOR I = 1 TO 64 FOR J = 1 TO 8 IF ChessSquare(I, J) THEN MaxSquare(I) = J NEXT NEXT '---------- INITIALIZE VARIABLES LOCATE 16, 1 PRINT "COMPLETED ROUTES = " PRINT "CURRENT NO. OF STEPS = " PRINT "MAXIMUM NO. OF STEPS = " LastSquare = 1 CurrentSquare = 1 KnightRoute(1) = 1 Pointer(1) = 1 BeenThere(1) = 1 FOR I = 1 TO 64 Pointer(I) = 1 NEXT '---------- GO FIND ROUTES 150 NextSquare = ChessSquare(CurrentSquare, Pointer(CurrentSquare)) IF BeenThere(NextSquare) = 1 GOTO 170 GOTO 230 170 IF Pointer(CurrentSquare) >= MaxSquare(CurrentSquare) GOTO 190 180 INCR Pointer(CurrentSquare) '= Pointer(CurrentSquare) + 1 GOTO 150 190 IF KnightRoute(LastSquare) = 1 GOTO 280 200 Pointer(CurrentSquare) = 1 KnightRoute(LastSquare) = 0 BeenThere(CurrentSquare) = 0 DECR LastSquare '= LastSquare - 1 CurrentSquare = KnightRoute(LastSquare) IF Pointer(CurrentSquare) < MaxSquare(CurrentSquare) THEN INCR Pointer(CurrentSquare) '= Pointer(CurrentSquare) + 1 GOTO 150 END IF 220 GOTO 200 230 CurrentSquare = NextSquare INCR LastSquare '= LastSquare + 1 KnightRoute(LastSquare) = CurrentSquare BeenThere(CurrentSquare) = 1 IF CurrentSquare < 64 GOTO 150 '---------- COMPLETED PATH FROM a1 TO h8 INCR Total&& 'Total# = Total# + 1 SELECT CASE LastSquare CASE IS > MaxFound Times = 1 MaxFound = LastSquare FOR X = 1 TO LastSquare L(X) = KnightRoute(X) NEXT CASE MaxFound INCR Times '= Times + 1 END SELECT IF LastSquare >= MaxFound THEN LOCATE 12, 1 FOR X = 1 TO LastSquare PRINT A$(KnightRoute(X)); " "; NEXT MaxFound = LastSquare END IF '---------- ONLY UPDATE STATS IF MORE THAN 59 SQUARES IF LastSquare > 60 THEN LOCATE 16, 24 PRINT Total&& 'Total# LOCATE 17, 24 PRINT LastSquare; LOCATE 18, 24 PRINT MaxFound; END IF '---------- BeenThere(CurrentSquare) = 0 KnightRoute(LastSquare) = 0 DECR LastSquare '= LastSquare - 1 CurrentSquare = KnightRoute(LastSquare) IF LastSquare > 0 GOTO 170 '---------- WE'RE DONE 280 INPUT " : ", O FOR X = 1 TO MaxFound PRINT A$(L(X)); " "; NEXT PRINT PRINT "MAX. SQUARES FOUND : "; MaxFound PRINT "NUMBER OF TIMES : "; Times