Provide a simple menu for user to choose and run commands.

Allow user to enter the checker board size.

Display all solutions on the 2D checker board presentation.

Display only the unique solutions.

User Interface

=====n_Queens Test Menu=====

size - Checker Board Size display - Display solutions unique - Display Unique solutions quit - Quit

Sample Output

One possible 8-Queens solution: *|0|1|2|3|4|5|6|7|* 0|X|_|_|_|_|_|_|_|0 1|_|_|_|_|X|_|_|_|1 2|_|_|_|_|_|_|_|X|2 3|_|_|_|_|_|X|_|_|3 4|_|_|X|_|_|_|_|_|4 5|_|_|_|_|_|_|X|_|5 6|_|X|_|_|_|_|_|_|6 7|_|_|_|X|_|_|_|_|7 *|0|1|2|3|4|5|6|7|* One possible 14-Queens solution: *|0|1|2|3|4|5|6|7|8|9|0|1|2|3|* 0|X|_|_|_|_|_|_|_|_|_|_|_|_|_|0 1|_|_|X|_|_|_|_|_|_|_|_|_|_|_|1 2|_|_|_|_|X|_|_|_|_|_|_|_|_|_|2 3|_|_|_|_|_|_|X|_|_|_|_|_|_|_|3 4|_|_|_|_|_|_|_|_|_|_|_|X|_|_|4 5|_|_|_|_|_|_|_|_|_|X|_|_|_|_|5 6|_|_|_|_|_|_|_|_|_|_|_|_|X|_|6 7|_|_|_|X|_|_|_|_|_|_|_|_|_|_|7 8|_|_|_|_|_|_|_|_|_|_|_|_|_|X|8 9|_|_|_|_|_|_|_|_|X|_|_|_|_|_|9 0|_|X|_|_|_|_|_|_|_|_|_|_|_|_|0 1|_|_|_|_|_|X|_|_|_|_|_|_|_|_|1 2|_|_|_|_|_|_|_|X|_|_|_|_|_|_|2 3|_|_|_|_|_|_|_|_|_|_|X|_|_|_|3 *|0|1|2|3|4|5|6|7|8|9|0|1|2|3|*

Starter kit

The n_queens.cpp in the class github contains an ASCII checker board structure, a outputBoard() function to display solutions on the checker board, a pre-defined user interface and a complete back track algorithm for all distinct solutions.

The N-Queens C++ Implementation (Links to an external site.)Links to an external site. by WikiBooks that contains isSafe() and solve() methods.

The attached rotate_n_mirror.cpp (github) is the the starter of an unique solution to potentially different mirrors and rotations.

You may Google for additional info on this well documented subject online.

Here is an in-line comment for the rotate_n_mirror algorithm:

 // Solution: P(x) = 0 2 4 1 3 // y // ^ // *|0|1|2|3|4|*P(y) // 4|_|_|X|_|_| 2 // 3|_|_|_|_|X| 4 // 2|_|X|_|_|_| 1 // 1|_|_|_|X|_| 3 // 0|X|_|_|_|_| 0 // *|0|1|2|3|4|* > x // P(x)= 0 2 4 1 3 // P(y)= 0 3 1 4 2 // The above posision can be represented as a 2-D or 1-D vector: // vector position { {0,0}, {1,2}, {2,4}, {3,1}, {4,3} }; // vector P(x') = {0,2,4,1,3}, P'(N-x') = {3,1,4,2,0}; // vector P(y') = {0,3,1,4,2}; P'(N-y') = {2,4,1,3,0}; // pos' ---LR---> pos, i.e. p() // x = y'; y = N-x'; // y': 4-3-2-1-0 // x': 0-1-2-3-4 y': 0-1-2-3-4 x: 0-1-2-3-4 // P(x'): 0,2,4,1,3 -tr->P(y'): 0,3,1,4,2 ->reverse-> P(x): 3,1,4,2,0 // ( x': start w/0) (y=N-x': start w/4) // pos' ---RR---> pos // pos' as prev pos, i.e. p() // y = x'; x = N-y'; ditto 

Programming Techniques

Backtracking - we have used stack to perform the backtracking of failed attempt. How exactly we do that?

Dynamic programming (also known as Dynamic Optimization) is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions.

Associative Memory (also known as associative array or container) is the association between a key and a value is often known as a "binding". This binding can be a lot more intuitive to a programmer hence superior than the index or pointers came with the array or container.

Stream processing allows some applications to more easily exploit a limited form of parallel processing (Links to an external site.)Links to an external site., which we already learn in the iostream, fstream, and sstream by pipelining segments of processes and/or executed in different processors.

