Due Date
See the
calendar for due date.
Objectives:
- Implement a backtracking algorithm
Description:
The research team was so pleased with your previous labs, that you have been asked to write a C++ program by applying a backtracking algorithm to get a solution of the classic N-Queens problem.
The N-Queens problem is to place
N queens on an
N x
N chess board, such that no queen is attacking another queen.
A queen is attacking another queen if they're in the same row, column or diagonal.
If a solution is not possible, then print out (in the output file specified in main()):
No solution possible for N queens!
(where
N is the number of queens).
If there is a solution, print out (in the output file specified in main()) a "
Q" where the queens belong and a "
-" otherwise. For example,
Q - - - -
- - Q - -
- - - - Q
- Q - - -
- - - Q -
Requirements
Your program needs to meet the the following requirements:
- Use the following source code as the driver for this lab: labBacktracking-main.cpp.
- Your program must compile and run in both Visual Studio and on ranger. On ranger, it must compile with the following command:
g++ -std=c++0x *.cpp -o labBacktracking
- Use C++ comments to identify the location in your code that does the backtracking. The check for this will be automated, so use the following syntax:
/*** BACKTRACKING HERE ***/
- Include a completed rubric and number of hours spent on the assignment. Please copy and paste the rubric into a new file inside your project directory. Name the file: rubric-yourlastname.txt.
Submission
Before preparing your project for submission, remove the
debug and
ipch directories (if present) and any
.sdf files.
Additionally, remove any other files not associated with labBacktracking.
Zip the whole project folder (
e.g., by right-clicking on the folder and choosing
send to::Compressed (zipped folder)). Name your zip file as
labBacktracking.zip.
Make sure that all of the source code files are in your zipped file.
Submit your zip file at
https://3110.cs.mtsu.edu/.
Rubric:
Points Item
---------- --------------------------------------------------------------
Requirements met:
_____ / 30 + Backtracking algorithm and comment
_____ / + Compiles and runs in Visual Studio and on ranger
_____ / 50 + Correct output (matches the format of the example exactly & demonstrates correct execution)
_____ / 80 Total
_____ Approximate number of hours spent
Optional (worth 0 points!)
- Printout all possible solutions