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

1. Initial Setup

1. Log in to Unix.

2. Run the setup script for Assignment 2 by typing:

    setup 2 

The setup script will create the directory Assign2 under your csci241 directory. It will copy a makefile named makefile to the assignment directory and will also create symbolic links to a pair of test programs that you can use to verify that your output is correct.

Using the makefile we give you, you can build one specific program or build both programs. To build a single specific program, run the command make followed by the target name for the program that you want to build (hanoi or queens). For example:

z123456@turing:~$ make hanoi

To build both programs, run the command make all or just make.

Running the command make clean will remove all of the object and executable files created by the make command.

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.