Whether your instructional language is C++, Java, Ada, or Visual Basic, the computer science introductory curriculum is moving steadily towards objects and libraries of reusable code. Unfortunately, the curriculum never really reaches this goal in the sense that there are too few instances where students learn how to build reusable modules themselves. As students move through the undergraduate curriculum they learn how to access standard modules and to incorporate these modules into custom applications. When they don't know if an appropriate module exists, they write their own code, and this code is written with no expectation that it will be reused. The seniors that I see in Software Engineering Practicum understand that it is more economical to buy than to build, and they are willing to expend great effort to learn how to make use of packaged code. But they seem to think that, like operating systems and compilers, packaged code comes from specialists who market it to applications programmers. This paper recounts an exercise I developed with sophomores in an effort to teach them about code reuse. Beyond the example presented its suggests that the second language course is one of the logical places in the curriculum to emphasize building for reuse.

When teaching Java as a second language, I was looking for exercises that would be more complex than the narrow tasks the students had accomplished in CS1 and CS2. They were learning a new syntax but I felt that they should also be maturing in their ability to cope with complexity. Since we were going over arrays, linked lists, and recursion a second time, I wanted a simple but challenging application which would use these concepts but also illustrate the power of design for reuse. Unfortunately, I was using an introductory textbook to teach the second language and its exercises naturally focused on drilling the use of unfamiliar syntax. One of my students happen to give me a board game that is like many puzzles in that it has an initial position and a final position and the challenge is to move the pieces around to transform the board from initial to final state. In this case over one hundred moves were needed and there was no obvious strategy as to their sequence. After an hour of random exploration with the puzzle I decided to write a Java program to find the solution by exhaustive search.

I wrote several versions of my program, iteratively improving my class design and the opportunity to generalize the solution strategy. The PlayGame module did a depth-first recursive search of the state space, starting with the initial state and selecting any valid move to transition to another state. Each new state was tested for either the winning state or a repeated state and otherwise it was used to generate the next state. The program recursively descended through the state space until it happened onto a winning state. From there it regressed to the initial state, building a link list which captured the sequence of states from initial to final. The next phase of the PlayGame module refined this list by cutting out the ox-bow loops: a sequential search was made forward from each state to see if there was a subsequent state in the solution that was immediately reachable from this state, allowing all the intervening wanderings to be discarded. Finally the refined list was displayed as a list of move steps: starting in the initial state, move piece on square m to square n,..., until the final state is reached.

The PlayGame module utilized a hash-table array with a linked list for the collisions so the linked list class that came out of the textbook was employed twice in the program. The PlayGame module manipulated GameStates, generating them, sequencing them, and displaying them. The GameState class interacted with the GameBoard class and the Pieces class. The GameBoard class encapsulated an array that represented the positioning of pieces on the board in any state. The Pieces class was abstract and its final subclasses were the different pieces, each of which encapsulated its position and its possible moves (each piece had a different rule for making valid moves). Two GameState instances were different if their boards were different and neighbors if moving one piece on the first board would transform that board into the second board. The GameState class had methods for creating neighbor states and for testing the neighbor relation.

The solution of the puzzle with a small set of effectively orthogonal classes was satisfying and educational, but it was just the beginning. Typically Computer Science instructors do not dwell too long on one exercise and consider the coordination of several classes to achieve the goal of solving a puzzle more than an adequate accomplishment in an intermediate programming assignment. I had used recursion and a packaged class from the textbook to solve the puzzle, but since I never doubted that this was possible, whatever the elegance of the solution, I considered it a sterile achievement. I thought my students were mature enough to get more out of the exercise than just a solution.

I then examined the "blind" search strategy to see if small manipulations of the code could result in an alternate and perhaps better solution. In this puzzle there were four "yellow" pieces which were easily moved, and one "red" piece that was difficult to move (there were also five "blue" pieces). If the program went through the piece list from start to end (ten pieces) and always tried to move "yellow" pieces first, it made lots of extraneous moves. If it always tried to move the "red" piece first, it missed good moves. The point was that the blind search of the state space was seriously impacted by the inflexible strategy of how to choose a piece to generate a new state. I then introduced a systematic rotation of starting points based on the sequence number of the last state generated. I also showed how to arbitrarily cut off the depth of the recursion and force the program to retreat back across the search tree. Such considerations were motivated by the fact that the recursive program at first "spaced out"--it exhausted the heap before finding a solution. The realization that thousand of states were being generated and stored led to the examination of how to minimize state information and that led to the storage of the move history in the piece instead of in the GameState instances. This change also made it feasible to continue the recursive search for additional solutions after the first since the position history was not lost in the refining process (and all processed states remained stored in the hash table).

