Description
The most powerful piece in the game of chess is the queen, which can move any number
of squares in any direction, horizontally, vertically, or diagonally. For example, the queen
shown in the following chessboard of size can move to any of the marked squares.
Even though the queen can cover a large number of squares, it is possible to place
queens on an chessboard so that none of them can attack any of the others, as
shown in the following diagram:
Write a C++ program that solves the problem of whether it is possible to place queens
for on an chessboard so that none of them can move to a square
occupied by any of the others in a single turn. Your program should either display a
solution if it finds one or report that no solutions exists.
The routine simply reads several values of between and from the and
for each value of it calls the following routine to place the queens on the chessboard.
This routine first creates a two-dimensional
of vectors of type for the given size Then, it calls the routine
to initialize a RNG with the value and set all positions on the
chessboard to To place the queens on the chessboard, starting from the
first row, it prints out the chessboard size and calls to routine
as explained below. If the returned value of is then it calls
the routine to print out the contents of the chessboard on by
N Queens Puzzle
2
showing the positions of the queens on the chessboard, otherwise, it prints a
message indicating that a solution does not exists.
This
recursive routine starts on the row number and gets a random column
number between and ( ) from the RNG, and it checks if a
queen can be placed on the location It calls the routine as
explained below, to determine if the location is safe, so the queen can be placed in
that location. If the is not the last row on the it continues to the next
row by making a recursive call. If a queen cannot be placed on the column
then it chooses another column in the given and if none of the columns in the
turns out invalid, then the returned value of the recursive call will be In
this case, by backtracking, this routine simply returns to the previous row and
chooses another column to replace the queen in that row. If the backtracking
goes all the way to the first raw and none of the columns in that row results a
successful placement, then the routine returns to calling routine.
This
routine checks if a queen can be placed in the row number and the column
number on the If the answer is yes, then it returns If there is
another queen in the location then the cannot be equal to since the
queens are placed on the one piece at a time, but those two queens can be in
the same column if and it can be easily verified that they can be in the
same diagonal if
Put the declarations of all constants and routines that you use in your program in the
header file and the implementation of all routines in the source file
At the top of your source file, insert the following statement:
To compile the source files and link the generated object files with the system library
routines, first make a link to in directory: from your
working directory, and then execute:
To test of your program, execute: The correct output file,
is in the same directory with Since you execute your program with a random
value, you’ll get a different placement of the queens on the chessboard each time.
For your information, the total number of possible placements is given as: for
for for for for for and for but some
solutions differ only by symmetry operations (rotations and reflections) of the
chessboard.
When your program is ready, mail its source and header files to your TA by executing:
