Question
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
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 | |
bool isSafe(int queen_number, int row_position, vector | |
void solve(int k, int N, vector | |
void rotateLeft(vector | |
void uniqueSolve(int k, int N, vector | |
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 | |
vector | |
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 | |
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. |
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started