CS 3733 Operating Systems, Spring 2011 Assignment 4

Assignment 4: Due Thursday, March 31

In the last 2 assignments we will look at solving standard problem in three ways. In this assignment we will develop a serial solution to the problem and then extend it to use POSIX threads. In Assignment 5 we will use a network of workstations to solve this problem.

This assignment has several parts and will be graded on a bases of 50 points. The first 4 parts of this assignment will form the basis of Assignment 5, so it is important that you get these parts working correctly.

Learn about the 8-queens problem. One possible source is here. You only need to understand the problem, so the first paragraph is sufficient.

The n-queens problem reduces to finding n unique integers between 1 and n (a permutation) such that no two numbers in the list differ by the distance between them in the list (the diagonal property). The first number is the list in the row number of the queen in the first column, the second is the row number of the queen in the second column, etc. The first property ensures that no queen can take another moving horizontally or vertically. The second ensures that no queen can take another moving diagonally. Make sure you understand these statements.

One inefficient brute-force method of solving this problem is to try all possibilities and check to see if each is a solution. To be a solution, the numbers must be a permutation and satisfy the diagonal property.

We will be a little more clever and generate only permutations and check each to see if it satisfies the diagonal property.

When using a brute force method, it is useful to have a lot a computing power at your disposal. Therefore we will eventually try to do this computation in parallel. Since array indices start at 0, it is simpler to use numbers between 0 and n-1 instead of 1 to n. We can break the problem into 2 parts:

Part 0
Make a new directory for this assignment. Create a main program that takes a single command line parameter, the value of n. Start by printing your name. Call the function:
int generate_n_queens_serial(int n, int print_flag)
This generates all solutions to the n-queens problem and returns the number of solutions found. If the print_flag is true, it prints the solutions to standard output, one per line.

Put the function in a file called nqueens_library.c and create an appropriate include file. Use make to compile the code.

For this part, have the generate_n_queens_serial function just return 0.

Test your program.

Part 1
In this part we will write half of generate_n_queens_serial.
All of the functions should be in the nqueens_library.

Write the function
void get_array_string(int *list, int n, char *s); that fills the last parameter with a string containing the n integers in list. Each integer should be right justified in a field of size 4, using blanks as separators. Include a newline at the end and assume that s is large enough to hold the result.
Hint: use sprintf in a loop with the appropriate output specification.
Clarification added 3/30/2011: The returned string should represent a single line with a newline at the end of the string, not a newline for each integer.

Test this by having generate_n_queens_serial generate the permutation: 0 1 2 3 ... n-1, call get_array_string and print the result if the flag is appropriate.

Find an efficient way to generate all permutations of the integers for 0 to n-1. For example, you can find an algorithm here under the topic Systematic generation of all permutations.

Use this to write a function:
int next_permutation(int *list, int n)
that generates in place the next permutation of size n.
It returns 0 on success and 1 if no more permutations exist.
The permutations should be generated in lexicographic order.
The first permutation should be: 0 1 2 3 ... n-1

Modify generate_n_queens_serial so that it generates all permutations. If the flag is set, for each permutation it should call get_array_string and print the result. The main program should print the count of the number of permutations found.

Test this by outputting all permutations for n = 1, 2, 3, 4, and 5.
Then test this using the flag equal to 0 (so that the permutations are not printed) for n = 6, 7, 8, 9, 10, 11, and 12. In each case the count should be n!. Save the output.

Part 2
Write the function
int check_diagonal(int *list, int n);
That assumes that list contains a permutation of size n and returns true if it satisfies the diagonal property of the n-queens problem.

Use this in generate_n_queens_serial to find all solutions to the n-queens problem. Print all solutions for n between 1 and 6. Print just the count for n between 7 and 12. Save the output.

Part 3
In this part we will prepare to use POSIX threads so that the calculation is faster when run on a multi-core machine.

Write the function
int generate_n_queens_serial_one(int n, int out_flag, int first);
That generates all solutions to the n-queens problems whose first value is first. That is, all of the arrays generated have first as the first element of the array.
To do this, find the smallest permutation that begins with first and use that one as a starting point. Continue generating new permutations until the first element changes. Otherwise the function will be similar to generate_n_queens_serial.

Test this by writing a main program that calls this for all possible values of first and see that it generates all of the solutions you found in Part 2.

Put the following typedef in your library:

typedef struct ti {
   int n;
   int first;
   int out_flag;
   int result;
} thread_info_t;
and write the function:
void *queens_thread(void *infopointer)
that takes a pointer of type thread_info_t and calls generate_n_queens_serial_one with the appropriate parameters. It will store the return value of generate_q_queens_serial in the result field and return NULL.
Have queens_thread print the value of first and the number of solutions found all on one line, independent of the value of flag.

Test this by writing a main program that takes n as its command line parameter and calls queens_thread in a loop for all possible values of first. It will then display the result for each call. Run this for the same values on n as in Part 2 and save the output. Verify that it gives the same results as your previous programs.

Part 4
Write another main program that takes a single command line parameter, n and creates n threads, each of which executes queens_thread for one value of first between 0 and n-1. Join the threads and output the total number of solutions found. Test this with values of n up to 12 and compare the results with your previous solutions.

Part 5
In the above program, all of the threads are outputting to standard output concurrently. There is a possibility (although it is unlikely) that the output will not be correct because the two lines generated by different threads might be interleaved.

Solve this problem while maintaining the maximal parallelism.

Determine how long it takes to run the serial (Part 3) and parallel (Part 6) versions of the program for values of n between 1 and at least 12. You can go higher if you like. Be sure to run the serial and parallel versions on the same type of machine whcih should have at least 2 cores. Make a table of your results. Include the name of the machine and how many cores it has.

Handing in your assignment
Use this cover sheet.