Part I
General guidelines for all assignments: (1) complete using a script file unless otherwise noted; (2) submit all your work [e.g. script, command window, function files, figures]
The Tower of Hanoi
1. In this assignment you will write a program to play a famous game that is also a classic computer science problem,
The Tower of Hanoi. For this assignment, you are NOT being asked to write an AI program to solve the puzzle – only to write a program to allow a HUMAN player to play the game.
A. Creating a struct to represent the game
The Tower of Hanoi consists of 3 pegs, each containing a stack of different-sized rings. At the start of the game, the rings are all on the left peg; the objective of the game is to move them all to the right peg, according to rules that will be discussed later.
In our MATLAB implementation, the configuration of the game will be described by a combination of structs and cell arrays. The overall organization of the data is as follows:
· The game board is represented by a struct, which contains 3 fields: Peg1, Peg2, and Peg3.
· Each of these fields is a
cell array, containing the rings on that peg.
· Each ring is a struct, containing the following fields: Size, Color.
· The Size is a dimensionless number. 1 is the smallest disk; in a 5-ring game, 5 is the largest disk.
· The Color is a single character, as in a plot control string:
b blue
g green
r red
c cyan
m magenta
y yellow
k black
w white
To clarify the relationship between the data structure and the game configuration, suppose that the current state of the game is as shown here:
The struct to represent this configuration could be created in steps as follows[1]:
%First initialize an empty struct
tower = struct(‘Peg1’, {}, ‘Peg2’, {}, ‘Peg3’, {});
%Set the values of each field[2]
tower(1).Peg1{1} = struct(‘Size’, 4, ‘Color’, ‘r’);
tower.Peg2{1} = struct(‘Size’, 3, ‘Color’, ‘g’);
tower.Peg2{2} = struct(‘Size’, 1, ‘Color’, ‘y’);
tower.Peg3{1} = struct(‘Size’, 2, ‘Color’, ‘b’);
Notice that the bottom ring is at index {1}; this makes it easier to add or remove a ring to/from the top of the stack.
WARNING: When you are initializing the tower, Peg2 and Peg3 will be empty. If you use the step-by-step approach shown above, even though it may seem redundant,
you must include these lines:
tower.Peg2 = {};
tower.Peg3 = {};
B. Writing a move() function
Write a function to move a ring from one peg to another, according to the rules of the game:
· Only one ring can be moved at a time
· Only the top ring on a peg can be moved
· A ring can only be placed on top of a larger ring. So in the figure above, a valid move would be to move the blue ring onto the red ring. Moving the red ring onto the blue ring would be an illegal move.
Inputs
to the function are:
· the struct describing the state of the game before the move, as described in part A
· The peg number (1=left, 2=middle, or 3=right) from which the ring is being moved
· The peg number (1, 2, or 3) to which the ring is being moved
The
output
of the function is the struct describing the state of the game after the move.
The function must check whether the move is legal. If it is illegal, it should produce an error message and leave the struct unchanged. For full credit, the message must be displayed using a
message box or error dialog, not the command line.
Programming hint: You can use
waitfor() to force the user to click the OK button on the message box before the program continues. For example:
M = msgbox(‘That move is illegal!’);
waitfor(M);
IMPORTANT: Removing an element from a cell array. To remove the top element from a stack, you must delete the entire cell, not just remove the contents of the cell. That is, you should do this:
tower.Peg1(end) = []; %Deletes the last cell in the array
NOT THIS:
tower.Peg1{end} = []; %Deletes the contents of the cell
Programming hint: Because the FROM & TO columns are given as numbers, but the columns are specified by field names, the logic can get very cumbersome. It can be done with
if or
switch structures, but there is a trick that may be useful in making the code more compact. The field name for a
struct can be specified using a character array like this:
>> field_name = ['Peg', num2str(from_col)];
>> tower.(field_name)
ans =
1×1 cell array
{1×1 struct}
This can also be combined with cell indexing like this:
>> tower.(field_name){1}
ans =
struct with fields:
Size: 4
Color: 'g'
C. Writing a simplified test script
In Application 8 – Part 2, you will write a full GUI program to play the game. In Part 1, you will write a simple test script to demonstrate that the function works.
The test script should operate as follows:
· Initialize the struct with all rings in order on Peg1, largest on the bottom, smallest on the top. You can use whatever colors you like, but each ring must be a different color.
NOTE: For Part 1, the number of rings can be fixed. In part 2, it must be adjustable by the user.
Important: since initially there are no rings on the second and third pegs, those 2 pegs must be initialized to empty cell arrays as follows:
tower.Peg2 = {};
tower.Peg3 = {};
· Display the tower configuration using the provided function, display_tower()
· Pause for one second using pause (1.0)
· Call the move() function to move the top ring from Peg 1 to Peg 2, and re-display the tower
· Pause for one second
· Call the move() function to move from Peg 1 to Peg 3, and re-display the tower
· Pause for one second
· Call the move() function to move a ring from Peg 3 to Peg 2, which should be an illegal move
Submission Requirements
Submission location: Carmen
Required Files:
1. Test script and user-defined move function with comments (.m)
Note – The user-defined function can be external or local.
[1] There are more compact ways of doing this; we are doing it step-by-step to make it easier to follow
[2] The index (1) after tower is necessary, because the previously created struct was empty (had dimensions of 0x0). If the initialization step is left out, this index is not necessary.