The n-queens problem reduces to finding n unique integers between 1 and n such that no two numbers in the list differ by the distance between them in the list. 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. Make sure you understand this statement.
One inefficient brute-force method of solving this problem is to pick n random integers between 1 and n and check to see if they are a solution. To be a solution, they must all be different and satisfy the condition above.
We will attempt to use this method to find some solutions to the n-queens problem for various values of n.
When using a brute force method, it is useful to have a lot a computing power at your disposal. Therefore we will try to do this computation in parallel. We can divide the problem of into two parts:
We will think of this as a producer-consumer problem in which the producers generate n distinct integers, and the consumers check whether they satisfy the diagonal property and save them if they are. In this assignment we will use the integers between 0 and n-1 since this is simpler when using arrays whose indexes start at 0.
In this assignment you will solve this problem using POSIX threads with POSIX unnamed semaphores for synchronization.
The consumers will need to store the solutions in a shared buffer.
You can use the program solution_buffer.c and associated files from the lecture as a starting point. This is a protected bounded buffer that allows you to put in items that are arrays of integers of fixed length. It will also make sure that the same item is not inserted more than once.
Assignment 4:
Start by creating a non-threaded producer and consumer.
The producer creates an item which is an array of distinct
integers between 0 and N-1. You need to figure out how to do this.
You can use the randsafe function from Chapter 13 of USP, since
eventually will we need a safe random number generator. You need to find
a way of creating only distinct integers. For now, the producer can just put
the items in a fixed buffer of size 1.
The consumer takes the item in the fixed buffer and determines if it is a solution to the problem. That is, it checks the diagonal property. The consume may assume that when it gets an item, that item contains N unique integers between 0 and N-1. If the item is a solution, the consumer puts the item in the solution_buffer. For this part, your main loop can look something like this:
for (i=0;i< max;i++) {
producer();
consumer();
}
If N is 5, you should be able to find all 10 solutions using a value of
max less than 10,000.
Save the solutions you generated for N=5 in a text file.
Also run for N = 6, 7 and 8 and try to find all of the solutions.
The value of max will need to be increased. Don't try this for
N greater than 9 unless you are running on your own machine.
Note that in this solution, there is no concurrency. The producer and consumer alternate creating an item and processing that item. No synchronization is necessary, even though solution_buffer and saferand are protected. You will need this protection later in the assignment.
Assignment 5, Part 1
Turn the producer and consumer into threads that execute concurrently.
Now you will need a protected buffer of size greater than 1 for storing
the items made by the producer threads. Make a new program called
bounded_buffer.c that is like solution_buffer.c
but allows for items to be removed as well as put in.
Use a moderate (20) size for this buffer. Implement this as a circular
queue. Use three semaphores, full, empty and mutex.
The putin and takeout methods will look like the producer
and consumer semaphore solutions
from the notes. Use variables in and out, to keep track
of where to put items in and where to take them out.
Note that for solution_buffer it is an error if you try to put
an item in the buffer when it is full. This is because items are never removed
from this buffer. For bounded_buffer the caller must wait if the
buffer is full and proceed when there are empty slots.
Start with one producer thread and one consumer thread. Each of these will execute a loop the same number of times. Each time through the producer loop an item will be put in bounder_buffer and each time through the consumer loop an item will be removed from bounded_buffer. Make sure your main program does not exit until the consumer has finished. You can do this by joining the consumer. When finished, print out the solutions found. You should find the same solutions as in Part 0. This program can use two CPUs (or 2 cores) if they are available. If you have a dual-core machine, try doing some timing tests.
Assignment 5, Part 2
Modify your program to use several producers and several consumers.
Now it is more difficult to determine when the all of the threads have
completed. Figure out a way to do this in which the total number of
items generated is independent of the number of producer threads or consumer
threads. If you have 4 cores, how many producer threads and how many consumer
threads should you use? Note that the answer depends on the relative speed
of the producers and consumers.
Handing in your assignment
Use this cover sheet for Assignment 4 and
this this one for Assignment 5.
By Friday, November 2, you must turn in a draft of your bounded_buffer.c program. Just turn this in on a single sheet of paper with you name in the upper right corner.
Consecutively number all of the pages you turn in.