CSCI 241 - Homework 2: N-Queens

Due by 11:59.59pm Wed, 24 Sept 2008

Introduction

The N-Queens problem is a common (and old) recreational mathematical puzzle. Originally known as the "8-Queens Puzzle" a general version can be expressed as follows:

Given a standard 8x8 chessboard, how can you place 8 queens on the board such that no queen is attacking (able to take) another one.

In 1850, Franz Nauck generalized this problem to placing N queens on a NxN sized chessboard. When N=1, the solution is trivial. There is only one square and there is only one queen (therefore, no other queen can be attacking it). For N=2 or N=3, there are no solutions. For any N greater than or equal to 4, there is at least one solution.

You may have seen this puzzle before as it is often used in computer science as an example of a backtracking algorithm (the technique we'll be using), permutation generation, divide-and-conquer, and constraint satisfaction problems, among others.

Problem Specification

Your task is to construct a program that is capable of solving the N-Queens problem for an arbitrary, non-negative sized board (N>0). I am only going to be testing for solutions where N is less than or equal to 12, but your program should be capable of solving larger sized problems.

By definition, two queens are said to be attacking if they occur in the same row, column, or on the same diagonal.

To gain full credit, your program must solve the N-Queen problem recursively. Additionally, you may not output solutions based on pre-computed or partially pre-computed information. Your program will need a constant to limit the board size, a function that gets the size of the puzzle to solve, a function or functions that calculate the solution, a way to print out the all the solutions that are found, and a count of the solutions found.

Your program should run in a reasonable amount of time. Probably less than 10 seconds for N=12.

You should solve this problem using a recursive backtracking approach which we will discuss in class.

Programming Details

Maximum board size

Create a constant MAX_QUEENS that defines the maximum size problem your program is willing to solve.

    #define MAX_QUEENS 20

Coordinate system

We'll be using a 0-based coordinate system with 0,0 being the top left corner as shown below for an 8x8 board.

	0	1	2	3	4	5	6	7
0
1
2
3
4
5
6
7

Printing a solution

Given the following solution to an 8x8 problem, you should output a single line containing the coordinates of the queens starting in row 0 and proceeding to row 7 in the format (row,col). So, the first digits should always be 0, 1, ..., N-1.

	0	1	2	3	4	5	6	7
0
1
2
3
4
5
6
7

    (0,0)(1,4)(2,7)(3,5)(4,2)(5,6)(6,1)(7,3)

Required Functions

There are a number of functions that I want you to create for this program:

• int getint() - read in a non-negative integer value from stdin. I'll suggest you just modify your getint() from HW1 to handle multiple digits, and then read in (and discard) until the end of the line or EOF. It should read in a line of input (i.e., until you see \n) and extract the first integer value it sees. Be sure to handle multi-digit input (see atoi() in chapter 2 for hints on how to implement this).

  In the case of an error you should return either:

  • -1 if there is no number on the line
  • -2 if EOF is encountered and no digits have been seen so far -- otherwise return the current total.

  You might find it useful to "unread" a character. You can do so using ungetc(ch, stdin); where "ch" is the character you just read. Note that you can only un-read one character at a time.

• int getsize(int low, int high) - prompt the user to enter a value between low and high and loop/re-prompt until they do. Return that value. If getint signals EOF, return a default value of 8.
• void init_board(int board[], int max) - initialize the chessboard for the current attempt to solve the puzzle.
• void print_board(int board[], int max) - print out the current state of the board in the format described above.
• int check_board(int board[], int row) - check to see if rows 0 to row are not attacking each other. Return 1 if board is good, 0 if there is an attacking queen.
• void solve(int board[], int current_row, int max) - recursive function to solve this puzzle and call print_board() when a solution is found.

Makefile

I also want you to create a Makefile for this project that compiles this program using make into a file called nqueens and also has a target clean that removes the binary and other temporary files.

Timing

You can use the Unix program time to report to you the amount of time a program took when running. You are concerned with the user and system time, and not so much the wall-clock time. See the man page for more details.

I/O will slow the running time of the system down. For your measurements, you are welcome to turn off the printing of the results, or redirect the results into a file/nowhere. Here's a simple command that should let you measure the runtime of N=12 but remove much of the overhead of printing.

sh -c "echo 12 | ./nqueens > /dev/null"

Sample program

I've included my sample solution in ~kuperman/pub/cs241/hw02/ with binaries that should work on both lab machines and OCCS. Let me know if you encounter any bugs or unexpected behavior.

If you want to check your results for larger N, you can redirect the output to a file and then use diff. Just be sure that you are matching the format or you will get tons of output.

    echo 12 | ./nqueens > mine.out
    echo 12 | ~kuperman/pub/cs241/hw02/nqueens > yours.out
    diff mine.out yours.out

README

As with the first project, I want you to create a file called README

1. Your name and the date
2. A list of the programs with a short one-line description of each
3. The runtimes for solving n=8, 9, 10, 11, and 12
4. A list of all compilation problems, warnings, or errors. Note that for full marks, it is expected that you will have corrected all of these things.
5. The honor code statement: I have adhered to the Honor Code in this assignment

Extra credit

For a small amount of extra-credit (no more than 10%), implement the same algorithm in Java. In your README file, chart the differences in runtime between C and Java up to at least N=12. You may want to go higher than that as well, but don't do so on OCCS.

Since we care about the speed of this program, you might find that adding in the compiler option -O or even -O4 for optimizations that will help speed things up dramatically.

To get full bonus marks, add in a rule that will compile your Java program as part of all and also removes the *.class files when you "make clean".

handin

Now you should make clean to get rid of your executables and handin your folder containing your source files, README, and Makefile.

    % cd ~/cs241
    % handin -c 241 -a 2 hw2
    % lshand

Grading

Here is what I am looking for in this assignment:

• A working Makefile with your program, all, and clean as targets
• A working nqueens.c with requisite output. Solution should be recursive, and all possible solutions for a given n should be printed.
• All programs should have comments including your name and date at the top. Functions should have a brief description of what they do and an explanation of their return values.
• All programs should compile using gccx on OCCS or Gandalf with no compiler warnings or errors.

Last Modified: September 11, 2008 - Benjamin A. Kuperman