COMP1721 - Higher Computing 1B

This lab involves:

• Manipulating a 2 dimensional array

Create a separate directory (lab05 is a good name) using mkdir for this week's lab exercises.

Exercise 1: N Queens

For those who don't play chess, here is a reminder of how queens attack. Queens can attack in three ways

First a queen can attack a piece on the same row of the chessboard. So we can't place two queens on the same row of the chessboard. For example, we can't place two queens like this:

. . . . . . 

. . . . . . 

. q . . . q 

. . . . . . 

. . . . . . 

. . . . . . 

A queen also can attack a piece on the same column of the chessboard. So we can't place two queens on the same column of the chessboard. For example, we can't place two queens like this:

. . . . . . 

. . . . . . 

q . . . . . 

. . . . . . 

q . . . . . 

. . . . . . 

A queen also can attack a piece on the same diagonal of the chessboard. So we can't place two queens on the same diagonal of the chessboard. For example, we can't place two queens like this:

. . . . . . 

. . . . . . 

q . . . . . 

. . . . . . 

. . . . . . 

. . . q . . 

or like this:

. . . . . . 

. . . . . . 

. . . . q . 

. . . . . . 

. . . . . . 

. q . . . . 

Getting Started

The program use a simple and very inefficient strategy to find a suitable placement of 6 queens on a 6x6 board.

It repeatedly generates a random placement of the 6 queens on the 6x6 board until it finds one where no queen can attack any other.

The function you must complete is called no_queens_attack_each_other. It is used to check if any two queens can attack each other. It is given the randomly generated placement of queens on the chessboard. It must check if there are 2 queens on the same row or on the same column or on the same diagonal.

Hints

The program you have been given compiles and runs. It will generate a random placement of queens and print it. Sadly the placement will almost certainly have queens which can attack each other.

This is because no_queens_attack_each_other always returns true (1). It rejects no random placements.

First modify no_queens_attack_each_other so that it returns false (0) if there are two queens in the same row. Check that random placements are rejected if they have two queens in the same row.

Then add code to no_queens_attack_each_other so that it returns false (0) if there are two queens in the same column. Check that random placements are rejected if they have two queens in the same row or two queens in the same column.

Last, and this is quite tricky, add code to no_queens_attack_each_other so that it returns false (0) if there are two queens in the same diagonal.

Finished?

After your tutor has checked that your answer is correct and given you the lab mark, you must also submit your answer using give. Here is the command to use:

% /home/cs1721/bin/classrun -give lab05 queens.c

Exercise 2 (optional and difficult): Efficient N Queens

Your program should be able to solve find solutions for n < 30 in less than a minute (on a CSE lab machine)

Note, you will need to use a completely different approach to that given in exercise 1.

Use gcc -O3 not dcc to compile your program - this will result in much faster execution.

An extra lab mark is available if you complete this exercise.

If you complete this extra exercise, and your tutor has checked that your answer is correct and given you the extra lab mark, submit your answers to bothe exercises using give. Here is the command to use:

% /home/cs1721/bin/classrun -give lab05 queens.c nqueens.c