When the design was revealed to support all these improvements the class was impressed, but I was still not done. I then returned to the real reason I had sought a general solution to the puzzle, couched in terms of states, boards and pieces-- I wanted to solve a different puzzle with the same code! To show the power of reuse, I solved the eight queens puzzle. The dimension of the board changed from 4x5 to 8x8. I now had eight identical pieces instead of ten varied pieces. The initial state was all the queens on one row. The ending state was to reposition seven of the queens on its file so that it didn't "cast a shadow" on any other queen. None of the method signatures (shown in the appendix) were changed and no code in the PlayGame module was change. I had to change the code inside of the boolean-valued win method since the final position was not static but one of nearly two dozen configurations (none explicitly known). I had to write new code for the final class Queen, and I had to change the methods that reported on the contents of the squares of the board so that a Queen could calculate what squares were potential moves (most squares were actually empty but I recorded the number of "shadows" on each). Obviously the names of the squares changed within the methods that displayed the board but the names were literals that were stored in a string array. In the first puzzle each board was hashed based on the square numbers of the two vacant squares (which had to be found), and in the Eight Queens solution the hash was based on the highest and lowest numbered squares occupied by queens. Finally, the creation of a new state involving the moving of a queen from a previous state (creating a neighbor) was accomplished a little differently (there were more side-effects to moving a queen than there had been when a move simply filled a vacant square and created a new empty one). Over half of the code used to solve the Eight Queens puzzle, however, was carried over untouched from the solution of the previous puzzle!

As I thought about the positive insights that the discussion of this exercise seemed to bring to my class I wondered why I had not thought to make this an emphasis before. I reflected that one reason is that few texts are written specifically for the second language course, so we use introductory texts that focus on developing algorithmic understanding instead of software engineering principles. A second impediment is that the second language course typically proceeds much faster than the first, often covering in one semester the language features that were introduced over the course of a year for the first language. Instructors tend to use the duplication of syntactical forms as a review both to gain a deeper understanding of compilation and a better grasp of language design. I often challenged my second language students with more intricate exercises, but did not think much about introducing new software design considerations. On this occasion the class was offered in the summer so I had barely enough time to let the students complete the exercises from the text without contemplating a separate term project.

As the instructor, however, I had no difficulty tackling the project on my own, and since I needed to illustrate the language's features in class anyway, this application proved to be an attention-getter. Now that I'm enlightened I have looked again at my objectives for the second language course. The curriculum at LSU-Shreveport does not focus much attention on class design in the freshman year, so the sophomore-level second language course in Java becomes a natural place to introduce software engineering ideas such as designing for reuse. Fortunately, I have discovered that many introductory Java texts choose to focus on Java's support for software engineering and the object paradigm. Knowing what I wanted in my text enabled me to select a different text for the next regular semester offering of this course [1]. I still have to deal with the fact that first-year students have focused on the procedural programming paradigm so that I have to develop experience with classes slowly. A term project of the complexity of the game program may still be too much of a challenge to assign them on their own. However, I plan to use my game program again as lecture material to demonstrate the practical consequence of heeding the textbook's message.

The training of programmers will be more effective if they are challenged to solve a series of increasingly complex problems. We are rather successful data structures, operating systems, compilers, and artificial intelligence courses in providing an introduction to many techniques and strategies, and in our programming language courses we teach how to access a variety of library objects. I fear we are not so good at connecting these abstract and concrete components so that somewhere before the software engineering project course the student begins to appreciate how to generate solutions that are well designed and reusable. More attention to patterns will help. But opportunity must be seized in situations such as the second language course to make "design and write to reuse" part of the programmer's psyche.

Most of the undergraduate student's programming exercises fail to provide any incentive for developing reusable code since they are generally focused, independent assignments. Consequently students are being taught more about objects without learning to appreciate their practical value. This paper has demonstrated that with just a little more effort we can find ways to help students reuse objects that they have created for one context in a slightly different context and thereby impress upon them the benefits of designing abstractly and implementing with hiding.

1. Culwin, Fintan, Java: An Object First Approach, Prentice Hall, 1997.

The puzzle's initial and winning positions. The Red piece is 2x2, the Blue pieces are 2x1 or 1x2 (Vertical Blue), and the Yellow pieces are 1x1.

Signatures for both programs (internals of some methods changed as noted in discussion). The longest method comprises 25 lines and the average is about 10 lines.

Class Play Game

Static methods: boolean before(GameState) //determine if previously generated

DisplayState(GameState)

Main()

RefineSol() //process linked list of GameStates

boolean test(GameState,int) //recursive search, if not win, call tryOthers

boolean tryOthers(GameState, int) //generate neighbor and test

Abstract Class Pieces

Abstract methods (only methods implemented by final classes)

int doMove(int, int, GameBoard)

GameBoard makeMove(int, GameBoard)

Misc methods to access piece memory and recover positions at previous states (stack operations inherited by pieces)

int getOldPos(int)

int getPosition()

int get Position(int)

SetOldPos(int)

Class GameState

displayGameBoard()

boolean equals(GameState)

int getState(GameState) //access state number

boolean IsNeighbor(Gamestate)

GameState nextNeighbor()

int tag() //hash function on a GameState to store it or checking if previously generated

String transitionTo(GameState) //display move in a list (piece at .. moved to ..)

boolean win() //test for winning state

Also three constructors for making new GameStates, one of which is the initial state.

Class GameBoard

String displayBoard(GameBoard) <static>

String getSpotName(int) <static>

boolean equal(GameBoard)

int getBIndex(int, char) //locations on board identified as a direction from a given square

int getLoc(int, char, int) //content code on a distant square

int getType(int) //content code on a given square

int maxv() //added to Queens program to help identify winning position

register(int, Pieces )

register( Pieces )

setLoc(int, char, int, int)

Class LinkListRecord <identical for both programs>

Final classes extending Pieces in the two versions of the program are BluePiece, VerticalBluePiece, RedPiece, YellowPiece, and Queen, respectively, each implementing the abstract methods of Pieces.