This question came from the homework4 in the DS class. Here I met two problems, one is how to show the solutions right; while another one is how to make the program recognize the integer from the bash.

Below is my final code:

#include<iostream>
#include<stdio.h>						// include atoi()
#include<stdlib.h>
using namespace std;

class Queen{
public:
	Queen(int k = 8);
	~Queen();
	
	void PrintSolution();
	void QueenOne(int k);				// 回溯的具体实现函数
	int GetCount();

private:
	int n;
	int count;
	int *line;
	bool *a, *b, *c;
};

int main(int argc, char* argv[]) {
	int n = atoi(argv[1]);				// 获得传入数值。
	Queen queen(n);
	queen.QueenOne(1);
	cout << queen.GetCount() << " in total.\n";
	return 0;
}

/*************************************
* Private Method: QueenOne(int k)
* 回溯的具体实现函数
* 
*************************************/
void Queen::QueenOne(int k) {
	if(k>n) {
		count++;
		PrintSolution();
	}
	else{
		for(int i=1; i<=n; i++) {
			if(a[i] && b[k+i-1] && c[k-i+n]) {
				a[i] = b[k+i-1] = c[k-i+n] = false;
				line[k] = i;
				QueenOne(k+1);
				a[i] = b[k+i-1] = c[k-i+n] = true;
			}
		}
	}
}


/**************************************
* Priavte Method: PrintSolution()
* 输出当前得到的解
*
**************************************/
void Queen::PrintSolution() {
	for(int i=1; i<=n; i++) {
		for(int j=1; j<line[i]; j++)
			cout << ".";
		cout << "Q";
		for(int j=line[i]+1; j<=n; j++)
			cout << ".";
		cout << endl;
	}
	cout << endl;
}

/**************************************
* Public Method: GetCount()
* return the count of solutions.
* 
**************************************/
int Queen::GetCount() {
	return count;
}

/**************************************
* 构造函数
* 如果没有输入参数,默认n = 8
*
**************************************/
Queen::Queen(int k): n(k) {
	count = 0;
	line = new int[n+1];
	a = new bool[n+1];
	b = new bool[2*n+1];
	c = new bool[2*n+1];
	for(int i=0; i<n+1; i++) {
		a[i] = true;
		line[i] = 0;
	}
	for(int i=0; i<2*n+1; i++) {
		b[i] = true;
		c[i] = true;
	}
}

/**************************************
* 析构函数
* 
**************************************/
Queen::~Queen() {
	delete[] line;
	delete[] a;
	delete[] b;
	delete[] c;
}

The homework4

###Introduction

The N-queens problem is the problem of positioning N Queens on an N x N chess board such that no queen attacks another (i.e. they do not share the same row, column, or diagonal).

###Requirement

Your task is to write a program that accept 1 argument (i.e. N) from the command line and print all solutions. The argument stands for N, where we have 4 <= N <= 10.

Your program should behave just like the sample:

bob@bob-pc:~/$ ./NQueens 4
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

2 in total. 
bob@bob-pc:~/$ 

Your should use recursive function in your program.

###Hand in

You should turn in all files via turnin command like:

$ turnin homework4@cplusplus NQueens.cpp Makefile ...