Object Oriented programming is to encapsulate all related data and functionality inside of a class. In this N-Queens exercise, we can create an n_queen class to hold all most of the code that we have written excluding the user interface portion of code.

Assessment to the Programing Techniques used

We have applied four (4) programming techniques to solve this N-Queens problem. Please provide your assessment and reasons on each of the four approach the way you understand it:

Backtracking - Where and how (what mechanism) we applied the backtracking algorithm?

Dynamic programming - Please identify and describe the two (or more) places that we applied dynamic programming (one explicitly and another one implicitly mentioned in the class.)

Associative container - Please describe the pros and cons of using the map container to solve the unique solutions by associating the pattern with its type description as key/value pair? Please compare this solution with the solution that you would otherwise deployed.

Stream processing - How and where the stream processing help you in solving this problem?

Test Run Example

Design Pattern

In this assignment we are using the Dyanamic Programming to reduce the design complexity. The two design patterns introduced in our approach are:

using the DFS backtracking on a Stack data structure to find all solutions, and

using the Matrix rotation and mirror on an Associative Array to identify different kinds of duplicaions.

/*
	* N-Queen Starter - Solving Duplicates with MAP
	*/
	#include
	#include
	#include
	#include
	#include
	using namespace std;
	void outputBoard(vector, int);
	bool isSafe(int queen_number, int row_position, vector position);
	void solve(int k, int N, vector& position);
	void rotateLeft(vector position, int size, map& solutions, int counter, bool isMirrored);
	void uniqueSolve(int k, int N, vector& position, map& solutions, int& counter);
	const string MIRRORED = "MIRRORED";
	int main() {
	int size = 8; // start up default to standard checker board size
	// The following 7 lines of code are to test the outputBoard()
	// You may choose to comment out in your submitted n_queens.cpp
	vector queen8 = { 0, 4, 7, 5, 2, 6, 1, 3 };
	vector queen14 = { 0, 2, 4, 6, 11, 9, 12, 3, 13, 8, 1, 5, 7, 10 };
	cout
	outputBoard(queen8, size);
	cout
	size = 14;
	outputBoard(queen14, size);
	// end of outputBoard() test
	auto menu=[]() {
	cout
	};
	string choice;
	while (true) {
	menu();
	cin >> choice; cin.ignore(1000,10);
	switch (choice[0]) {
	case 's': // change size
	case 'S':
	cout
	cin >> size;
	cin.ignore(1000, 10);
	cout
	if (size != 1 && size
	cout
	break;
	}
	break;
	case 'd': // display all solutions
	case 'D':
	{
	cout
	}
	break;
	case 'u': // display only the unique solutions
	case 'U':
	{
	cout
	}
	break;
	case 'q':
	case 'Q':
	return 0;
	break;
	default:
	cout
	break;
	}
	}
	return 0;
	}
	/*
	* precondition: input the n-queens\' solution array and its size
	* postcondition: output the checker board
	*/
	void outputBoard(vector ar, int size) {
	int i, j;
	cout
	for (i = 0; i
	cout
	for (i = 0; i
	cout
	for (j = 0; j
	if (j == ar[i]) cout
	else cout
	cout
	}
	cout
	for (i = 0; i
	cout
	} The program is suppose to be done using dynamic programming and the different programming methods were short answer part of this assignment.

N-Queen Test Menu S-Checker Board Size D-Display solutions U-Display Unique solutions Q-Quit Enter your Choice: s Enter Size of checker board: 5 Enter your Choice: u 2 Unique solutions m[02413] #1 Unique Solution m[03142] #1 Mirrored + Rotated m[13024] = #1 Rotated 180 m[14203] = #2 Unique Solution m[20314] #1 Mirrored + Rotated m[24130] - #1 Rotated 090 m[30241] - #2 MIRRORED m[31420] - #1 MIRRORED m[41302] #1 Rotated 270 m[42031] - #1 Mirrored + Rotated 10 solutions found. 270 090 180 Enter your Choice N-Queen Test Menu S-Checker Board Size D-Display solutions U-Display Unique solutions Q-Quit Enter your Choice: s Enter Size of checker board: 5 Enter your Choice: u 2 Unique solutions m[02413] #1 Unique Solution m[03142] #1 Mirrored + Rotated m[13024] = #1 Rotated 180 m[14203] = #2 Unique Solution m[20314] #1 Mirrored + Rotated m[24130] - #1 Rotated 090 m[30241] - #2 MIRRORED m[31420] - #1 MIRRORED m[41302] #1 Rotated 270 m[42031] - #1 Mirrored + Rotated 10 solutions found. 270 090 180 Enter your Choice