In this assignment, you are going to solve the eight-queens problem in C.

Eight Queens Problem

The problem is how to find a way to place eight queens on a chessboard (8x8 grid) so that no queen attacks any other queen. An alternate way of expressing the problem is to place eight objects (one per grid cell) on an eight by eight 2-dimensional array, such that no object shares a common row, column, or diagonal. It has long been known that there are 92 solutions to the problem.

Approach

Data Structure

One of the easiest ways to model the problem is an array to represent the chessboard grid. This should be a two dimensional array, as follows:

#define N 8 static int Matrix[N][N];

A 2D array can be though of as a 1D sequence of bytes in row-major order. Thus, given a position in a 1D array with index i, the corresponding row and column of an equivalent 2D array (of dimensions NxN) can be calculated as follows:

row = i/8 and column = i%8

Note: division is integer division.

Initially, you could set all the elements in the grid to be 0, showing that no queen is on the board. However, the "static" keyword above will effectively set all elements of the 2D Matrix to 0. When you want to place a queen in a specific cell, you should set that element to be 1.

Algorithms

You are suggested to use recursive techniques to solve this problem. Noted that whether the ith queen could be placed into the current position is dependent on whether all the following i+1(th) to (N-1)th queens can find their positions. Note that in C, an array starts with index 0, so the (N-1)th queen is the last one. Here is some helper pseudocode to get you started:

#define N 8 int matrix[N][N]; void print_matrix(){ int i,j; for ( i = 0 ; i < N ; i++ ){ for( j = 0 ; j < N ; j++ ){ printf( "%d ", matrix[i][j]); } printf( " " ); } printf( " " ); } int valid( int i , int j ){ // Check the current queen in row i and column j is not in the same row, column or diagonal as another queen // If valid, return 1 else return 0 // Write your code here... } void putall( int id ){ /*id: index for the current queen*/ for ( i = start_position of id; i < 8*8 ; i++ ){ if( valid(i) ){ /*if current position is a valid one*/ chessboard[i/8][i%8] = 1; if( id == N-1 ){ /*if this is the last one to place*/ find a solution and output result } else{ calculate the start_position for next queen. putall( id + 1 ); } } } } 

Output

Both your C code and assembly code should output a 8*8 matrix with space " " as the delimiter like the following:

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 

First Deliverable

You should first attempt to write a solution to the 8 Queens problem which produces ONE valid 8x8 grid.

Bonus Deliverable

If you get the first deliverable completed you should produce a second version of your code that prints all 92 valid solutions.

Submission

You should submit all source files and a README file to explain how to run and test your code using gsubmit. Please tar all your source files into one file called PA0.tar:

shell-prompt> tar cvzf PA0.tar 8queens-one-soln.c 8queens-all-solns.c README

Then read the class website main page for help on how to use gsubmit.