Linked lists are alive and well in computer graphics. Mark Coleman.
Linked Lists Are Alive And Well In Computer Graphics
What in the world is a linked list? Linked List is a fancy buzz phrase that means each position in the list contains, among other things, a map showing how to get to the next position in the list, much like a treasure hunt.
Lists that are not linked are called sequential lists. In a sequential list, the next element in the list must be in the next storage location. However in a linked list the next element value may be stored anywhere, since each element has a pointer to the location of the next element. Figure 1 shows the list (A, B, D, E, F) in both forms.
There are many advantages and disadvantages to linked lists. One disadvantage is that they take up more memory since links must be stored along with element values. One advantage is the ease of inserting or deleting elements. Say we want to insert C between B and D.
Figure 2 shows that in the sequential list all elements after B must move one storage location in the list to make room for C. This can take a great deal of time if the list is very long. But in a linked list all that need be done is change the value of the link at B so it points at the storage position of C and make the link of C point to D.
In a doubly linked list, each element has two links, one pointing to the next element and one pointing to the previous element as shown in Figure 3.
In the example above, the links are actually the values of the next storage location. In general, links are any pieces of information which point to the location of the next value. This article shows how linked lists can be useful in solving a game known as Magic Path.
The Game
The game goes like this. Given the 5X5 matrix in Figure 4, draw a line which starts at START and ends at END. The line may not cross the same square twice, it may not go diagonally or out of the matrix, and the sum of the numbers crossed by the line must be 1958. Sounds easy.
I spent a few minutes trying to figure out a short cut solution, but soon decided that a systematic trial and error approach would be faster. All I had to do was try each possible path. Figuring out how to do this systematically is where the fun comes in.
The Algorithm
Since the matrix is a two-dimensional array, I decided to store the data in the same form. For a given square, the first subscript of the array corresponds to the column and the second subscript corresponds to the row as shown in Figure 5.
But how do I decide which direction to go from any given square? There are only four directions that are legal so I numbered them 1 to 4 as in Figure 6.
When I first enter a square I will try to exit from it in direction 1. If for some reason I cannot exit in the desired direction--if I run into an edge or the new total will exceed 1958--then I simply increment my direction pointer and try the next direction. If that direction doesn't work, I increment it again and again until I find a direction I can go or until I exhaust all four possible directions. For example, in Figure 7, directions 1 and 2 from square H go off the matrix, so direction 3 is chosen making I the next square.
To generate the Row (x), Column (y) coordinates of the next square, I wrote a "direction decoder' routine which relates the direction number 1 to 4 to the required change in subscripts.
IF D=1 THEN Y=Y+1
IF D=2 THEN X=X+1
IF D=3 THEN X=X-1
IF D=4 THEN Y=Y-1
But what if I exhaust all possible directions from a given square, the classic "You can't get there from here' problem? I must then go back to the previous square on the path and try the next direction from that square. For example trying to select the next square from square "216' in Figure 8 results in: direction 1 crosses a square twice; direction 2 crosses a square twice; direction 3 crosses a square twice; direction 4 causes sum to be greater than 1958.
In this case square 216 must be eliminated from the path and the next direction must be selected from square 7.
Now I realized I had a problem. I needed two pieces of information that I didn't have yet. First of all, square 216 needs to know how to find square 7 and then square 7 needs to know which direction it tried last so it knows which direction to try next, or in other words it needs to know how it got to suare 216. I needed "links' forward and backward in the list of squares on the path.
I decided to expand my two-dimensional array, which was storing the values of the squares, into a three-dimensional array as in Fugure 9.
The values for the links are the numbers 1 through 4 corresponding to the directions shown in Figure 6. In addition, when a square is not yet on the path, I set the links to zero. This makes it easy to tell whether or not a given square is available or has already been used. Remember that you can't cross a square twice.
To illustrate this scheme consider the path shown in Figure 10.
The zeros arise from the fact that square (2, 1) is the start square so it has no previous square and square (3, 1) is the last square shown so it has no next square.
Once I figured out the linking scheme all I had to do was check for a total of 1958 and current coordinates equal to the END square.
Graphics
To keep myself from feeling completely neglected as my computer solved this problem, I added a few lines to the program to draw the matrix on my screen and to draw and erase the different paths as they were tried. Having the different paths drawn on my CRT not only made the program more fun to watch, but it also made debugging much easier since I already had a mental picture of how the search should proceed.
The machine I used was a Hewlett-Packard 9845B which has really super graphics, but you don't need anything too super to perform most of the operations I discuss below.
By scaling my graphics area (.5, 5.5, .5, 5.5) and drawing the matrix with corners at (.5, .5), (.5, 5.5), (5.5, 5.5), and (5.5, .5), the centers of the squares occur at integer coordinates corresponding to the subscripts of my A array. (Figure 11).
Initially I do a MOVE to the center of the START square. Then, after I decide which square to move to next, I do a DRAW to the new coordinates. If I arrive at a dead end and have to back up, I erase lines by doing a PEN -1 and a DRAW to the coordinates of the previous square. On my HP 9845B, PEN-1 means erase.
If your machine doesn't have a SCALE statement just MOVE and DRAW to 3*X, 3*Y or 5*X, 5*Y or whatever scale factor is necessary to get a reasonable size matrix and pathway.
Also if you don't have MOVE, DRAW commands you will want to write a little subroutine which lets you draw horizontal and vertical lines. The program in Listing 1, or some modification of it, ought to work on your machine. As shown it will run on a TRS-80 or the like. It only draws vertical and horizontal lines, but that's all you need for this application.
To do a MOVE, simply set XS equal to the x-coordinate of the starting point and YS equal to the y-coordinate.
To do a DRAW set XE equal to the x-coordinate of the end point and YE equal to the y-coordinate. Then do a GOSUB 1000.
The routine draws a line from XE, YE to XS, YS. Then it sets XS=XE and YS=YE so you can draw a line starting at the end of the last line without redefining the startpoint.
P determines whether the line is to be drawn or erased (-1 means erase, any other value means draw).
Faster Solutions
After I got the program running, I noticed that the search spent a great deal of time on paths that I knew wouldn't work. For example, once a square in column 1 or 5 is entered (sides) there is no way to get to the END square by going down (direction 4). Also when Row 1 or 5 is entered (top and bottom) and I'm in columns 3, 4 or 5, there is no way to get to the END square by going right (direction 2). Also the END square should be treated as a dead end.
I was able to avoid searching these paths by modifying a few lines of code in the routine which checks to see if the proposed direction is legal. By eliminating these paths I was able to speed up the search considerably.
Conclusion
Figure 12 and Listing 2 show my flowchart and program. If you rewrite it for your own machine be careful to undo all your steps completely as you travel backward from a dead end. It is very easy to forget something. It took me a while to figure out that I was forgetting to subtract the values of the squares as I left them.
There are several solutions which result in a total of 1958, but only four which also terminate in the END square. I have shown one of the correct paths in Figure 13. Of course, there is nothing magic about 1958 or the values in the squares. Try different values and make your own puzzles. Try a three-dimensional matrix or different searching schemes.
Singly and doubly linked lists, aside from being buzz words, can be very useful in solving many types of problems, like this one, that involve searching large amounts of data.
Table: Figure 1.
Table: Figure 2.
Table: Figure 3.
Table: Figure 4.
Table: Figure 5.
Table: Figure 6.
Table: Figure 7.
Table: Figure 8.
Table: Figure 9.
Table: Figure 10.
Table: Figure 11.
Table: Figure 12.
Table: Listing 1.
Table: Listing 2.
Table: Figure 13.