In this assignment, you will write two short programs to solve problems using recursion.

Towers of Hanoi

Legend has it that in a temple in the Far East, priests are attempting to move a stack of disks from one peg to another. The initial stack had 64 disks threaded onto one peg and arranged from bottom to top by decreasing size. The priests are attempting to move the stack from this peg to a second peg under the constraints that exactly one disk is moved at a time, and at no time may a larger disk be placed above a smaller disk. A third peg is available for temporarily holding the disks. According to the legend, the world will end when the priests complete their task.

Consider three pegs numbered 1 through 3. Let us assume that the priests are attempting to move the 64 disks from peg 1 to peg 2, using peg 3 as a temporary holding peg. The problem is to design an algorithm that that will print the precise sequence of disk peg-to-peg transfers.

If you were to approach this problem with conventional methods, you would rapidly find yourself hopelessly knotted up in managing the disks. Instead, if you attack the problem with recursion in mind, it immediately becomes tractable. If we assume that we have a function that can move n - 1 disks from one peg to another using a third peg as a temporary holding peg, then we can easily formulate an algorithm to move n disks from peg 1 to peg 2 by using the function that moves n - 1 disks as follows:

1. Move n - 1 disks from peg 1 to peg 3, using peg 2 as a temporary holding peg.

2. Move the last disk (the largest) from peg 1 to peg 2.

3. Move the n - 1 disks from peg 3 to peg 2, using peg 1 as a temporary holding peg.

Write a recursive program that solves the Towers of Hanoi problem. Your solution must be recursive to be eligible for any credit.

2.1. Input

Your program must accept a single command line argument, a positive integer. This integer n will represents the number of disks to move. Number the disks from 1 (the smallest disk) to n (the largest disk). You should always start with all the disks on peg 1 with pegs 2 and 3 empty. Your program should then produce the sequence of disk peg-to-peg moves to move all the disks from peg 1 to peg 2.

2.2. Output

Your output should print one move per line. Each move must be in the following format,

1 2->3

which is interpreted as "move disk 1 from peg 2 to peg 3." Assuming that the name of your program is hanoi, below is an example of what an execution of your program should look like:

z123456@turing:~$ ./hanoi 2 1 1->3 2 1->2 1 3->2 z123456@turing:~$

The format of the output must be exactly has shown above. There is another program (described below) that we have written to check the output of your program. It expects exactly this format.

WARNING: The number of moves it takes to transfer the disks from peg 1 to 2 grows exponentially as you increase the number of disks, (for n disks the number of moves is 2^{n - 1}). If each move produces 7 bytes of output, redirecting the 20 disk output to a file will produce a 7MB file. Take care not to do that. It is safe to run your program with as many disks as you want as long as the output goes to the screen. But be careful not to redirect the stdout of your program for large disk counts, e.g., do not do the following,

z123456@turing:~/csci241/Assign2$ ./hanoi 20 > 20.out

If this does happen, don't panic. Simply remove the file using the command

rm 20.out

2.3. Files You Must Write

Write the code for this part of the assignment in a single file which must be called hanoi.cpp.

2.4. Files We Give You

If you use the setup command to get ready for this assignment, you will find an executable file called test_hanoi in your ~/csci241/Assign2 directory.

You can use test_hanoi to test the output of your program (rather then checking it by hand). test_hanoi reads the output (in the format described above) of hanoi and prints either "SUCCESS" or "failure". test_hanoi also takes a command line argument that must match the command line argument passed to hanoi that generated the output file.

You can run test_hanoi in one of two ways.

z123456@turing:~/csci241/Assign2$ ./hanoi 5 > 5.out z123456@turing:~/csci241/Assign2$ ./test_hanoi 5 < 5.out SUCCESS z123456@turing:~/csci241/Assign2$ 

In this method you are storing the output from hanoi in a file called 5.out and then passing that file to test_hanoi. This should only be used for smaller runs, say problems with 10 or fewer disks. You might want to run hanoi this way while debugging; in case test_hanoi reports "failure", you can hand-inspect 5.out to find the error.

z123456@turing:~/csci241/Assign2$ ./hanoi 5 | ./test_hanoi 5 SUCCESS z123456@turing:~/csci241/Assign2$ 

In this method you do not create an output file. The output of hanoi is "piped" directly as input to test_hanoi. Running large problems (many disks) with this method does not create large files but may take very long to execute. You're probably safe with disk counts < 20.

2.5. Hints

Consider writing a recursive function

void move(int n_disks, int src_peg, int dest_peg, int temp_peg)

3. Eight Queens

Write a program that places eight queens on a chessboard (8 x 8 board) such that no queen is "attacking" another. Queens in chess can move vertically, horizontally, or diagonally.

How you solve this problem is entirely up to you. You may choose to write a recursive program or an iterative (i.e., non-recursive) program. You will not be penalized/rewarded for choosing one method or another. Do what is easiest for you.

3.1. Output

Below is one solution to the eight queens problem, there may be others. Your program only needs to find one solution, any solution, and print it. Assuming the name of your program is queens, executing your program should look like this:

z123456@turing:~/csci241/Assign2$ ./queens 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 z123456@turing:~/csci241/Assign2$ 

where a '1'; means a queen is on that square of the board and a '0' means the square is empty.

Note that it is very important that your output be formatted exactly as shown above. In grading your program, its output will be checked by another program (we wrote) that expects as input a solution in this format.

3.2. Files You Must Write

Write the code for this part of the assignment in a single file which must be called queens.cpp.

3.3. Files We Give You

If you use the setup command to get ready for this assignment, you will find an executable file called test_queens in your ~/csci241/Assign2 directory.

You can use test_queens to test the output of your program (rather then checking it by hand). test_queens reads the output (in the format described above) of queens and prints either "SUCCESS" or "failure".

You can run test_queens in one of two ways.

z123456@turing:~/csci241/Assign2$ ./queens > queens.out z123456@turing:~/csci241/Assign2$ ./test_queens < queens.out SUCCESS z123456@turing:~/csci241/Assign2$ 

In this method you are storing the output from queens in a file called queens.out and then passing that file to test_queens. You might want to run queens this way while debugging; in case test_queens reports "failure", you can hand-inspect queens.out to find the error.

z123456@turing:~/csci241/Assign2$ ./queens | ./test_queens SUCCESS z123456@turing:~/csci241/Assign2$ 

In this method you do not create an output file. The output of queens is "piped" directly as input to test_queens.