Reference no: EM131658499

Project

Your first project will be to write a C program to solve the n-Queens problem. The objective is to place n queens on a n × n chess board: no two queens are allowed to be in the same row, column, or a diagonal.

You can represent a board configuration with a simple n-element sequence Q_n = {q₀ q₁ · · · q_n-1}; q_i corresponds to the column position of ith queen in row i. For example, {0 2 1 3} would correspond to the 4 queens in positions (0, 0) (row 0, column 0), (1, 2) (row 1, column 2), (2, 1) (row 2, column 1), and (3, 3) (row 3, column 3). Note that in our representation we do not use row indexes: the ith queen is placed in the ith row and its column index is q_i.

To check whether a sequence Qn solves the n-Queens problem you need to make sure that

1. Two queens do not share a column, i.e. q_i ≠ q_j, for i ≠ j, and

2. Two queens do not share a diagonal, i.e. |q_i - q_j| ≠ |i - j|, when i ≠ j.

There are multiple ways to solve this problem. The simplest one would be to generate all possible configurations and check if they solve the problem. Note that there are nⁿ possible configurations that would need to be checked. You can do better if you realize that you only need to check permutations of numbers 0, . . . , n-1 as possible configurations. (Why?) Note that in the case of the 4 queens that would be 256 possible board configurations, but there are only 24 permutations; you can verify that there are just 4 legal 4-queen placements. However, the method for generating all possible permutations is somewhat involved; it is much easier to generate random permutations.

Your assignment is to write a program to solve n-queens problem for n = 4, . . . , 20 using random board configurations. You should use your randperm function to do this. In addition, you will write two additional functions: checkboard for checking if a permutation solves the problem, and displayboard for printing a solution. Finally, for each board size you should solve the problem 10 times so that you can obtain some statistics on performance of your program.

Detailed requirements:

1. You will seed the random number generator using srandom(seed), where seed ={last 4 digits of your G#}.

2. You will write void randperm(int b[], int n) function to generate random boards. Note that you only need to initialize b[] once for each board size. A simple algorithm for generating a random permutation of elements of a chooses a random number 0 ≤ i ≤ n - 1 and swaps a[i] and a[n - 1]; this step is then repeated for the subsequence a[0 : n - 2].

You can use functions srandom() and random() to generate random numbers. srandom(1) will initialize your random number generator with seed 1, and k = random() will return a random long integer k. To produce a random number j such that 0 ≤ j < p you need a call j = random()%p. To use srandom() and random() you will have to include < stdlib.h >.

2. Write

int checkboard(int b[], int n)

checkboard returns 1 if the board represented by b[] solves n-queens problem, it returns 0 otherwise.

3. Write int displayboard(int b[], int n)

displayboard prints a solution of n-queens problem in an easy to check form. Here is a possible way your output should look for n = 6.

4. For each board size n = 4, . . . , 20 you will run your program 10 times to collect some statistics on its performance. For each n you will calculate min, max, and mean number of random boards generated until a solution was found. To calculate mean value for any board size you need to add up the total number of boards generated for that size and divide it by 10. To calculate the min and max values you can utilize the macros.

5. You will run your program for board sizes n = 4, . . . , 20 ten (10) times. You will display the first solution only for each value of n using displayboard. You will display the following statistics for each size n: min, max, and mean number of boards generated before a solution was found, nⁿ and n!. You can use integers to calculate min and max values but you need to use floats or doubles to calculate the remaining three values.

Attachment:- Assignment File.rar