Home » CEEFAX disks » telesoftware16.adl » 14-07-89/TKnight
14-07-89/TKnight
This website contains an archive of files for the Acorn Electron, BBC Micro, Acorn Archimedes, Commodore 16 and Commodore 64 computers, which Dominic Ford has rescued from his private collection of floppy disks and cassettes.
Some of these files were originally commercial releases in the 1980s and 1990s, but they are now widely available online. I assume that copyright over them is no longer being asserted. If you own the copyright and would like files to be removed, please contact me.
| Tape/disk: | Home » CEEFAX disks » telesoftware16.adl |
| Filename: | 14-07-89/TKnight |
| Read OK: | ✔ |
| File size: | 30AF bytes |
| Load address: | 0000 |
| Exec address: | FFFFFFFF |
File contents
Recursion and Backtracking. Rob Anderson. June'88.
Introduction
Recursion is a powerful programming technique which is often shunned
because of its slightly "abstract" nature. However it is well worth
getting to grips with, and even though only a small subset of problems are
suitable for solution using recursion, nothing else will do when such a
problem is encountered.
Many books have been written containing sections on recursion (especially
PASCAL textbooks, ref.2) so only a little theory is given here. More
attention will be given to backtracking algorithms which often take full
advantage of recursion to solve a given problem by trial and error. Two
such examples are The Knights Tour, and the game of Solitaire.
There are three programs that accompany this article. The first is a
simple PASCAL implementation of the Knights Tour which can generate a
solution to the problem and output the moves required as text on the
screen, and the second is a BBC BASIC version which provides a pretty
display so that the "thought" processes that the computer uses to obtain
the solution can be examined, while providing a variety of options to
demonstrate the versatility of the recursive routine. The final program
(in PASCAL) generates a solution to the game of Solitaire, showing how
backtracking methods can be applied successfully to many applications.
What is recursion?
Put simply, recursion is a process whereby a procedure may call itself a
number of times. A simple but revealing example is the generation of
factorials, where the factorial (!) of a number is the multiplication of
the sequence of integers from 1 to that number. For example;
5! = 5*4*3*2*1 = 120
2! = 2*1 = 2
0! = 1 (by definition)
The following PASCAL code will generate the factorial for any legal input
number.
PROGRAM factorial(INPUT,OUTPUT);
VAR number : INTEGER;
FUNCTION fact(n : INTEGER) : INTEGER;
BEGIN
IF n <= 1 THEN fact := 1
ELSE fact := n * fact(n-1);
END; { fact }
BEGIN
READ(number);
WRITE(fact(number));
END.
Note the recursive procedure "fact" which returns 1 if its argument is
less then or equal to one, otherwise it returns the number multiplied by
the factorial of one minus the number (performed by the statement
fact(n-1)).
Many mathematical functions and series can be calculated using recursion,
but in many cases recursion is not absolutely necessary and a simpler
algorithm may be used. For example, the factorial may simply be generated
using;
READ(num);
ans := 1;
FOR loop := 1 TO num DO
ans := ans * loop;
WRITE(ans);
A much better example (but more complex) is the Knights Tour, which would
be very tricky to solve without recursion.
The Knights Tour
The problem is to move a single knight on an empty chess board such that
it visits each square only once.
The first program "PKnight" is a PASCAL version of a solution to the
problem. This has been included to show the structure of the program
better, as the BBC BASIC version held under "BKnight" is somewhat harder
to follow due to the extra coding included to produce a nice graphical
display of the knight whizzing around the chess board.
The pascal version should run on any standard implementation of PASCAL.
However, ISO PASCAL on the BBC requires the following compiler options to
be placed right at the beginning of the program (ie before "PROGRAM");
{$C3000,+F}
When the program is running a constant update about the current state of
solution is given, and upon completion the solution is output. Note that
different parameters to the problem may be specified in the CONSTant
declarations in the source code, including board size, start position
etc..
The BASIC version is more versatile, enabling board dimensions and start
position to be input directly (simply follow the prompts), after-which the
required size board is drawn and the knight put in the start position.
Then, by pressing "S", the knight will move one step at a time around the
board, with the moves also being output as text to the right of the
screen. Note how the knight must backtrack so as to try a different path
when it becomes stuck. Pressing "C" makes the knight continuously search
for a solution, but may be placed back into single step mode by pressing
"S" again. Pressing "R" restarts the program to enable new start
parameters to be entered.
If a solution is found then the following options are presented;
"R" - restart program.
"P" - output solution to printer.
"F" - output solution to file.
"S" - output solution to screen.
"E" - exit program.
The program should work on any implementation of BBC BASIC, but if no
shadow mode is available (eg. in a standard BBC 'B') then line 60 should
be changed by setting mode% to 4 instead of 129. This will simply mean
that only two colours are used for the display instead of four.
How the programs work:
A human could go about solving the Knights Tour by simply choosing a
random selection of moves until no more are possible. If some of the
squares remained un-visited then the path taken could be reversed a few
moves and different paths taken until a solution was found. Now computers
are very good at performing mundane tasks very quickly, so we can write a
program to generate a path, check if it is a solution, and if not then it
can BACKTRACK along the current path and try a different route. So to
start with the Knight has eight possible moves, and for each of those
another eight moves are possible, and so on. If upon making a move the
Knight is stuck, then it can backtrack to its previous position and try
one of the other seven moves.
This is all very well, but how do we check that all possible paths are
tried, and that no paths are repeated? Consider algorithm 1.
1 FUNCTION trynextmove : BOOLEAN;
2
3 Initialise 8 possible moves for the Knight.
4 REPEAT
5 Select next move from list of eight possible moves.
6 IF move is legal
7 THEN
8 Make the move.
9 IF board not full
10 THEN
11 success := trynextmove;
12 IF NOT(success)
THEN Erase last move because no path can
be generated from it.
13 UNTIL success OR all eight moves have been tried.
Algorithm 1.
This is a backtracking algorithm which uses recursion to keep an ordered
record of the paths that have been tried. Note line 11 which recursively
calls trynextmove. The sequence of events upon calling trynextmove are;
(assuming the Knight to be initially at the top right of the 8*8 board and
the first move selected of the eight possible is left one square and down
two)
- First call to trynextmove moves Knight left one and down two squares.
- A recursive call to trynextmove results in the Knight moving left one
and down two squares from its current position.
- A second recursive call results in the same move again.
- A third recursive call attempts the same move again, but finds the
Knight at the bottom of the board, so selects the next move in the
candidate list.
The above sequence of events can be examined using "BKnight".
Backtracking algorithms have in general a sequence of events which can be
applied to many situations. In fact, we can define a generalised
backtracking algorithm (algorithm 2).
PROCEDURE trynextmove;
BEGIN
initialise selection of moves;
REPEAT
Select next candidate from list of possible moves.
IF move is legal
THEN
Make the move;
IF board not full
THEN
trynextmove;
IF NOT(success)
THEN Erase last move because no solution can be made from that move.
UNTIL success OR all eight moves have been tried.
END trynextmove
Algorithm 2.
Armed with algorithm 2 we can now attempt to write a program to solve
Solitaire, where the object of the game is to remove in play all the pegs
from the playing board except the last one which must finish in the centre
hole. Pegs are removed by hopping over them with another adjacent peg into
an empty space beyond, either vertically or horizontally. The board at
start of play is given in figure 1.
111
111
1111111
1110111
1111111
111
111
Figure 1 - initial solitaire board.
( 1 => peg, 0 => hole)
First of all, a method of representation must be adopted. The simplest way
is to use a two dimensional array of boolean values, where TRUE implies an
hole, and FALSE implies a peg. Note that this is slightly wasteful,
because not all the elements of the array will be used due to the unusual
shape of the board, which also means that the routine ("legalpos") is
required to check that any move remains inside the cross shape.
We now need a way of selecting all possible moves. The easiest way is to
take each peg in turn and, if a legal move can be made, that move should
be recorded and then a recursive call to "trymove" made to try and make
further moves. This continues until the game is finished, or no further
moves can be made in which case backtracking occurs.
The PASCAL program "P/SOL" performs this, and as before if ISO PASCAL on
the BBC is used then the compiler directives mentioned above should be
included.
Other classic problems with recursion.
The following are interesting problems involving backtracking and or
recursion.
Generating the fibonacci series - The fibonacci series is a sequence of
numbers where the next number comprises the previous two numbers in the
sequence added together. The first two numbers are defined to be 1. The
first 10 numbers are therefore 1,1,2,3,5,8,13,21,34,55. This sequence can
be generated using a short recursive procedure.
Tower of Hanoi - This consists of three posts, one of which has a number
of discs with holes in that are placed on the leftmost post in decreasing
order of size (the largest radius disc is placed at the bottom of the
pile). The object of the puzzle is to move the pile of discs from one post
to another, with the condition that only one disc may be moved at a time
and at no stage may a larger disc rest on a smaller disc.
The Eight Queens problem - Here, eight queens must be placed on a chess
board such that no queen is placed in check with another. This requires
another backtracking algorithm similar to the knights tour problem.
Conclusion
Recursion is a powerful technique which can result in a lot of processing
from a small amount of code. It is especially useful with backtracking
algorithms such as the Knights Tour, enabling thousands of combinations to
be tried in the generation of a solution to a problem.
However, as can be seen from the Knights Tour, the time to produce a
solution may be considerable. While a 4*3 board can be solved very
quickly, the number of combinations involved for an 8*8 board are
enormous, and the solution time is very large. Therefore, while
backtracking algorithms provide an ordered and consistent problem solving
approach, solution times must be considered. In fact, algorithms may be
classed as "tractable" (solution time is polynomial i.e. reasonable) or
"intractable" (solution time is super-polynomial i.e. unreasonable). For
further details see reference 1.
The algorithm design is also important with such tasks, and every effort
should be made to reduce the processing inside the recursive procedure to
a minimum. With the Solitaire program, a solution was generated on an
Amstrad 1512 running Turbo Pascal V4 in 84 hrs, 12 min & 30 s, which isn't
exactly quick. However, the method of solution is very naive, and with a
little work the solution time could be reduced quite dramatically (I would
be interested to hear of any improvements in solution time).
Finally, here is the solution that the computer generated for solitaire
(1,1 represents the top left of the square matrix used to hold the board);
Jump 2,4 over 3,4. Jump 3,2 over 3,3. Jump 1,3 over 2,3.
Jump 1,5 over 1,4. Jump 3,4 over 3,3. Jump 3,1 over 3,2.
Jump 3,5 over 2,5. Jump 3,7 over 3,6. Jump 4,3 over 3,3.
Jump 1,3 over 2,3. Jump 4,1 over 4,2. Jump 4,3 over 3,3.
Jump 4,5 over 3,5. Jump 1,5 over 2,5. Jump 4,7 over 4,6.
Jump 4,5 over 3,5. Jump 6,3 over 5,3. Jump 5,1 over 5,2.
Jump 5,3 over 4,3. Jump 2,3 over 3,3. Jump 4,3 over 4,4.
Jump 5,5 over 4,5. Jump 2,5 over 3,5. Jump 5,7 over 5,6.
Jump 5,4 over 5,5. Jump 7,5 over 6,5. Jump 4,5 over 5,5.
Jump 7,3 over 7,4. Jump 7,5 over 6,5. Jump 5,6 over 5,5.
Jump 6,4 over 5,4.
00000000 52 65 63 75 72 73 69 6f 6e 20 61 6e 64 20 42 61 |Recursion and Ba|
00000010 63 6b 74 72 61 63 6b 69 6e 67 2e 20 20 20 20 20 |cktracking. |
00000020 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 52 | R|
00000030 6f 62 20 41 6e 64 65 72 73 6f 6e 2e 20 4a 75 6e |ob Anderson. Jun|
00000040 65 27 38 38 2e 0d 0d 20 49 6e 74 72 6f 64 75 63 |e'88... Introduc|
00000050 74 69 6f 6e 0d 0d 52 65 63 75 72 73 69 6f 6e 20 |tion..Recursion |
00000060 69 73 20 61 20 70 6f 77 65 72 66 75 6c 20 70 72 |is a powerful pr|
00000070 6f 67 72 61 6d 6d 69 6e 67 20 74 65 63 68 6e 69 |ogramming techni|
00000080 71 75 65 20 77 68 69 63 68 20 69 73 20 6f 66 74 |que which is oft|
00000090 65 6e 20 73 68 75 6e 6e 65 64 0d 62 65 63 61 75 |en shunned.becau|
000000a0 73 65 20 6f 66 20 69 74 73 20 73 6c 69 67 68 74 |se of its slight|
000000b0 6c 79 20 22 61 62 73 74 72 61 63 74 22 20 6e 61 |ly "abstract" na|
000000c0 74 75 72 65 2e 20 48 6f 77 65 76 65 72 20 69 74 |ture. However it|
000000d0 20 69 73 20 77 65 6c 6c 20 77 6f 72 74 68 0d 67 | is well worth.g|
000000e0 65 74 74 69 6e 67 20 74 6f 20 67 72 69 70 73 20 |etting to grips |
000000f0 77 69 74 68 2c 20 61 6e 64 20 65 76 65 6e 20 74 |with, and even t|
00000100 68 6f 75 67 68 20 6f 6e 6c 79 20 61 20 73 6d 61 |hough only a sma|
00000110 6c 6c 20 73 75 62 73 65 74 20 6f 66 20 70 72 6f |ll subset of pro|
00000120 62 6c 65 6d 73 20 61 72 65 0d 73 75 69 74 61 62 |blems are.suitab|
00000130 6c 65 20 66 6f 72 20 73 6f 6c 75 74 69 6f 6e 20 |le for solution |
00000140 75 73 69 6e 67 20 72 65 63 75 72 73 69 6f 6e 2c |using recursion,|
00000150 20 6e 6f 74 68 69 6e 67 20 65 6c 73 65 20 77 69 | nothing else wi|
00000160 6c 6c 20 64 6f 20 77 68 65 6e 20 73 75 63 68 20 |ll do when such |
00000170 61 0d 70 72 6f 62 6c 65 6d 20 69 73 20 65 6e 63 |a.problem is enc|
00000180 6f 75 6e 74 65 72 65 64 2e 0d 0d 4d 61 6e 79 20 |ountered...Many |
00000190 62 6f 6f 6b 73 20 68 61 76 65 20 62 65 65 6e 20 |books have been |
000001a0 77 72 69 74 74 65 6e 20 63 6f 6e 74 61 69 6e 69 |written containi|
000001b0 6e 67 20 73 65 63 74 69 6f 6e 73 20 6f 6e 20 72 |ng sections on r|
000001c0 65 63 75 72 73 69 6f 6e 20 28 65 73 70 65 63 69 |ecursion (especi|
000001d0 61 6c 6c 79 0d 50 41 53 43 41 4c 20 74 65 78 74 |ally.PASCAL text|
000001e0 62 6f 6f 6b 73 2c 20 72 65 66 2e 32 29 20 73 6f |books, ref.2) so|
000001f0 20 6f 6e 6c 79 20 61 20 6c 69 74 74 6c 65 20 74 | only a little t|
00000200 68 65 6f 72 79 20 69 73 20 67 69 76 65 6e 20 68 |heory is given h|
00000210 65 72 65 2e 20 4d 6f 72 65 0d 61 74 74 65 6e 74 |ere. More.attent|
00000220 69 6f 6e 20 77 69 6c 6c 20 62 65 20 67 69 76 65 |ion will be give|
00000230 6e 20 74 6f 20 62 61 63 6b 74 72 61 63 6b 69 6e |n to backtrackin|
00000240 67 20 61 6c 67 6f 72 69 74 68 6d 73 20 77 68 69 |g algorithms whi|
00000250 63 68 20 6f 66 74 65 6e 20 74 61 6b 65 20 66 75 |ch often take fu|
00000260 6c 6c 0d 61 64 76 61 6e 74 61 67 65 20 6f 66 20 |ll.advantage of |
00000270 72 65 63 75 72 73 69 6f 6e 20 74 6f 20 73 6f 6c |recursion to sol|
00000280 76 65 20 61 20 67 69 76 65 6e 20 70 72 6f 62 6c |ve a given probl|
00000290 65 6d 20 62 79 20 74 72 69 61 6c 20 61 6e 64 20 |em by trial and |
000002a0 65 72 72 6f 72 2e 20 54 77 6f 0d 73 75 63 68 20 |error. Two.such |
000002b0 65 78 61 6d 70 6c 65 73 20 61 72 65 20 54 68 65 |examples are The|
000002c0 20 4b 6e 69 67 68 74 73 20 54 6f 75 72 2c 20 61 | Knights Tour, a|
000002d0 6e 64 20 74 68 65 20 67 61 6d 65 20 6f 66 20 53 |nd the game of S|
000002e0 6f 6c 69 74 61 69 72 65 2e 0d 0d 54 68 65 72 65 |olitaire...There|
000002f0 20 61 72 65 20 74 68 72 65 65 20 70 72 6f 67 72 | are three progr|
00000300 61 6d 73 20 74 68 61 74 20 61 63 63 6f 6d 70 61 |ams that accompa|
00000310 6e 79 20 74 68 69 73 20 61 72 74 69 63 6c 65 2e |ny this article.|
00000320 20 54 68 65 20 66 69 72 73 74 20 69 73 20 61 0d | The first is a.|
00000330 73 69 6d 70 6c 65 20 50 41 53 43 41 4c 20 69 6d |simple PASCAL im|
00000340 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 6f 66 20 |plementation of |
00000350 74 68 65 20 4b 6e 69 67 68 74 73 20 54 6f 75 72 |the Knights Tour|
00000360 20 77 68 69 63 68 20 63 61 6e 20 67 65 6e 65 72 | which can gener|
00000370 61 74 65 20 61 0d 73 6f 6c 75 74 69 6f 6e 20 74 |ate a.solution t|
00000380 6f 20 74 68 65 20 70 72 6f 62 6c 65 6d 20 61 6e |o the problem an|
00000390 64 20 6f 75 74 70 75 74 20 74 68 65 20 6d 6f 76 |d output the mov|
000003a0 65 73 20 72 65 71 75 69 72 65 64 20 61 73 20 74 |es required as t|
000003b0 65 78 74 20 6f 6e 20 74 68 65 0d 73 63 72 65 65 |ext on the.scree|
000003c0 6e 2c 20 61 6e 64 20 74 68 65 20 73 65 63 6f 6e |n, and the secon|
000003d0 64 20 69 73 20 61 20 42 42 43 20 42 41 53 49 43 |d is a BBC BASIC|
000003e0 20 76 65 72 73 69 6f 6e 20 77 68 69 63 68 20 70 | version which p|
000003f0 72 6f 76 69 64 65 73 20 61 20 70 72 65 74 74 79 |rovides a pretty|
00000400 0d 64 69 73 70 6c 61 79 20 73 6f 20 74 68 61 74 |.display so that|
00000410 20 74 68 65 20 22 74 68 6f 75 67 68 74 22 20 70 | the "thought" p|
00000420 72 6f 63 65 73 73 65 73 20 74 68 61 74 20 74 68 |rocesses that th|
00000430 65 20 63 6f 6d 70 75 74 65 72 20 75 73 65 73 20 |e computer uses |
00000440 74 6f 20 6f 62 74 61 69 6e 0d 74 68 65 20 73 6f |to obtain.the so|
00000450 6c 75 74 69 6f 6e 20 63 61 6e 20 62 65 20 65 78 |lution can be ex|
00000460 61 6d 69 6e 65 64 2c 20 77 68 69 6c 65 20 70 72 |amined, while pr|
00000470 6f 76 69 64 69 6e 67 20 61 20 76 61 72 69 65 74 |oviding a variet|
00000480 79 20 6f 66 20 6f 70 74 69 6f 6e 73 20 74 6f 0d |y of options to.|
00000490 64 65 6d 6f 6e 73 74 72 61 74 65 20 74 68 65 20 |demonstrate the |
000004a0 76 65 72 73 61 74 69 6c 69 74 79 20 6f 66 20 74 |versatility of t|
000004b0 68 65 20 72 65 63 75 72 73 69 76 65 20 72 6f 75 |he recursive rou|
000004c0 74 69 6e 65 2e 20 54 68 65 20 66 69 6e 61 6c 20 |tine. The final |
000004d0 70 72 6f 67 72 61 6d 0d 28 69 6e 20 50 41 53 43 |program.(in PASC|
000004e0 41 4c 29 20 67 65 6e 65 72 61 74 65 73 20 61 20 |AL) generates a |
000004f0 73 6f 6c 75 74 69 6f 6e 20 74 6f 20 74 68 65 20 |solution to the |
00000500 67 61 6d 65 20 6f 66 20 53 6f 6c 69 74 61 69 72 |game of Solitair|
00000510 65 2c 20 73 68 6f 77 69 6e 67 20 68 6f 77 0d 62 |e, showing how.b|
00000520 61 63 6b 74 72 61 63 6b 69 6e 67 20 6d 65 74 68 |acktracking meth|
00000530 6f 64 73 20 63 61 6e 20 62 65 20 61 70 70 6c 69 |ods can be appli|
00000540 65 64 20 73 75 63 63 65 73 73 66 75 6c 6c 79 20 |ed successfully |
00000550 74 6f 20 6d 61 6e 79 20 61 70 70 6c 69 63 61 74 |to many applicat|
00000560 69 6f 6e 73 2e 0d 0d 20 57 68 61 74 20 69 73 20 |ions... What is |
00000570 72 65 63 75 72 73 69 6f 6e 3f 0d 0d 50 75 74 20 |recursion?..Put |
00000580 73 69 6d 70 6c 79 2c 20 72 65 63 75 72 73 69 6f |simply, recursio|
00000590 6e 20 69 73 20 61 20 70 72 6f 63 65 73 73 20 77 |n is a process w|
000005a0 68 65 72 65 62 79 20 61 20 70 72 6f 63 65 64 75 |hereby a procedu|
000005b0 72 65 20 6d 61 79 20 63 61 6c 6c 20 69 74 73 65 |re may call itse|
000005c0 6c 66 20 61 0d 6e 75 6d 62 65 72 20 6f 66 20 74 |lf a.number of t|
000005d0 69 6d 65 73 2e 20 41 20 73 69 6d 70 6c 65 20 62 |imes. A simple b|
000005e0 75 74 20 72 65 76 65 61 6c 69 6e 67 20 65 78 61 |ut revealing exa|
000005f0 6d 70 6c 65 20 69 73 20 74 68 65 20 67 65 6e 65 |mple is the gene|
00000600 72 61 74 69 6f 6e 20 6f 66 0d 66 61 63 74 6f 72 |ration of.factor|
00000610 69 61 6c 73 2c 20 77 68 65 72 65 20 74 68 65 20 |ials, where the |
00000620 66 61 63 74 6f 72 69 61 6c 20 28 21 29 20 6f 66 |factorial (!) of|
00000630 20 61 20 6e 75 6d 62 65 72 20 69 73 20 74 68 65 | a number is the|
00000640 20 6d 75 6c 74 69 70 6c 69 63 61 74 69 6f 6e 20 | multiplication |
00000650 6f 66 0d 74 68 65 20 73 65 71 75 65 6e 63 65 20 |of.the sequence |
00000660 6f 66 20 69 6e 74 65 67 65 72 73 20 66 72 6f 6d |of integers from|
00000670 20 31 20 74 6f 20 74 68 61 74 20 6e 75 6d 62 65 | 1 to that numbe|
00000680 72 2e 20 46 6f 72 20 65 78 61 6d 70 6c 65 3b 0d |r. For example;.|
00000690 0d 20 35 21 20 3d 20 35 2a 34 2a 33 2a 32 2a 31 |. 5! = 5*4*3*2*1|
000006a0 20 3d 20 31 32 30 0d 20 32 21 20 3d 20 32 2a 31 | = 120. 2! = 2*1|
000006b0 20 3d 20 32 0d 20 30 21 20 3d 20 31 20 20 20 20 | = 2. 0! = 1 |
000006c0 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 28 | (|
000006d0 62 79 20 64 65 66 69 6e 69 74 69 6f 6e 29 0d 0d |by definition)..|
000006e0 54 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 50 41 |The following PA|
000006f0 53 43 41 4c 20 63 6f 64 65 20 77 69 6c 6c 20 67 |SCAL code will g|
00000700 65 6e 65 72 61 74 65 20 74 68 65 20 66 61 63 74 |enerate the fact|
00000710 6f 72 69 61 6c 20 66 6f 72 20 61 6e 79 20 6c 65 |orial for any le|
00000720 67 61 6c 20 69 6e 70 75 74 0d 6e 75 6d 62 65 72 |gal input.number|
00000730 2e 0d 0d 20 20 20 20 50 52 4f 47 52 41 4d 20 66 |... PROGRAM f|
00000740 61 63 74 6f 72 69 61 6c 28 49 4e 50 55 54 2c 4f |actorial(INPUT,O|
00000750 55 54 50 55 54 29 3b 0d 20 0d 20 20 20 20 56 41 |UTPUT);. . VA|
00000760 52 20 6e 75 6d 62 65 72 20 3a 20 49 4e 54 45 47 |R number : INTEG|
00000770 45 52 3b 0d 0d 20 20 20 20 46 55 4e 43 54 49 4f |ER;.. FUNCTIO|
00000780 4e 20 66 61 63 74 28 6e 20 3a 20 49 4e 54 45 47 |N fact(n : INTEG|
00000790 45 52 29 20 3a 20 49 4e 54 45 47 45 52 3b 0d 20 |ER) : INTEGER;. |
000007a0 20 20 20 42 45 47 49 4e 0d 20 20 20 20 49 46 20 | BEGIN. IF |
000007b0 6e 20 3c 3d 20 31 20 54 48 45 4e 20 66 61 63 74 |n <= 1 THEN fact|
000007c0 20 3a 3d 20 31 0d 45 4c 53 45 20 66 61 63 74 20 | := 1.ELSE fact |
000007d0 3a 3d 20 6e 20 2a 20 66 61 63 74 28 6e 2d 31 29 |:= n * fact(n-1)|
000007e0 3b 0d 20 20 20 20 45 4e 44 3b 20 7b 20 66 61 63 |;. END; { fac|
000007f0 74 20 7d 0d 20 0d 20 20 20 20 42 45 47 49 4e 0d |t }. . BEGIN.|
00000800 20 0d 20 20 20 20 20 20 52 45 41 44 28 6e 75 6d | . READ(num|
00000810 62 65 72 29 3b 0d 20 20 20 20 20 20 57 52 49 54 |ber);. WRIT|
00000820 45 28 66 61 63 74 28 6e 75 6d 62 65 72 29 29 3b |E(fact(number));|
00000830 0d 20 0d 20 20 20 20 45 4e 44 2e 0d 20 0d 4e 6f |. . END.. .No|
00000840 74 65 20 74 68 65 20 72 65 63 75 72 73 69 76 65 |te the recursive|
00000850 20 70 72 6f 63 65 64 75 72 65 20 22 66 61 63 74 | procedure "fact|
00000860 22 20 77 68 69 63 68 20 72 65 74 75 72 6e 73 20 |" which returns |
00000870 31 20 69 66 20 69 74 73 20 61 72 67 75 6d 65 6e |1 if its argumen|
00000880 74 20 69 73 0d 6c 65 73 73 20 74 68 65 6e 20 6f |t is.less then o|
00000890 72 20 65 71 75 61 6c 20 74 6f 20 6f 6e 65 2c 20 |r equal to one, |
000008a0 6f 74 68 65 72 77 69 73 65 20 69 74 20 72 65 74 |otherwise it ret|
000008b0 75 72 6e 73 20 74 68 65 20 6e 75 6d 62 65 72 20 |urns the number |
000008c0 6d 75 6c 74 69 70 6c 69 65 64 20 62 79 0d 74 68 |multiplied by.th|
000008d0 65 20 66 61 63 74 6f 72 69 61 6c 20 6f 66 20 6f |e factorial of o|
000008e0 6e 65 20 6d 69 6e 75 73 20 74 68 65 20 6e 75 6d |ne minus the num|
000008f0 62 65 72 20 28 70 65 72 66 6f 72 6d 65 64 20 62 |ber (performed b|
00000900 79 20 74 68 65 20 73 74 61 74 65 6d 65 6e 74 0d |y the statement.|
00000910 66 61 63 74 28 6e 2d 31 29 29 2e 0d 20 0d 4d 61 |fact(n-1)).. .Ma|
00000920 6e 79 20 6d 61 74 68 65 6d 61 74 69 63 61 6c 20 |ny mathematical |
00000930 66 75 6e 63 74 69 6f 6e 73 20 61 6e 64 20 73 65 |functions and se|
00000940 72 69 65 73 20 63 61 6e 20 62 65 20 63 61 6c 63 |ries can be calc|
00000950 75 6c 61 74 65 64 20 75 73 69 6e 67 20 72 65 63 |ulated using rec|
00000960 75 72 73 69 6f 6e 2c 0d 62 75 74 20 69 6e 20 6d |ursion,.but in m|
00000970 61 6e 79 20 63 61 73 65 73 20 72 65 63 75 72 73 |any cases recurs|
00000980 69 6f 6e 20 69 73 20 6e 6f 74 20 61 62 73 6f 6c |ion is not absol|
00000990 75 74 65 6c 79 20 6e 65 63 65 73 73 61 72 79 20 |utely necessary |
000009a0 61 6e 64 20 61 20 73 69 6d 70 6c 65 72 0d 61 6c |and a simpler.al|
000009b0 67 6f 72 69 74 68 6d 20 6d 61 79 20 62 65 20 75 |gorithm may be u|
000009c0 73 65 64 2e 20 46 6f 72 20 65 78 61 6d 70 6c 65 |sed. For example|
000009d0 2c 20 74 68 65 20 66 61 63 74 6f 72 69 61 6c 20 |, the factorial |
000009e0 6d 61 79 20 73 69 6d 70 6c 79 20 62 65 20 67 65 |may simply be ge|
000009f0 6e 65 72 61 74 65 64 0d 75 73 69 6e 67 3b 0d 20 |nerated.using;. |
00000a00 0d 20 20 20 20 52 45 41 44 28 6e 75 6d 29 3b 0d |. READ(num);.|
00000a10 20 20 20 20 61 6e 73 20 3a 3d 20 31 3b 0d 20 20 | ans := 1;. |
00000a20 20 20 46 4f 52 20 6c 6f 6f 70 20 3a 3d 20 31 20 | FOR loop := 1 |
00000a30 54 4f 20 6e 75 6d 20 44 4f 0d 20 20 20 20 20 20 |TO num DO. |
00000a40 61 6e 73 20 3a 3d 20 61 6e 73 20 2a 20 6c 6f 6f |ans := ans * loo|
00000a50 70 3b 0d 20 0d 20 20 20 20 57 52 49 54 45 28 61 |p;. . WRITE(a|
00000a60 6e 73 29 3b 0d 20 0d 41 20 6d 75 63 68 20 62 65 |ns);. .A much be|
00000a70 74 74 65 72 20 65 78 61 6d 70 6c 65 20 28 62 75 |tter example (bu|
00000a80 74 20 6d 6f 72 65 20 63 6f 6d 70 6c 65 78 29 20 |t more complex) |
00000a90 69 73 20 74 68 65 20 4b 6e 69 67 68 74 73 20 54 |is the Knights T|
00000aa0 6f 75 72 2c 20 77 68 69 63 68 20 77 6f 75 6c 64 |our, which would|
00000ab0 0d 62 65 20 76 65 72 79 20 74 72 69 63 6b 79 20 |.be very tricky |
00000ac0 74 6f 20 73 6f 6c 76 65 20 77 69 74 68 6f 75 74 |to solve without|
00000ad0 20 72 65 63 75 72 73 69 6f 6e 2e 0d 20 0d 20 54 | recursion.. . T|
00000ae0 68 65 20 4b 6e 69 67 68 74 73 20 54 6f 75 72 0d |he Knights Tour.|
00000af0 0d 54 68 65 20 70 72 6f 62 6c 65 6d 20 69 73 20 |.The problem is |
00000b00 74 6f 20 6d 6f 76 65 20 61 20 73 69 6e 67 6c 65 |to move a single|
00000b10 20 6b 6e 69 67 68 74 20 6f 6e 20 61 6e 20 65 6d | knight on an em|
00000b20 70 74 79 20 63 68 65 73 73 20 62 6f 61 72 64 20 |pty chess board |
00000b30 73 75 63 68 20 74 68 61 74 0d 69 74 20 76 69 73 |such that.it vis|
00000b40 69 74 73 20 65 61 63 68 20 73 71 75 61 72 65 20 |its each square |
00000b50 6f 6e 6c 79 20 6f 6e 63 65 2e 0d 20 0d 54 68 65 |only once.. .The|
00000b60 20 66 69 72 73 74 20 70 72 6f 67 72 61 6d 20 22 | first program "|
00000b70 50 4b 6e 69 67 68 74 22 20 69 73 20 61 20 50 41 |PKnight" is a PA|
00000b80 53 43 41 4c 20 76 65 72 73 69 6f 6e 20 6f 66 20 |SCAL version of |
00000b90 61 20 73 6f 6c 75 74 69 6f 6e 20 74 6f 20 74 68 |a solution to th|
00000ba0 65 0d 70 72 6f 62 6c 65 6d 2e 20 54 68 69 73 20 |e.problem. This |
00000bb0 68 61 73 20 62 65 65 6e 20 69 6e 63 6c 75 64 65 |has been include|
00000bc0 64 20 74 6f 20 73 68 6f 77 20 74 68 65 20 73 74 |d to show the st|
00000bd0 72 75 63 74 75 72 65 20 6f 66 20 74 68 65 20 70 |ructure of the p|
00000be0 72 6f 67 72 61 6d 0d 62 65 74 74 65 72 2c 20 61 |rogram.better, a|
00000bf0 73 20 74 68 65 20 42 42 43 20 42 41 53 49 43 20 |s the BBC BASIC |
00000c00 76 65 72 73 69 6f 6e 20 68 65 6c 64 20 75 6e 64 |version held und|
00000c10 65 72 20 22 42 4b 6e 69 67 68 74 22 20 69 73 20 |er "BKnight" is |
00000c20 73 6f 6d 65 77 68 61 74 20 68 61 72 64 65 72 0d |somewhat harder.|
00000c30 74 6f 20 66 6f 6c 6c 6f 77 20 64 75 65 20 74 6f |to follow due to|
00000c40 20 74 68 65 20 65 78 74 72 61 20 63 6f 64 69 6e | the extra codin|
00000c50 67 20 69 6e 63 6c 75 64 65 64 20 74 6f 20 70 72 |g included to pr|
00000c60 6f 64 75 63 65 20 61 20 6e 69 63 65 20 67 72 61 |oduce a nice gra|
00000c70 70 68 69 63 61 6c 0d 64 69 73 70 6c 61 79 20 6f |phical.display o|
00000c80 66 20 74 68 65 20 6b 6e 69 67 68 74 20 77 68 69 |f the knight whi|
00000c90 7a 7a 69 6e 67 20 61 72 6f 75 6e 64 20 74 68 65 |zzing around the|
00000ca0 20 63 68 65 73 73 20 62 6f 61 72 64 2e 0d 0d 54 | chess board...T|
00000cb0 68 65 20 70 61 73 63 61 6c 20 76 65 72 73 69 6f |he pascal versio|
00000cc0 6e 20 73 68 6f 75 6c 64 20 72 75 6e 20 6f 6e 20 |n should run on |
00000cd0 61 6e 79 20 73 74 61 6e 64 61 72 64 20 69 6d 70 |any standard imp|
00000ce0 6c 65 6d 65 6e 74 61 74 69 6f 6e 20 6f 66 20 50 |lementation of P|
00000cf0 41 53 43 41 4c 2e 0d 48 6f 77 65 76 65 72 2c 20 |ASCAL..However, |
00000d00 49 53 4f 20 50 41 53 43 41 4c 20 6f 6e 20 74 68 |ISO PASCAL on th|
00000d10 65 20 42 42 43 20 72 65 71 75 69 72 65 73 20 74 |e BBC requires t|
00000d20 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 63 6f 6d |he following com|
00000d30 70 69 6c 65 72 20 6f 70 74 69 6f 6e 73 20 74 6f |piler options to|
00000d40 0d 62 65 20 70 6c 61 63 65 64 20 72 69 67 68 74 |.be placed right|
00000d50 20 61 74 20 74 68 65 20 62 65 67 69 6e 6e 69 6e | at the beginnin|
00000d60 67 20 6f 66 20 74 68 65 20 70 72 6f 67 72 61 6d |g of the program|
00000d70 20 28 69 65 20 62 65 66 6f 72 65 20 22 50 52 4f | (ie before "PRO|
00000d80 47 52 41 4d 22 29 3b 0d 20 0d 20 7b 24 43 33 30 |GRAM");. . {$C30|
00000d90 30 30 2c 2b 46 7d 0d 20 0d 57 68 65 6e 20 74 68 |00,+F}. .When th|
00000da0 65 20 70 72 6f 67 72 61 6d 20 69 73 20 72 75 6e |e program is run|
00000db0 6e 69 6e 67 20 61 20 63 6f 6e 73 74 61 6e 74 20 |ning a constant |
00000dc0 75 70 64 61 74 65 20 61 62 6f 75 74 20 74 68 65 |update about the|
00000dd0 20 63 75 72 72 65 6e 74 20 73 74 61 74 65 20 6f | current state o|
00000de0 66 0d 73 6f 6c 75 74 69 6f 6e 20 69 73 20 67 69 |f.solution is gi|
00000df0 76 65 6e 2c 20 61 6e 64 20 75 70 6f 6e 20 63 6f |ven, and upon co|
00000e00 6d 70 6c 65 74 69 6f 6e 20 74 68 65 20 73 6f 6c |mpletion the sol|
00000e10 75 74 69 6f 6e 20 69 73 20 6f 75 74 70 75 74 2e |ution is output.|
00000e20 20 4e 6f 74 65 20 74 68 61 74 0d 64 69 66 66 65 | Note that.diffe|
00000e30 72 65 6e 74 20 70 61 72 61 6d 65 74 65 72 73 20 |rent parameters |
00000e40 74 6f 20 74 68 65 20 70 72 6f 62 6c 65 6d 20 6d |to the problem m|
00000e50 61 79 20 62 65 20 73 70 65 63 69 66 69 65 64 20 |ay be specified |
00000e60 69 6e 20 74 68 65 20 43 4f 4e 53 54 61 6e 74 0d |in the CONSTant.|
00000e70 64 65 63 6c 61 72 61 74 69 6f 6e 73 20 69 6e 20 |declarations in |
00000e80 74 68 65 20 73 6f 75 72 63 65 20 63 6f 64 65 2c |the source code,|
00000e90 20 69 6e 63 6c 75 64 69 6e 67 20 62 6f 61 72 64 | including board|
00000ea0 20 73 69 7a 65 2c 20 73 74 61 72 74 20 70 6f 73 | size, start pos|
00000eb0 69 74 69 6f 6e 0d 65 74 63 2e 2e 0d 20 0d 54 68 |ition.etc... .Th|
00000ec0 65 20 42 41 53 49 43 20 76 65 72 73 69 6f 6e 20 |e BASIC version |
00000ed0 69 73 20 6d 6f 72 65 20 76 65 72 73 61 74 69 6c |is more versatil|
00000ee0 65 2c 20 65 6e 61 62 6c 69 6e 67 20 62 6f 61 72 |e, enabling boar|
00000ef0 64 20 64 69 6d 65 6e 73 69 6f 6e 73 20 61 6e 64 |d dimensions and|
00000f00 20 73 74 61 72 74 0d 70 6f 73 69 74 69 6f 6e 20 | start.position |
00000f10 74 6f 20 62 65 20 69 6e 70 75 74 20 64 69 72 65 |to be input dire|
00000f20 63 74 6c 79 20 28 73 69 6d 70 6c 79 20 66 6f 6c |ctly (simply fol|
00000f30 6c 6f 77 20 74 68 65 20 70 72 6f 6d 70 74 73 29 |low the prompts)|
00000f40 2c 20 61 66 74 65 72 2d 77 68 69 63 68 20 74 68 |, after-which th|
00000f50 65 0d 72 65 71 75 69 72 65 64 20 73 69 7a 65 20 |e.required size |
00000f60 62 6f 61 72 64 20 69 73 20 64 72 61 77 6e 20 61 |board is drawn a|
00000f70 6e 64 20 74 68 65 20 6b 6e 69 67 68 74 20 70 75 |nd the knight pu|
00000f80 74 20 69 6e 20 74 68 65 20 73 74 61 72 74 20 70 |t in the start p|
00000f90 6f 73 69 74 69 6f 6e 2e 0d 54 68 65 6e 2c 20 62 |osition..Then, b|
00000fa0 79 20 70 72 65 73 73 69 6e 67 20 22 53 22 2c 20 |y pressing "S", |
00000fb0 74 68 65 20 6b 6e 69 67 68 74 20 77 69 6c 6c 20 |the knight will |
00000fc0 6d 6f 76 65 20 6f 6e 65 20 73 74 65 70 20 61 74 |move one step at|
00000fd0 20 61 20 74 69 6d 65 20 61 72 6f 75 6e 64 20 74 | a time around t|
00000fe0 68 65 0d 62 6f 61 72 64 2c 20 77 69 74 68 20 74 |he.board, with t|
00000ff0 68 65 20 6d 6f 76 65 73 20 61 6c 73 6f 20 62 65 |he moves also be|
00001000 69 6e 67 20 6f 75 74 70 75 74 20 61 73 20 74 65 |ing output as te|
00001010 78 74 20 74 6f 20 74 68 65 20 72 69 67 68 74 20 |xt to the right |
00001020 6f 66 20 74 68 65 0d 73 63 72 65 65 6e 2e 20 4e |of the.screen. N|
00001030 6f 74 65 20 68 6f 77 20 74 68 65 20 6b 6e 69 67 |ote how the knig|
00001040 68 74 20 6d 75 73 74 20 62 61 63 6b 74 72 61 63 |ht must backtrac|
00001050 6b 20 73 6f 20 61 73 20 74 6f 20 74 72 79 20 61 |k so as to try a|
00001060 20 64 69 66 66 65 72 65 6e 74 20 70 61 74 68 0d | different path.|
00001070 77 68 65 6e 20 69 74 20 62 65 63 6f 6d 65 73 20 |when it becomes |
00001080 73 74 75 63 6b 2e 20 50 72 65 73 73 69 6e 67 20 |stuck. Pressing |
00001090 22 43 22 20 6d 61 6b 65 73 20 74 68 65 20 6b 6e |"C" makes the kn|
000010a0 69 67 68 74 20 63 6f 6e 74 69 6e 75 6f 75 73 6c |ight continuousl|
000010b0 79 20 73 65 61 72 63 68 0d 66 6f 72 20 61 20 73 |y search.for a s|
000010c0 6f 6c 75 74 69 6f 6e 2c 20 62 75 74 20 6d 61 79 |olution, but may|
000010d0 20 62 65 20 70 6c 61 63 65 64 20 62 61 63 6b 20 | be placed back |
000010e0 69 6e 74 6f 20 73 69 6e 67 6c 65 20 73 74 65 70 |into single step|
000010f0 20 6d 6f 64 65 20 62 79 20 70 72 65 73 73 69 6e | mode by pressin|
00001100 67 0d 22 53 22 20 61 67 61 69 6e 2e 20 50 72 65 |g."S" again. Pre|
00001110 73 73 69 6e 67 20 22 52 22 20 72 65 73 74 61 72 |ssing "R" restar|
00001120 74 73 20 74 68 65 20 70 72 6f 67 72 61 6d 20 74 |ts the program t|
00001130 6f 20 65 6e 61 62 6c 65 20 6e 65 77 20 73 74 61 |o enable new sta|
00001140 72 74 0d 70 61 72 61 6d 65 74 65 72 73 20 74 6f |rt.parameters to|
00001150 20 62 65 20 65 6e 74 65 72 65 64 2e 0d 20 0d 49 | be entered.. .I|
00001160 66 20 61 20 73 6f 6c 75 74 69 6f 6e 20 69 73 20 |f a solution is |
00001170 66 6f 75 6e 64 20 74 68 65 6e 20 74 68 65 20 66 |found then the f|
00001180 6f 6c 6c 6f 77 69 6e 67 20 6f 70 74 69 6f 6e 73 |ollowing options|
00001190 20 61 72 65 20 70 72 65 73 65 6e 74 65 64 3b 0d | are presented;.|
000011a0 20 0d 20 22 52 22 20 2d 20 72 65 73 74 61 72 74 | . "R" - restart|
000011b0 20 70 72 6f 67 72 61 6d 2e 0d 20 22 50 22 20 2d | program.. "P" -|
000011c0 20 6f 75 74 70 75 74 20 73 6f 6c 75 74 69 6f 6e | output solution|
000011d0 20 74 6f 20 70 72 69 6e 74 65 72 2e 0d 20 22 46 | to printer.. "F|
000011e0 22 20 2d 20 6f 75 74 70 75 74 20 73 6f 6c 75 74 |" - output solut|
000011f0 69 6f 6e 20 74 6f 20 66 69 6c 65 2e 0d 20 22 53 |ion to file.. "S|
00001200 22 20 2d 20 6f 75 74 70 75 74 20 73 6f 6c 75 74 |" - output solut|
00001210 69 6f 6e 20 74 6f 20 73 63 72 65 65 6e 2e 0d 20 |ion to screen.. |
00001220 22 45 22 20 2d 20 65 78 69 74 20 70 72 6f 67 72 |"E" - exit progr|
00001230 61 6d 2e 0d 20 0d 54 68 65 20 70 72 6f 67 72 61 |am.. .The progra|
00001240 6d 20 73 68 6f 75 6c 64 20 77 6f 72 6b 20 6f 6e |m should work on|
00001250 20 61 6e 79 20 69 6d 70 6c 65 6d 65 6e 74 61 74 | any implementat|
00001260 69 6f 6e 20 6f 66 20 42 42 43 20 42 41 53 49 43 |ion of BBC BASIC|
00001270 2c 20 62 75 74 20 69 66 20 6e 6f 0d 73 68 61 64 |, but if no.shad|
00001280 6f 77 20 6d 6f 64 65 20 69 73 20 61 76 61 69 6c |ow mode is avail|
00001290 61 62 6c 65 20 28 65 67 2e 20 69 6e 20 61 20 73 |able (eg. in a s|
000012a0 74 61 6e 64 61 72 64 20 42 42 43 20 27 42 27 29 |tandard BBC 'B')|
000012b0 20 74 68 65 6e 20 6c 69 6e 65 20 36 30 20 73 68 | then line 60 sh|
000012c0 6f 75 6c 64 0d 62 65 20 63 68 61 6e 67 65 64 20 |ould.be changed |
000012d0 62 79 20 73 65 74 74 69 6e 67 20 6d 6f 64 65 25 |by setting mode%|
000012e0 20 74 6f 20 34 20 69 6e 73 74 65 61 64 20 6f 66 | to 4 instead of|
000012f0 20 31 32 39 2e 20 54 68 69 73 20 77 69 6c 6c 20 | 129. This will |
00001300 73 69 6d 70 6c 79 20 6d 65 61 6e 0d 74 68 61 74 |simply mean.that|
00001310 20 6f 6e 6c 79 20 74 77 6f 20 63 6f 6c 6f 75 72 | only two colour|
00001320 73 20 61 72 65 20 75 73 65 64 20 66 6f 72 20 74 |s are used for t|
00001330 68 65 20 64 69 73 70 6c 61 79 20 69 6e 73 74 65 |he display inste|
00001340 61 64 20 6f 66 20 66 6f 75 72 2e 0d 20 0d 20 48 |ad of four.. . H|
00001350 6f 77 20 74 68 65 20 70 72 6f 67 72 61 6d 73 20 |ow the programs |
00001360 77 6f 72 6b 3a 0d 20 0d 41 20 68 75 6d 61 6e 20 |work:. .A human |
00001370 63 6f 75 6c 64 20 67 6f 20 61 62 6f 75 74 20 73 |could go about s|
00001380 6f 6c 76 69 6e 67 20 74 68 65 20 4b 6e 69 67 68 |olving the Knigh|
00001390 74 73 20 54 6f 75 72 20 62 79 20 73 69 6d 70 6c |ts Tour by simpl|
000013a0 79 20 63 68 6f 6f 73 69 6e 67 20 61 0d 72 61 6e |y choosing a.ran|
000013b0 64 6f 6d 20 73 65 6c 65 63 74 69 6f 6e 20 6f 66 |dom selection of|
000013c0 20 6d 6f 76 65 73 20 75 6e 74 69 6c 20 6e 6f 20 | moves until no |
000013d0 6d 6f 72 65 20 61 72 65 20 70 6f 73 73 69 62 6c |more are possibl|
000013e0 65 2e 20 49 66 20 73 6f 6d 65 20 6f 66 20 74 68 |e. If some of th|
000013f0 65 0d 73 71 75 61 72 65 73 20 72 65 6d 61 69 6e |e.squares remain|
00001400 65 64 20 75 6e 2d 76 69 73 69 74 65 64 20 74 68 |ed un-visited th|
00001410 65 6e 20 74 68 65 20 70 61 74 68 20 74 61 6b 65 |en the path take|
00001420 6e 20 63 6f 75 6c 64 20 62 65 20 72 65 76 65 72 |n could be rever|
00001430 73 65 64 20 61 20 66 65 77 0d 6d 6f 76 65 73 20 |sed a few.moves |
00001440 61 6e 64 20 64 69 66 66 65 72 65 6e 74 20 70 61 |and different pa|
00001450 74 68 73 20 74 61 6b 65 6e 20 75 6e 74 69 6c 20 |ths taken until |
00001460 61 20 73 6f 6c 75 74 69 6f 6e 20 77 61 73 20 66 |a solution was f|
00001470 6f 75 6e 64 2e 20 4e 6f 77 20 63 6f 6d 70 75 74 |ound. Now comput|
00001480 65 72 73 0d 61 72 65 20 76 65 72 79 20 67 6f 6f |ers.are very goo|
00001490 64 20 61 74 20 70 65 72 66 6f 72 6d 69 6e 67 20 |d at performing |
000014a0 6d 75 6e 64 61 6e 65 20 74 61 73 6b 73 20 76 65 |mundane tasks ve|
000014b0 72 79 20 71 75 69 63 6b 6c 79 2c 20 73 6f 20 77 |ry quickly, so w|
000014c0 65 20 63 61 6e 20 77 72 69 74 65 20 61 0d 70 72 |e can write a.pr|
000014d0 6f 67 72 61 6d 20 74 6f 20 67 65 6e 65 72 61 74 |ogram to generat|
000014e0 65 20 61 20 70 61 74 68 2c 20 63 68 65 63 6b 20 |e a path, check |
000014f0 69 66 20 69 74 20 69 73 20 61 20 73 6f 6c 75 74 |if it is a solut|
00001500 69 6f 6e 2c 20 61 6e 64 20 69 66 20 6e 6f 74 20 |ion, and if not |
00001510 74 68 65 6e 20 69 74 0d 63 61 6e 20 42 41 43 4b |then it.can BACK|
00001520 54 52 41 43 4b 20 61 6c 6f 6e 67 20 74 68 65 20 |TRACK along the |
00001530 63 75 72 72 65 6e 74 20 70 61 74 68 20 61 6e 64 |current path and|
00001540 20 74 72 79 20 61 20 64 69 66 66 65 72 65 6e 74 | try a different|
00001550 20 72 6f 75 74 65 2e 20 53 6f 20 74 6f 0d 73 74 | route. So to.st|
00001560 61 72 74 20 77 69 74 68 20 74 68 65 20 4b 6e 69 |art with the Kni|
00001570 67 68 74 20 68 61 73 20 65 69 67 68 74 20 70 6f |ght has eight po|
00001580 73 73 69 62 6c 65 20 6d 6f 76 65 73 2c 20 61 6e |ssible moves, an|
00001590 64 20 66 6f 72 20 65 61 63 68 20 6f 66 20 74 68 |d for each of th|
000015a0 6f 73 65 0d 61 6e 6f 74 68 65 72 20 65 69 67 68 |ose.another eigh|
000015b0 74 20 6d 6f 76 65 73 20 61 72 65 20 70 6f 73 73 |t moves are poss|
000015c0 69 62 6c 65 2c 20 61 6e 64 20 73 6f 20 6f 6e 2e |ible, and so on.|
000015d0 20 49 66 20 75 70 6f 6e 20 6d 61 6b 69 6e 67 20 | If upon making |
000015e0 61 20 6d 6f 76 65 20 74 68 65 0d 4b 6e 69 67 68 |a move the.Knigh|
000015f0 74 20 69 73 20 73 74 75 63 6b 2c 20 74 68 65 6e |t is stuck, then|
00001600 20 69 74 20 63 61 6e 20 62 61 63 6b 74 72 61 63 | it can backtrac|
00001610 6b 20 74 6f 20 69 74 73 20 70 72 65 76 69 6f 75 |k to its previou|
00001620 73 20 70 6f 73 69 74 69 6f 6e 20 61 6e 64 20 74 |s position and t|
00001630 72 79 0d 6f 6e 65 20 6f 66 20 74 68 65 20 6f 74 |ry.one of the ot|
00001640 68 65 72 20 73 65 76 65 6e 20 6d 6f 76 65 73 2e |her seven moves.|
00001650 0d 20 0d 54 68 69 73 20 69 73 20 61 6c 6c 20 76 |. .This is all v|
00001660 65 72 79 20 77 65 6c 6c 2c 20 62 75 74 20 68 6f |ery well, but ho|
00001670 77 20 64 6f 20 77 65 20 63 68 65 63 6b 20 74 68 |w do we check th|
00001680 61 74 20 61 6c 6c 20 70 6f 73 73 69 62 6c 65 20 |at all possible |
00001690 70 61 74 68 73 20 61 72 65 0d 74 72 69 65 64 2c |paths are.tried,|
000016a0 20 61 6e 64 20 74 68 61 74 20 6e 6f 20 70 61 74 | and that no pat|
000016b0 68 73 20 61 72 65 20 72 65 70 65 61 74 65 64 3f |hs are repeated?|
000016c0 20 43 6f 6e 73 69 64 65 72 20 61 6c 67 6f 72 69 | Consider algori|
000016d0 74 68 6d 20 31 2e 0d 20 0d 20 31 20 46 55 4e 43 |thm 1.. . 1 FUNC|
000016e0 54 49 4f 4e 20 74 72 79 6e 65 78 74 6d 6f 76 65 |TION trynextmove|
000016f0 20 3a 20 42 4f 4f 4c 45 41 4e 3b 0d 20 32 0d 20 | : BOOLEAN;. 2. |
00001700 33 20 49 6e 69 74 69 61 6c 69 73 65 20 38 20 70 |3 Initialise 8 p|
00001710 6f 73 73 69 62 6c 65 20 6d 6f 76 65 73 20 66 6f |ossible moves fo|
00001720 72 20 74 68 65 20 4b 6e 69 67 68 74 2e 0d 20 34 |r the Knight.. 4|
00001730 20 52 45 50 45 41 54 0d 20 35 20 20 20 53 65 6c | REPEAT. 5 Sel|
00001740 65 63 74 20 6e 65 78 74 20 6d 6f 76 65 20 66 72 |ect next move fr|
00001750 6f 6d 20 6c 69 73 74 20 6f 66 20 65 69 67 68 74 |om list of eight|
00001760 20 70 6f 73 73 69 62 6c 65 20 6d 6f 76 65 73 2e | possible moves.|
00001770 0d 20 36 20 20 20 49 46 20 6d 6f 76 65 20 69 73 |. 6 IF move is|
00001780 20 6c 65 67 61 6c 0d 20 37 20 20 20 54 48 45 4e | legal. 7 THEN|
00001790 0d 20 38 20 20 20 20 20 4d 61 6b 65 20 74 68 65 |. 8 Make the|
000017a0 20 6d 6f 76 65 2e 0d 20 39 20 20 20 20 20 49 46 | move.. 9 IF|
000017b0 20 62 6f 61 72 64 20 6e 6f 74 20 66 75 6c 6c 0d | board not full.|
000017c0 20 31 30 20 20 20 20 54 48 45 4e 0d 20 31 31 20 | 10 THEN. 11 |
000017d0 20 20 20 20 20 73 75 63 63 65 73 73 20 3a 3d 20 | success := |
000017e0 74 72 79 6e 65 78 74 6d 6f 76 65 3b 0d 20 31 32 |trynextmove;. 12|
000017f0 20 20 20 20 20 20 49 46 20 4e 4f 54 28 73 75 63 | IF NOT(suc|
00001800 63 65 73 73 29 0d 20 20 20 20 20 20 20 20 20 54 |cess). T|
00001810 48 45 4e 20 45 72 61 73 65 20 6c 61 73 74 20 6d |HEN Erase last m|
00001820 6f 76 65 20 62 65 63 61 75 73 65 20 6e 6f 20 70 |ove because no p|
00001830 61 74 68 20 63 61 6e 0d 20 20 20 20 20 20 20 20 |ath can. |
00001840 20 62 65 20 67 65 6e 65 72 61 74 65 64 20 66 72 | be generated fr|
00001850 6f 6d 20 69 74 2e 0d 20 31 33 20 55 4e 54 49 4c |om it.. 13 UNTIL|
00001860 20 73 75 63 63 65 73 73 20 4f 52 20 61 6c 6c 20 | success OR all |
00001870 65 69 67 68 74 20 6d 6f 76 65 73 20 68 61 76 65 |eight moves have|
00001880 20 62 65 65 6e 20 74 72 69 65 64 2e 0d 20 0d 20 | been tried.. . |
00001890 41 6c 67 6f 72 69 74 68 6d 20 31 2e 0d 0d 54 68 |Algorithm 1...Th|
000018a0 69 73 20 69 73 20 61 20 62 61 63 6b 74 72 61 63 |is is a backtrac|
000018b0 6b 69 6e 67 20 61 6c 67 6f 72 69 74 68 6d 20 77 |king algorithm w|
000018c0 68 69 63 68 20 75 73 65 73 20 72 65 63 75 72 73 |hich uses recurs|
000018d0 69 6f 6e 20 74 6f 20 6b 65 65 70 20 61 6e 20 6f |ion to keep an o|
000018e0 72 64 65 72 65 64 0d 72 65 63 6f 72 64 20 6f 66 |rdered.record of|
000018f0 20 74 68 65 20 70 61 74 68 73 20 74 68 61 74 20 | the paths that |
00001900 68 61 76 65 20 62 65 65 6e 20 74 72 69 65 64 2e |have been tried.|
00001910 20 4e 6f 74 65 20 6c 69 6e 65 20 31 31 20 77 68 | Note line 11 wh|
00001920 69 63 68 20 72 65 63 75 72 73 69 76 65 6c 79 0d |ich recursively.|
00001930 63 61 6c 6c 73 20 74 72 79 6e 65 78 74 6d 6f 76 |calls trynextmov|
00001940 65 2e 20 54 68 65 20 73 65 71 75 65 6e 63 65 20 |e. The sequence |
00001950 6f 66 20 65 76 65 6e 74 73 20 75 70 6f 6e 20 63 |of events upon c|
00001960 61 6c 6c 69 6e 67 20 74 72 79 6e 65 78 74 6d 6f |alling trynextmo|
00001970 76 65 20 61 72 65 3b 0d 28 61 73 73 75 6d 69 6e |ve are;.(assumin|
00001980 67 20 74 68 65 20 4b 6e 69 67 68 74 20 74 6f 20 |g the Knight to |
00001990 62 65 20 69 6e 69 74 69 61 6c 6c 79 20 61 74 20 |be initially at |
000019a0 74 68 65 20 74 6f 70 20 72 69 67 68 74 20 6f 66 |the top right of|
000019b0 20 74 68 65 20 38 2a 38 20 62 6f 61 72 64 20 61 | the 8*8 board a|
000019c0 6e 64 0d 74 68 65 20 66 69 72 73 74 20 6d 6f 76 |nd.the first mov|
000019d0 65 20 73 65 6c 65 63 74 65 64 20 6f 66 20 74 68 |e selected of th|
000019e0 65 20 65 69 67 68 74 20 70 6f 73 73 69 62 6c 65 |e eight possible|
000019f0 20 69 73 20 6c 65 66 74 20 6f 6e 65 20 73 71 75 | is left one squ|
00001a00 61 72 65 20 61 6e 64 20 64 6f 77 6e 0d 74 77 6f |are and down.two|
00001a10 29 0d 20 0d 20 2d 20 46 69 72 73 74 20 63 61 6c |). . - First cal|
00001a20 6c 20 74 6f 20 74 72 79 6e 65 78 74 6d 6f 76 65 |l to trynextmove|
00001a30 20 6d 6f 76 65 73 20 4b 6e 69 67 68 74 20 6c 65 | moves Knight le|
00001a40 66 74 20 6f 6e 65 20 61 6e 64 20 64 6f 77 6e 20 |ft one and down |
00001a50 74 77 6f 20 73 71 75 61 72 65 73 2e 0d 20 2d 20 |two squares.. - |
00001a60 41 20 72 65 63 75 72 73 69 76 65 20 63 61 6c 6c |A recursive call|
00001a70 20 74 6f 20 74 72 79 6e 65 78 74 6d 6f 76 65 20 | to trynextmove |
00001a80 72 65 73 75 6c 74 73 20 69 6e 20 74 68 65 20 4b |results in the K|
00001a90 6e 69 67 68 74 20 6d 6f 76 69 6e 67 20 6c 65 66 |night moving lef|
00001aa0 74 20 6f 6e 65 0d 61 6e 64 20 64 6f 77 6e 20 74 |t one.and down t|
00001ab0 77 6f 20 73 71 75 61 72 65 73 20 66 72 6f 6d 20 |wo squares from |
00001ac0 69 74 73 20 63 75 72 72 65 6e 74 20 70 6f 73 69 |its current posi|
00001ad0 74 69 6f 6e 2e 0d 20 2d 20 41 20 73 65 63 6f 6e |tion.. - A secon|
00001ae0 64 20 72 65 63 75 72 73 69 76 65 20 63 61 6c 6c |d recursive call|
00001af0 20 72 65 73 75 6c 74 73 20 69 6e 20 74 68 65 20 | results in the |
00001b00 73 61 6d 65 20 6d 6f 76 65 20 61 67 61 69 6e 2e |same move again.|
00001b10 0d 20 2d 20 41 20 74 68 69 72 64 20 72 65 63 75 |. - A third recu|
00001b20 72 73 69 76 65 20 63 61 6c 6c 20 61 74 74 65 6d |rsive call attem|
00001b30 70 74 73 20 74 68 65 20 73 61 6d 65 20 6d 6f 76 |pts the same mov|
00001b40 65 20 61 67 61 69 6e 2c 20 62 75 74 20 66 69 6e |e again, but fin|
00001b50 64 73 20 74 68 65 0d 4b 6e 69 67 68 74 20 61 74 |ds the.Knight at|
00001b60 20 74 68 65 20 62 6f 74 74 6f 6d 20 6f 66 20 74 | the bottom of t|
00001b70 68 65 20 62 6f 61 72 64 2c 20 73 6f 20 73 65 6c |he board, so sel|
00001b80 65 63 74 73 20 74 68 65 20 6e 65 78 74 20 6d 6f |ects the next mo|
00001b90 76 65 20 69 6e 20 74 68 65 0d 63 61 6e 64 69 64 |ve in the.candid|
00001ba0 61 74 65 20 6c 69 73 74 2e 0d 20 0d 54 68 65 20 |ate list.. .The |
00001bb0 61 62 6f 76 65 20 73 65 71 75 65 6e 63 65 20 6f |above sequence o|
00001bc0 66 20 65 76 65 6e 74 73 20 63 61 6e 20 62 65 20 |f events can be |
00001bd0 65 78 61 6d 69 6e 65 64 20 75 73 69 6e 67 20 22 |examined using "|
00001be0 42 4b 6e 69 67 68 74 22 2e 0d 20 0d 42 61 63 6b |BKnight".. .Back|
00001bf0 74 72 61 63 6b 69 6e 67 20 61 6c 67 6f 72 69 74 |tracking algorit|
00001c00 68 6d 73 20 68 61 76 65 20 69 6e 20 67 65 6e 65 |hms have in gene|
00001c10 72 61 6c 20 61 20 73 65 71 75 65 6e 63 65 20 6f |ral a sequence o|
00001c20 66 20 65 76 65 6e 74 73 20 77 68 69 63 68 20 63 |f events which c|
00001c30 61 6e 20 62 65 0d 61 70 70 6c 69 65 64 20 74 6f |an be.applied to|
00001c40 20 6d 61 6e 79 20 73 69 74 75 61 74 69 6f 6e 73 | many situations|
00001c50 2e 20 49 6e 20 66 61 63 74 2c 20 77 65 20 63 61 |. In fact, we ca|
00001c60 6e 20 64 65 66 69 6e 65 20 61 20 67 65 6e 65 72 |n define a gener|
00001c70 61 6c 69 73 65 64 0d 62 61 63 6b 74 72 61 63 6b |alised.backtrack|
00001c80 69 6e 67 20 61 6c 67 6f 72 69 74 68 6d 20 28 61 |ing algorithm (a|
00001c90 6c 67 6f 72 69 74 68 6d 20 32 29 2e 0d 20 0d 20 |lgorithm 2).. . |
00001ca0 50 52 4f 43 45 44 55 52 45 20 74 72 79 6e 65 78 |PROCEDURE trynex|
00001cb0 74 6d 6f 76 65 3b 0d 20 42 45 47 49 4e 0d 20 20 |tmove;. BEGIN. |
00001cc0 20 20 69 6e 69 74 69 61 6c 69 73 65 20 73 65 6c | initialise sel|
00001cd0 65 63 74 69 6f 6e 20 6f 66 20 6d 6f 76 65 73 3b |ection of moves;|
00001ce0 0d 20 20 20 20 52 45 50 45 41 54 0d 20 20 20 20 |. REPEAT. |
00001cf0 20 20 20 53 65 6c 65 63 74 20 6e 65 78 74 20 63 | Select next c|
00001d00 61 6e 64 69 64 61 74 65 20 66 72 6f 6d 20 6c 69 |andidate from li|
00001d10 73 74 20 6f 66 20 70 6f 73 73 69 62 6c 65 20 6d |st of possible m|
00001d20 6f 76 65 73 2e 0d 20 20 20 20 20 20 20 49 46 20 |oves.. IF |
00001d30 6d 6f 76 65 20 69 73 20 6c 65 67 61 6c 0d 20 20 |move is legal. |
00001d40 20 20 20 20 20 54 48 45 4e 0d 20 20 20 20 20 20 | THEN. |
00001d50 20 20 20 20 4d 61 6b 65 20 74 68 65 20 6d 6f 76 | Make the mov|
00001d60 65 3b 0d 20 20 20 20 20 20 20 20 20 20 49 46 20 |e;. IF |
00001d70 62 6f 61 72 64 20 6e 6f 74 20 66 75 6c 6c 0d 20 |board not full. |
00001d80 20 20 20 20 20 20 20 20 20 54 48 45 4e 0d 20 74 | THEN. t|
00001d90 72 79 6e 65 78 74 6d 6f 76 65 3b 0d 20 49 46 20 |rynextmove;. IF |
00001da0 4e 4f 54 28 73 75 63 63 65 73 73 29 0d 20 54 48 |NOT(success). TH|
00001db0 45 4e 20 45 72 61 73 65 20 6c 61 73 74 20 6d 6f |EN Erase last mo|
00001dc0 76 65 20 62 65 63 61 75 73 65 20 6e 6f 20 73 6f |ve because no so|
00001dd0 6c 75 74 69 6f 6e 20 63 61 6e 20 62 65 20 6d 61 |lution can be ma|
00001de0 64 65 20 66 72 6f 6d 20 74 68 61 74 20 6d 6f 76 |de from that mov|
00001df0 65 2e 0d 20 20 20 20 55 4e 54 49 4c 20 73 75 63 |e.. UNTIL suc|
00001e00 63 65 73 73 20 4f 52 20 61 6c 6c 20 65 69 67 68 |cess OR all eigh|
00001e10 74 20 6d 6f 76 65 73 20 68 61 76 65 20 62 65 65 |t moves have bee|
00001e20 6e 20 74 72 69 65 64 2e 0d 20 45 4e 44 20 74 72 |n tried.. END tr|
00001e30 79 6e 65 78 74 6d 6f 76 65 0d 0d 20 41 6c 67 6f |ynextmove.. Algo|
00001e40 72 69 74 68 6d 20 32 2e 0d 20 0d 41 72 6d 65 64 |rithm 2.. .Armed|
00001e50 20 77 69 74 68 20 61 6c 67 6f 72 69 74 68 6d 20 | with algorithm |
00001e60 32 20 77 65 20 63 61 6e 20 6e 6f 77 20 61 74 74 |2 we can now att|
00001e70 65 6d 70 74 20 74 6f 20 77 72 69 74 65 20 61 20 |empt to write a |
00001e80 70 72 6f 67 72 61 6d 20 74 6f 20 73 6f 6c 76 65 |program to solve|
00001e90 0d 53 6f 6c 69 74 61 69 72 65 2c 20 77 68 65 72 |.Solitaire, wher|
00001ea0 65 20 74 68 65 20 6f 62 6a 65 63 74 20 6f 66 20 |e the object of |
00001eb0 74 68 65 20 67 61 6d 65 20 69 73 20 74 6f 20 72 |the game is to r|
00001ec0 65 6d 6f 76 65 20 69 6e 20 70 6c 61 79 20 61 6c |emove in play al|
00001ed0 6c 20 74 68 65 20 70 65 67 73 0d 66 72 6f 6d 20 |l the pegs.from |
00001ee0 74 68 65 20 70 6c 61 79 69 6e 67 20 62 6f 61 72 |the playing boar|
00001ef0 64 20 65 78 63 65 70 74 20 74 68 65 20 6c 61 73 |d except the las|
00001f00 74 20 6f 6e 65 20 77 68 69 63 68 20 6d 75 73 74 |t one which must|
00001f10 20 66 69 6e 69 73 68 20 69 6e 20 74 68 65 20 63 | finish in the c|
00001f20 65 6e 74 72 65 0d 68 6f 6c 65 2e 20 50 65 67 73 |entre.hole. Pegs|
00001f30 20 61 72 65 20 72 65 6d 6f 76 65 64 20 62 79 20 | are removed by |
00001f40 68 6f 70 70 69 6e 67 20 6f 76 65 72 20 74 68 65 |hopping over the|
00001f50 6d 20 77 69 74 68 20 61 6e 6f 74 68 65 72 20 61 |m with another a|
00001f60 64 6a 61 63 65 6e 74 20 70 65 67 20 69 6e 74 6f |djacent peg into|
00001f70 0d 61 6e 20 65 6d 70 74 79 20 73 70 61 63 65 20 |.an empty space |
00001f80 62 65 79 6f 6e 64 2c 20 65 69 74 68 65 72 20 76 |beyond, either v|
00001f90 65 72 74 69 63 61 6c 6c 79 20 6f 72 20 68 6f 72 |ertically or hor|
00001fa0 69 7a 6f 6e 74 61 6c 6c 79 2e 20 54 68 65 20 62 |izontally. The b|
00001fb0 6f 61 72 64 20 61 74 0d 73 74 61 72 74 20 6f 66 |oard at.start of|
00001fc0 20 70 6c 61 79 20 69 73 20 67 69 76 65 6e 20 69 | play is given i|
00001fd0 6e 20 66 69 67 75 72 65 20 31 2e 0d 0d 20 20 20 |n figure 1... |
00001fe0 20 20 20 20 31 31 31 0d 20 20 20 20 20 20 20 31 | 111. 1|
00001ff0 31 31 0d 20 20 20 20 20 31 31 31 31 31 31 31 0d |11. 1111111.|
00002000 20 20 20 20 20 31 31 31 30 31 31 31 20 20 20 0d | 1110111 .|
00002010 20 20 20 20 20 31 31 31 31 31 31 31 0d 20 20 20 | 1111111. |
00002020 20 20 20 20 31 31 31 0d 20 20 20 20 20 20 20 31 | 111. 1|
00002030 31 31 0d 20 0d 46 69 67 75 72 65 20 31 20 2d 20 |11. .Figure 1 - |
00002040 69 6e 69 74 69 61 6c 20 73 6f 6c 69 74 61 69 72 |initial solitair|
00002050 65 20 62 6f 61 72 64 2e 0d 20 28 20 31 20 3d 3e |e board.. ( 1 =>|
00002060 20 70 65 67 2c 20 30 20 3d 3e 20 68 6f 6c 65 29 | peg, 0 => hole)|
00002070 0d 20 0d 46 69 72 73 74 20 6f 66 20 61 6c 6c 2c |. .First of all,|
00002080 20 61 20 6d 65 74 68 6f 64 20 6f 66 20 72 65 70 | a method of rep|
00002090 72 65 73 65 6e 74 61 74 69 6f 6e 20 6d 75 73 74 |resentation must|
000020a0 20 62 65 20 61 64 6f 70 74 65 64 2e 20 54 68 65 | be adopted. The|
000020b0 20 73 69 6d 70 6c 65 73 74 20 77 61 79 0d 69 73 | simplest way.is|
000020c0 20 74 6f 20 75 73 65 20 61 20 74 77 6f 20 64 69 | to use a two di|
000020d0 6d 65 6e 73 69 6f 6e 61 6c 20 61 72 72 61 79 20 |mensional array |
000020e0 6f 66 20 62 6f 6f 6c 65 61 6e 20 76 61 6c 75 65 |of boolean value|
000020f0 73 2c 20 77 68 65 72 65 20 54 52 55 45 20 69 6d |s, where TRUE im|
00002100 70 6c 69 65 73 20 61 6e 0d 68 6f 6c 65 2c 20 61 |plies an.hole, a|
00002110 6e 64 20 46 41 4c 53 45 20 69 6d 70 6c 69 65 73 |nd FALSE implies|
00002120 20 61 20 70 65 67 2e 20 4e 6f 74 65 20 74 68 61 | a peg. Note tha|
00002130 74 20 74 68 69 73 20 69 73 20 73 6c 69 67 68 74 |t this is slight|
00002140 6c 79 20 77 61 73 74 65 66 75 6c 2c 0d 62 65 63 |ly wasteful,.bec|
00002150 61 75 73 65 20 6e 6f 74 20 61 6c 6c 20 74 68 65 |ause not all the|
00002160 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20 74 68 65 | elements of the|
00002170 20 61 72 72 61 79 20 77 69 6c 6c 20 62 65 20 75 | array will be u|
00002180 73 65 64 20 64 75 65 20 74 6f 20 74 68 65 20 75 |sed due to the u|
00002190 6e 75 73 75 61 6c 0d 73 68 61 70 65 20 6f 66 20 |nusual.shape of |
000021a0 74 68 65 20 62 6f 61 72 64 2c 20 77 68 69 63 68 |the board, which|
000021b0 20 61 6c 73 6f 20 6d 65 61 6e 73 20 74 68 61 74 | also means that|
000021c0 20 74 68 65 20 72 6f 75 74 69 6e 65 20 28 22 6c | the routine ("l|
000021d0 65 67 61 6c 70 6f 73 22 29 20 69 73 0d 72 65 71 |egalpos") is.req|
000021e0 75 69 72 65 64 20 74 6f 20 63 68 65 63 6b 20 74 |uired to check t|
000021f0 68 61 74 20 61 6e 79 20 6d 6f 76 65 20 72 65 6d |hat any move rem|
00002200 61 69 6e 73 20 69 6e 73 69 64 65 20 74 68 65 20 |ains inside the |
00002210 63 72 6f 73 73 20 73 68 61 70 65 2e 0d 20 0d 57 |cross shape.. .W|
00002220 65 20 6e 6f 77 20 6e 65 65 64 20 61 20 77 61 79 |e now need a way|
00002230 20 6f 66 20 73 65 6c 65 63 74 69 6e 67 20 61 6c | of selecting al|
00002240 6c 20 70 6f 73 73 69 62 6c 65 20 6d 6f 76 65 73 |l possible moves|
00002250 2e 20 54 68 65 20 65 61 73 69 65 73 74 20 77 61 |. The easiest wa|
00002260 79 20 69 73 20 74 6f 0d 74 61 6b 65 20 65 61 63 |y is to.take eac|
00002270 68 20 70 65 67 20 69 6e 20 74 75 72 6e 20 61 6e |h peg in turn an|
00002280 64 2c 20 69 66 20 61 20 6c 65 67 61 6c 20 6d 6f |d, if a legal mo|
00002290 76 65 20 63 61 6e 20 62 65 20 6d 61 64 65 2c 20 |ve can be made, |
000022a0 74 68 61 74 20 6d 6f 76 65 20 73 68 6f 75 6c 64 |that move should|
000022b0 0d 62 65 20 72 65 63 6f 72 64 65 64 20 61 6e 64 |.be recorded and|
000022c0 20 74 68 65 6e 20 61 20 72 65 63 75 72 73 69 76 | then a recursiv|
000022d0 65 20 63 61 6c 6c 20 74 6f 20 22 74 72 79 6d 6f |e call to "trymo|
000022e0 76 65 22 20 6d 61 64 65 20 74 6f 20 74 72 79 20 |ve" made to try |
000022f0 61 6e 64 20 6d 61 6b 65 0d 66 75 72 74 68 65 72 |and make.further|
00002300 20 6d 6f 76 65 73 2e 20 54 68 69 73 20 63 6f 6e | moves. This con|
00002310 74 69 6e 75 65 73 20 75 6e 74 69 6c 20 74 68 65 |tinues until the|
00002320 20 67 61 6d 65 20 69 73 20 66 69 6e 69 73 68 65 | game is finishe|
00002330 64 2c 20 6f 72 20 6e 6f 20 66 75 72 74 68 65 72 |d, or no further|
00002340 0d 6d 6f 76 65 73 20 63 61 6e 20 62 65 20 6d 61 |.moves can be ma|
00002350 64 65 20 69 6e 20 77 68 69 63 68 20 63 61 73 65 |de in which case|
00002360 20 62 61 63 6b 74 72 61 63 6b 69 6e 67 20 6f 63 | backtracking oc|
00002370 63 75 72 73 2e 0d 20 0d 54 68 65 20 50 41 53 43 |curs.. .The PASC|
00002380 41 4c 20 70 72 6f 67 72 61 6d 20 22 50 2f 53 4f |AL program "P/SO|
00002390 4c 22 20 70 65 72 66 6f 72 6d 73 20 74 68 69 73 |L" performs this|
000023a0 2c 20 61 6e 64 20 61 73 20 62 65 66 6f 72 65 20 |, and as before |
000023b0 69 66 20 49 53 4f 20 50 41 53 43 41 4c 20 6f 6e |if ISO PASCAL on|
000023c0 0d 74 68 65 20 42 42 43 20 69 73 20 75 73 65 64 |.the BBC is used|
000023d0 20 74 68 65 6e 20 74 68 65 20 63 6f 6d 70 69 6c | then the compil|
000023e0 65 72 20 64 69 72 65 63 74 69 76 65 73 20 6d 65 |er directives me|
000023f0 6e 74 69 6f 6e 65 64 20 61 62 6f 76 65 20 73 68 |ntioned above sh|
00002400 6f 75 6c 64 20 62 65 0d 69 6e 63 6c 75 64 65 64 |ould be.included|
00002410 2e 0d 20 0d 20 4f 74 68 65 72 20 63 6c 61 73 73 |.. . Other class|
00002420 69 63 20 70 72 6f 62 6c 65 6d 73 20 77 69 74 68 |ic problems with|
00002430 20 72 65 63 75 72 73 69 6f 6e 2e 0d 20 0d 54 68 | recursion.. .Th|
00002440 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 61 72 65 20 |e following are |
00002450 69 6e 74 65 72 65 73 74 69 6e 67 20 70 72 6f 62 |interesting prob|
00002460 6c 65 6d 73 20 69 6e 76 6f 6c 76 69 6e 67 20 62 |lems involving b|
00002470 61 63 6b 74 72 61 63 6b 69 6e 67 20 61 6e 64 20 |acktracking and |
00002480 6f 72 0d 72 65 63 75 72 73 69 6f 6e 2e 0d 20 0d |or.recursion.. .|
00002490 47 65 6e 65 72 61 74 69 6e 67 20 74 68 65 20 66 |Generating the f|
000024a0 69 62 6f 6e 61 63 63 69 20 73 65 72 69 65 73 20 |ibonacci series |
000024b0 2d 20 54 68 65 20 66 69 62 6f 6e 61 63 63 69 20 |- The fibonacci |
000024c0 73 65 72 69 65 73 20 69 73 20 61 20 73 65 71 75 |series is a sequ|
000024d0 65 6e 63 65 20 6f 66 0d 6e 75 6d 62 65 72 73 20 |ence of.numbers |
000024e0 77 68 65 72 65 20 74 68 65 20 6e 65 78 74 20 6e |where the next n|
000024f0 75 6d 62 65 72 20 63 6f 6d 70 72 69 73 65 73 20 |umber comprises |
00002500 74 68 65 20 70 72 65 76 69 6f 75 73 20 74 77 6f |the previous two|
00002510 20 6e 75 6d 62 65 72 73 20 69 6e 20 74 68 65 0d | numbers in the.|
00002520 73 65 71 75 65 6e 63 65 20 61 64 64 65 64 20 74 |sequence added t|
00002530 6f 67 65 74 68 65 72 2e 20 54 68 65 20 66 69 72 |ogether. The fir|
00002540 73 74 20 74 77 6f 20 6e 75 6d 62 65 72 73 20 61 |st two numbers a|
00002550 72 65 20 64 65 66 69 6e 65 64 20 74 6f 20 62 65 |re defined to be|
00002560 20 31 2e 20 54 68 65 0d 66 69 72 73 74 20 31 30 | 1. The.first 10|
00002570 20 6e 75 6d 62 65 72 73 20 61 72 65 20 74 68 65 | numbers are the|
00002580 72 65 66 6f 72 65 20 31 2c 31 2c 32 2c 33 2c 35 |refore 1,1,2,3,5|
00002590 2c 38 2c 31 33 2c 32 31 2c 33 34 2c 35 35 2e 20 |,8,13,21,34,55. |
000025a0 54 68 69 73 20 73 65 71 75 65 6e 63 65 20 63 61 |This sequence ca|
000025b0 6e 0d 62 65 20 67 65 6e 65 72 61 74 65 64 20 75 |n.be generated u|
000025c0 73 69 6e 67 20 61 20 73 68 6f 72 74 20 72 65 63 |sing a short rec|
000025d0 75 72 73 69 76 65 20 70 72 6f 63 65 64 75 72 65 |ursive procedure|
000025e0 2e 0d 20 0d 54 6f 77 65 72 20 6f 66 20 48 61 6e |.. .Tower of Han|
000025f0 6f 69 20 2d 20 54 68 69 73 20 63 6f 6e 73 69 73 |oi - This consis|
00002600 74 73 20 6f 66 20 74 68 72 65 65 20 70 6f 73 74 |ts of three post|
00002610 73 2c 20 6f 6e 65 20 6f 66 20 77 68 69 63 68 20 |s, one of which |
00002620 68 61 73 20 61 20 6e 75 6d 62 65 72 0d 6f 66 20 |has a number.of |
00002630 64 69 73 63 73 20 77 69 74 68 20 68 6f 6c 65 73 |discs with holes|
00002640 20 69 6e 20 74 68 61 74 20 61 72 65 20 70 6c 61 | in that are pla|
00002650 63 65 64 20 6f 6e 20 74 68 65 20 6c 65 66 74 6d |ced on the leftm|
00002660 6f 73 74 20 70 6f 73 74 20 69 6e 20 64 65 63 72 |ost post in decr|
00002670 65 61 73 69 6e 67 0d 6f 72 64 65 72 20 6f 66 20 |easing.order of |
00002680 73 69 7a 65 20 28 74 68 65 20 6c 61 72 67 65 73 |size (the larges|
00002690 74 20 72 61 64 69 75 73 20 64 69 73 63 20 69 73 |t radius disc is|
000026a0 20 70 6c 61 63 65 64 20 61 74 20 74 68 65 20 62 | placed at the b|
000026b0 6f 74 74 6f 6d 20 6f 66 20 74 68 65 0d 70 69 6c |ottom of the.pil|
000026c0 65 29 2e 20 54 68 65 20 6f 62 6a 65 63 74 20 6f |e). The object o|
000026d0 66 20 74 68 65 20 70 75 7a 7a 6c 65 20 69 73 20 |f the puzzle is |
000026e0 74 6f 20 6d 6f 76 65 20 74 68 65 20 70 69 6c 65 |to move the pile|
000026f0 20 6f 66 20 64 69 73 63 73 20 66 72 6f 6d 20 6f | of discs from o|
00002700 6e 65 20 70 6f 73 74 0d 74 6f 20 61 6e 6f 74 68 |ne post.to anoth|
00002710 65 72 2c 20 77 69 74 68 20 74 68 65 20 63 6f 6e |er, with the con|
00002720 64 69 74 69 6f 6e 20 74 68 61 74 20 6f 6e 6c 79 |dition that only|
00002730 20 6f 6e 65 20 64 69 73 63 20 6d 61 79 20 62 65 | one disc may be|
00002740 20 6d 6f 76 65 64 20 61 74 20 61 20 74 69 6d 65 | moved at a time|
00002750 0d 61 6e 64 20 61 74 20 6e 6f 20 73 74 61 67 65 |.and at no stage|
00002760 20 6d 61 79 20 61 20 6c 61 72 67 65 72 20 64 69 | may a larger di|
00002770 73 63 20 72 65 73 74 20 6f 6e 20 61 20 73 6d 61 |sc rest on a sma|
00002780 6c 6c 65 72 20 64 69 73 63 2e 0d 20 0d 54 68 65 |ller disc.. .The|
00002790 20 45 69 67 68 74 20 51 75 65 65 6e 73 20 70 72 | Eight Queens pr|
000027a0 6f 62 6c 65 6d 20 2d 20 48 65 72 65 2c 20 65 69 |oblem - Here, ei|
000027b0 67 68 74 20 71 75 65 65 6e 73 20 6d 75 73 74 20 |ght queens must |
000027c0 62 65 20 70 6c 61 63 65 64 20 6f 6e 20 61 20 63 |be placed on a c|
000027d0 68 65 73 73 0d 62 6f 61 72 64 20 73 75 63 68 20 |hess.board such |
000027e0 74 68 61 74 20 6e 6f 20 71 75 65 65 6e 20 69 73 |that no queen is|
000027f0 20 70 6c 61 63 65 64 20 69 6e 20 63 68 65 63 6b | placed in check|
00002800 20 77 69 74 68 20 61 6e 6f 74 68 65 72 2e 20 54 | with another. T|
00002810 68 69 73 20 72 65 71 75 69 72 65 73 0d 61 6e 6f |his requires.ano|
00002820 74 68 65 72 20 62 61 63 6b 74 72 61 63 6b 69 6e |ther backtrackin|
00002830 67 20 61 6c 67 6f 72 69 74 68 6d 20 73 69 6d 69 |g algorithm simi|
00002840 6c 61 72 20 74 6f 20 74 68 65 20 6b 6e 69 67 68 |lar to the knigh|
00002850 74 73 20 74 6f 75 72 20 70 72 6f 62 6c 65 6d 2e |ts tour problem.|
00002860 0d 20 0d 20 43 6f 6e 63 6c 75 73 69 6f 6e 0d 20 |. . Conclusion. |
00002870 0d 52 65 63 75 72 73 69 6f 6e 20 69 73 20 61 20 |.Recursion is a |
00002880 70 6f 77 65 72 66 75 6c 20 74 65 63 68 6e 69 71 |powerful techniq|
00002890 75 65 20 77 68 69 63 68 20 63 61 6e 20 72 65 73 |ue which can res|
000028a0 75 6c 74 20 69 6e 20 61 20 6c 6f 74 20 6f 66 20 |ult in a lot of |
000028b0 70 72 6f 63 65 73 73 69 6e 67 0d 66 72 6f 6d 20 |processing.from |
000028c0 61 20 73 6d 61 6c 6c 20 61 6d 6f 75 6e 74 20 6f |a small amount o|
000028d0 66 20 63 6f 64 65 2e 20 49 74 20 69 73 20 65 73 |f code. It is es|
000028e0 70 65 63 69 61 6c 6c 79 20 75 73 65 66 75 6c 20 |pecially useful |
000028f0 77 69 74 68 20 62 61 63 6b 74 72 61 63 6b 69 6e |with backtrackin|
00002900 67 0d 61 6c 67 6f 72 69 74 68 6d 73 20 73 75 63 |g.algorithms suc|
00002910 68 20 61 73 20 74 68 65 20 4b 6e 69 67 68 74 73 |h as the Knights|
00002920 20 54 6f 75 72 2c 20 65 6e 61 62 6c 69 6e 67 20 | Tour, enabling |
00002930 74 68 6f 75 73 61 6e 64 73 20 6f 66 20 63 6f 6d |thousands of com|
00002940 62 69 6e 61 74 69 6f 6e 73 20 74 6f 0d 62 65 20 |binations to.be |
00002950 74 72 69 65 64 20 69 6e 20 74 68 65 20 67 65 6e |tried in the gen|
00002960 65 72 61 74 69 6f 6e 20 6f 66 20 61 20 73 6f 6c |eration of a sol|
00002970 75 74 69 6f 6e 20 74 6f 20 61 20 70 72 6f 62 6c |ution to a probl|
00002980 65 6d 2e 0d 20 0d 48 6f 77 65 76 65 72 2c 20 61 |em.. .However, a|
00002990 73 20 63 61 6e 20 62 65 20 73 65 65 6e 20 66 72 |s can be seen fr|
000029a0 6f 6d 20 74 68 65 20 4b 6e 69 67 68 74 73 20 54 |om the Knights T|
000029b0 6f 75 72 2c 20 74 68 65 20 74 69 6d 65 20 74 6f |our, the time to|
000029c0 20 70 72 6f 64 75 63 65 20 61 0d 73 6f 6c 75 74 | produce a.solut|
000029d0 69 6f 6e 20 6d 61 79 20 62 65 20 63 6f 6e 73 69 |ion may be consi|
000029e0 64 65 72 61 62 6c 65 2e 20 57 68 69 6c 65 20 61 |derable. While a|
000029f0 20 34 2a 33 20 62 6f 61 72 64 20 63 61 6e 20 62 | 4*3 board can b|
00002a00 65 20 73 6f 6c 76 65 64 20 76 65 72 79 0d 71 75 |e solved very.qu|
00002a10 69 63 6b 6c 79 2c 20 74 68 65 20 6e 75 6d 62 65 |ickly, the numbe|
00002a20 72 20 6f 66 20 63 6f 6d 62 69 6e 61 74 69 6f 6e |r of combination|
00002a30 73 20 69 6e 76 6f 6c 76 65 64 20 66 6f 72 20 61 |s involved for a|
00002a40 6e 20 38 2a 38 20 62 6f 61 72 64 20 61 72 65 0d |n 8*8 board are.|
00002a50 65 6e 6f 72 6d 6f 75 73 2c 20 61 6e 64 20 74 68 |enormous, and th|
00002a60 65 20 73 6f 6c 75 74 69 6f 6e 20 74 69 6d 65 20 |e solution time |
00002a70 69 73 20 76 65 72 79 20 6c 61 72 67 65 2e 20 54 |is very large. T|
00002a80 68 65 72 65 66 6f 72 65 2c 20 77 68 69 6c 65 0d |herefore, while.|
00002a90 62 61 63 6b 74 72 61 63 6b 69 6e 67 20 61 6c 67 |backtracking alg|
00002aa0 6f 72 69 74 68 6d 73 20 70 72 6f 76 69 64 65 20 |orithms provide |
00002ab0 61 6e 20 6f 72 64 65 72 65 64 20 61 6e 64 20 63 |an ordered and c|
00002ac0 6f 6e 73 69 73 74 65 6e 74 20 70 72 6f 62 6c 65 |onsistent proble|
00002ad0 6d 20 73 6f 6c 76 69 6e 67 0d 61 70 70 72 6f 61 |m solving.approa|
00002ae0 63 68 2c 20 73 6f 6c 75 74 69 6f 6e 20 74 69 6d |ch, solution tim|
00002af0 65 73 20 6d 75 73 74 20 62 65 20 63 6f 6e 73 69 |es must be consi|
00002b00 64 65 72 65 64 2e 20 49 6e 20 66 61 63 74 2c 20 |dered. In fact, |
00002b10 61 6c 67 6f 72 69 74 68 6d 73 20 6d 61 79 20 62 |algorithms may b|
00002b20 65 0d 63 6c 61 73 73 65 64 20 61 73 20 22 74 72 |e.classed as "tr|
00002b30 61 63 74 61 62 6c 65 22 20 28 73 6f 6c 75 74 69 |actable" (soluti|
00002b40 6f 6e 20 74 69 6d 65 20 69 73 20 70 6f 6c 79 6e |on time is polyn|
00002b50 6f 6d 69 61 6c 20 69 2e 65 2e 20 72 65 61 73 6f |omial i.e. reaso|
00002b60 6e 61 62 6c 65 29 20 6f 72 0d 22 69 6e 74 72 61 |nable) or."intra|
00002b70 63 74 61 62 6c 65 22 20 28 73 6f 6c 75 74 69 6f |ctable" (solutio|
00002b80 6e 20 74 69 6d 65 20 69 73 20 73 75 70 65 72 2d |n time is super-|
00002b90 70 6f 6c 79 6e 6f 6d 69 61 6c 20 69 2e 65 2e 20 |polynomial i.e. |
00002ba0 75 6e 72 65 61 73 6f 6e 61 62 6c 65 29 2e 20 46 |unreasonable). F|
00002bb0 6f 72 0d 66 75 72 74 68 65 72 20 64 65 74 61 69 |or.further detai|
00002bc0 6c 73 20 73 65 65 20 72 65 66 65 72 65 6e 63 65 |ls see reference|
00002bd0 20 31 2e 0d 20 0d 54 68 65 20 61 6c 67 6f 72 69 | 1.. .The algori|
00002be0 74 68 6d 20 64 65 73 69 67 6e 20 69 73 20 61 6c |thm design is al|
00002bf0 73 6f 20 69 6d 70 6f 72 74 61 6e 74 20 77 69 74 |so important wit|
00002c00 68 20 73 75 63 68 20 74 61 73 6b 73 2c 20 61 6e |h such tasks, an|
00002c10 64 20 65 76 65 72 79 20 65 66 66 6f 72 74 0d 73 |d every effort.s|
00002c20 68 6f 75 6c 64 20 62 65 20 6d 61 64 65 20 74 6f |hould be made to|
00002c30 20 72 65 64 75 63 65 20 74 68 65 20 70 72 6f 63 | reduce the proc|
00002c40 65 73 73 69 6e 67 20 69 6e 73 69 64 65 20 74 68 |essing inside th|
00002c50 65 20 72 65 63 75 72 73 69 76 65 20 70 72 6f 63 |e recursive proc|
00002c60 65 64 75 72 65 20 74 6f 0d 61 20 6d 69 6e 69 6d |edure to.a minim|
00002c70 75 6d 2e 20 57 69 74 68 20 74 68 65 20 53 6f 6c |um. With the Sol|
00002c80 69 74 61 69 72 65 20 70 72 6f 67 72 61 6d 2c 20 |itaire program, |
00002c90 61 20 73 6f 6c 75 74 69 6f 6e 20 77 61 73 20 67 |a solution was g|
00002ca0 65 6e 65 72 61 74 65 64 20 6f 6e 20 61 6e 0d 41 |enerated on an.A|
00002cb0 6d 73 74 72 61 64 20 31 35 31 32 20 72 75 6e 6e |mstrad 1512 runn|
00002cc0 69 6e 67 20 54 75 72 62 6f 20 50 61 73 63 61 6c |ing Turbo Pascal|
00002cd0 20 56 34 20 69 6e 20 38 34 20 68 72 73 2c 20 31 | V4 in 84 hrs, 1|
00002ce0 32 20 6d 69 6e 20 26 20 33 30 20 73 2c 20 77 68 |2 min & 30 s, wh|
00002cf0 69 63 68 20 69 73 6e 27 74 0d 65 78 61 63 74 6c |ich isn't.exactl|
00002d00 79 20 71 75 69 63 6b 2e 20 48 6f 77 65 76 65 72 |y quick. However|
00002d10 2c 20 74 68 65 20 6d 65 74 68 6f 64 20 6f 66 20 |, the method of |
00002d20 73 6f 6c 75 74 69 6f 6e 20 69 73 20 76 65 72 79 |solution is very|
00002d30 20 6e 61 69 76 65 2c 20 61 6e 64 20 77 69 74 68 | naive, and with|
00002d40 20 61 0d 6c 69 74 74 6c 65 20 77 6f 72 6b 20 74 | a.little work t|
00002d50 68 65 20 73 6f 6c 75 74 69 6f 6e 20 74 69 6d 65 |he solution time|
00002d60 20 63 6f 75 6c 64 20 62 65 20 72 65 64 75 63 65 | could be reduce|
00002d70 64 20 71 75 69 74 65 20 64 72 61 6d 61 74 69 63 |d quite dramatic|
00002d80 61 6c 6c 79 20 28 49 20 77 6f 75 6c 64 0d 62 65 |ally (I would.be|
00002d90 20 69 6e 74 65 72 65 73 74 65 64 20 74 6f 20 68 | interested to h|
00002da0 65 61 72 20 6f 66 20 61 6e 79 20 69 6d 70 72 6f |ear of any impro|
00002db0 76 65 6d 65 6e 74 73 20 69 6e 20 73 6f 6c 75 74 |vements in solut|
00002dc0 69 6f 6e 20 74 69 6d 65 29 2e 0d 20 0d 46 69 6e |ion time).. .Fin|
00002dd0 61 6c 6c 79 2c 20 68 65 72 65 20 69 73 20 74 68 |ally, here is th|
00002de0 65 20 73 6f 6c 75 74 69 6f 6e 20 74 68 61 74 20 |e solution that |
00002df0 74 68 65 20 63 6f 6d 70 75 74 65 72 20 67 65 6e |the computer gen|
00002e00 65 72 61 74 65 64 20 66 6f 72 20 73 6f 6c 69 74 |erated for solit|
00002e10 61 69 72 65 0d 28 31 2c 31 20 72 65 70 72 65 73 |aire.(1,1 repres|
00002e20 65 6e 74 73 20 74 68 65 20 74 6f 70 20 6c 65 66 |ents the top lef|
00002e30 74 20 6f 66 20 74 68 65 20 73 71 75 61 72 65 20 |t of the square |
00002e40 6d 61 74 72 69 78 20 75 73 65 64 20 74 6f 20 68 |matrix used to h|
00002e50 6f 6c 64 20 74 68 65 20 62 6f 61 72 64 29 3b 0d |old the board);.|
00002e60 20 0d 4a 75 6d 70 20 32 2c 34 20 6f 76 65 72 20 | .Jump 2,4 over |
00002e70 33 2c 34 2e 20 4a 75 6d 70 20 33 2c 32 20 6f 76 |3,4. Jump 3,2 ov|
00002e80 65 72 20 33 2c 33 2e 20 4a 75 6d 70 20 31 2c 33 |er 3,3. Jump 1,3|
00002e90 20 6f 76 65 72 20 32 2c 33 2e 0d 4a 75 6d 70 20 | over 2,3..Jump |
00002ea0 31 2c 35 20 6f 76 65 72 20 31 2c 34 2e 20 4a 75 |1,5 over 1,4. Ju|
00002eb0 6d 70 20 33 2c 34 20 6f 76 65 72 20 33 2c 33 2e |mp 3,4 over 3,3.|
00002ec0 20 4a 75 6d 70 20 33 2c 31 20 6f 76 65 72 20 33 | Jump 3,1 over 3|
00002ed0 2c 32 2e 0d 4a 75 6d 70 20 33 2c 35 20 6f 76 65 |,2..Jump 3,5 ove|
00002ee0 72 20 32 2c 35 2e 20 4a 75 6d 70 20 33 2c 37 20 |r 2,5. Jump 3,7 |
00002ef0 6f 76 65 72 20 33 2c 36 2e 20 4a 75 6d 70 20 34 |over 3,6. Jump 4|
00002f00 2c 33 20 6f 76 65 72 20 33 2c 33 2e 0d 4a 75 6d |,3 over 3,3..Jum|
00002f10 70 20 31 2c 33 20 6f 76 65 72 20 32 2c 33 2e 20 |p 1,3 over 2,3. |
00002f20 4a 75 6d 70 20 34 2c 31 20 6f 76 65 72 20 34 2c |Jump 4,1 over 4,|
00002f30 32 2e 20 4a 75 6d 70 20 34 2c 33 20 6f 76 65 72 |2. Jump 4,3 over|
00002f40 20 33 2c 33 2e 0d 4a 75 6d 70 20 34 2c 35 20 6f | 3,3..Jump 4,5 o|
00002f50 76 65 72 20 33 2c 35 2e 20 4a 75 6d 70 20 31 2c |ver 3,5. Jump 1,|
00002f60 35 20 6f 76 65 72 20 32 2c 35 2e 20 4a 75 6d 70 |5 over 2,5. Jump|
00002f70 20 34 2c 37 20 6f 76 65 72 20 34 2c 36 2e 0d 4a | 4,7 over 4,6..J|
00002f80 75 6d 70 20 34 2c 35 20 6f 76 65 72 20 33 2c 35 |ump 4,5 over 3,5|
00002f90 2e 20 4a 75 6d 70 20 36 2c 33 20 6f 76 65 72 20 |. Jump 6,3 over |
00002fa0 35 2c 33 2e 20 4a 75 6d 70 20 35 2c 31 20 6f 76 |5,3. Jump 5,1 ov|
00002fb0 65 72 20 35 2c 32 2e 0d 4a 75 6d 70 20 35 2c 33 |er 5,2..Jump 5,3|
00002fc0 20 6f 76 65 72 20 34 2c 33 2e 20 4a 75 6d 70 20 | over 4,3. Jump |
00002fd0 32 2c 33 20 6f 76 65 72 20 33 2c 33 2e 20 4a 75 |2,3 over 3,3. Ju|
00002fe0 6d 70 20 34 2c 33 20 6f 76 65 72 20 34 2c 34 2e |mp 4,3 over 4,4.|
00002ff0 0d 4a 75 6d 70 20 35 2c 35 20 6f 76 65 72 20 34 |.Jump 5,5 over 4|
00003000 2c 35 2e 20 4a 75 6d 70 20 32 2c 35 20 6f 76 65 |,5. Jump 2,5 ove|
00003010 72 20 33 2c 35 2e 20 4a 75 6d 70 20 35 2c 37 20 |r 3,5. Jump 5,7 |
00003020 6f 76 65 72 20 35 2c 36 2e 0d 4a 75 6d 70 20 35 |over 5,6..Jump 5|
00003030 2c 34 20 6f 76 65 72 20 35 2c 35 2e 20 4a 75 6d |,4 over 5,5. Jum|
00003040 70 20 37 2c 35 20 6f 76 65 72 20 36 2c 35 2e 20 |p 7,5 over 6,5. |
00003050 4a 75 6d 70 20 34 2c 35 20 6f 76 65 72 20 35 2c |Jump 4,5 over 5,|
00003060 35 2e 0d 4a 75 6d 70 20 37 2c 33 20 6f 76 65 72 |5..Jump 7,3 over|
00003070 20 37 2c 34 2e 20 4a 75 6d 70 20 37 2c 35 20 6f | 7,4. Jump 7,5 o|
00003080 76 65 72 20 36 2c 35 2e 20 4a 75 6d 70 20 35 2c |ver 6,5. Jump 5,|
00003090 36 20 6f 76 65 72 20 35 2c 35 2e 0d 4a 75 6d 70 |6 over 5,5..Jump|
000030a0 20 36 2c 34 20 6f 76 65 72 20 35 2c 34 2e 0d | 6,4 over 5,4..|
000030af 
14-07-89/TKnight.m0
14-07-89/TKnight.m1
14-07-89/TKnight.m2
14-07-89/TKnight.m4
14-07-89/TKnight.m5
.