CS 11 C track: Assignment 4

The Triangle Game is a solitaire (one player) board game played on a triangular board with fifteen equally-spaced holes in it. The diagram below shows how the holes are arranged and numbered.

Initially, fourteen of the holes have pegs in them, while hole 4 starts out empty. We denote holes with pegs in them by drawing a box around the number.

A peg can move by jumping over an adjacent peg which is then removed, just like in checkers. However, unlike in checkers, it is okay to jump horizontally as well as diagonally (vertical jumps are not allowed). Also unlike checkers, you can’t just move pegs around; the only way to move a peg is to jump over an adjacent peg into an empty space.

For instance, starting from the initial board configuration, we could take peg 11, jump it over peg 7, and land in space 4. Peg 7 is removed, leaving us with the board configuration shown here:

We could continue by taking peg 9, jumping over peg 8, and landing in space 7. Notice that there is one fewer peg after every move, which means that the longest possible game has thirteen moves, removing thirteen pegs, which leaves only one peg remaining.

The object of the game is to make the game last as long as possible (thirteen moves). It might also be nice if you could get the final peg to end up in position 4, thereby preserving a sense of harmony, but as it turns out, that isn’t possible. (In fact, the final peg will always be in position 12.)

It’s convenient to use the term "board" to refer to a particular arrangement of pegs — for instance, we would say that the two diagrams above show two different boards. A move is said to be legal for a particular board if it complies with the rules described above. For instance, the move "jump 9 over 8 landing on 7" is a legal move for the second board shown above, but it is not a legal move for the initial board. The set of possible moves is just the set of all moves which are legal in at least one conceivable arrangement of pegs. So "jump 9 over 8 landing on 7" is a possible move. However, "jump 9 over 8 landing on 14" is not a possible move, because it is never legal.

Your program should do the following:

In order to make this easier, and to allow you to concentrate on the problem at hand, we are supplying you with the input/output functions for the program. These functions are:

To use these handy functions (and you really should use them), save the following files to the same place as your program will go:

You’re not required to understand how they work, but by all means look through them if you’re curious.

triangle_example.c is a short example of the use of these functions. Save it into the same directory as triangle_routines.c, and compile and run it like this:

When you run it will simply ask you for a board and print out the board you entered.

A couple of things to notice in the example:

We strongly encourage you to use this example as a starting point for your program.

Your board-solving function should take one argument: an array representing a board. It should return 1 (true) if the board can be solved, and 0 (false) if the board cannot be solved. Other than that, it should not change the board. It’s OK if it changes the board temporarily, as long as it changes it back to its original state before returning.

To check if the board is solvable, it’s easiest if you use a recursive algorithm. One way to use recursion to solve a board would be to proceed as follows:

In order to know what moves are allowed, you need to come up with a representation of the move. One way is to represent a move as an ordered triple of numbers. For instance, in the initial position we can take a peg at position 11, jump over position 7 and land in position 4. This can be represented as the triple: 11, 7, 4. Similarly, we can enumerate all possible moves (there are 36 of them), and stuff them into a global array:

This uses C’s array initialization syntax (see lecture 3, or Darnell and Margolis sections 7.3 and 7.11, or K&R sections 4.9 and 5.7). Then you can iterate through the array, looking for moves which are legal given the current board position. When you find one, make the move and recursively call the function on the resulting board. If the move does not lead to a solution, un-make it and continue. Once there is only a single peg on the board, you have found a solution.

If there’s a solution, you’re required to also print out the solution in reverse order (i.e. starting with a board with only one peg and growing by one peg each time until the starting board is printed). This seems really hard but in fact is really easy. All you need to do is (in the board-solving function) to print out the board before any place where you return 1 (a true value i.e. success). Because of the way the recursive function works, this will end up printing out the successful solution in reverse order. Normally, it’s bad design to print out something in a function whose main job is to do something else (like solve a board in this case); however, here we’re mainly using the board printing as a debugging aid, so it’s OK.

Here are the function prototypes we used for our solution, along with comments stating what they do:

Note that the move[] arguments in the above function prototypes don’t refer to the entire 2-dimensional moves array, but to a single move i.e. a one-dimensional array of 3 integers.

The solve function is a bit tricky (it’s the recursive one); the rest are quite straightforward. When we say "do not permanently alter the board passed in" what we mean is that the function can change the board, but it should undo the change before it exits. When you think about it, this makes sense; all the function really has to do is to figure out whether the board is solvable or not (which doesn’t require the board to be altered when it exits) and to print out the solution if it finds one (ditto). The unmake_move() function will be useful to ensure that the board doesn’t get permanently altered before the solve function exits.

As we mentioned above, the fact that the solve function prints the solution after it finds it is unusual, and would normally be considered bad design. Normally we would store the solution somewhere, and print it in another function. That can be done, but it’s quite a bit harder. To make this easier, you just have to print the solution immediately, and you don’t have to store any old boards anywhere. That’s also the reason for the reverse order; it makes it possible to print the boards without having to store them. To be absolutely clear, by "reverse order" we mean that the solved board (with one peg) is the first thing you print, followed by the previous board (with only two pegs), and so on up to the full board, with e.g. 14 filled pegs and one empty peg. Of course, use the triangle_print() function to print the board. Make sure you print the original board!

We recommend that you concentrate on solving the board first, and only after that worry about printing the boards in the solution. It won’t require much extra code.

You should also realize that it’s OK to use one-dimensional array components of a two-dimensional array. So the first move in the array is moves[0], which in the above example stands for the array {0, 1, 3}. A lot of students copy the move to a new array, but that isn’t necessary.

Don’t use any global variables for this program except for the two-dimensional array of moves! It’s OK for the moves array to be a global variable because it’s really a global constant; you never change it. Global variables that get changed are occasionally useful too, but more often they just make your program much harder to debug, so normal practice is to avoid using them if possible. None of the assignments in the C track require global variables other than this one, and this one’s only global variable is the moves array.

Don’t use magic numbers! Don’t put numbers like 36 or 15 in your code; use #define to create symbolic names for them and use the symbolic name instead. That’s good programming style.