Description
The original version of this problem goes like this – You have a 8 × 8 chessboard, and you have to place 8 queens on this chessboard such that no two of
them threaten each other. Since a queen can attack any piece that shares a row,
column, or diagonal, with it, we are essentially looking to place 8 elements in a
8 × 8 grid such that no two of them share a common row, column, or diagonal.
You can read more about this problem at this link.
The n × n version of this problem asks you to place n queens on a n × n
chessboard. For the first part of this assignment we are seeking just one solution
(among a set of many possible solutions) to this problem. You have to solve
this by a recursive implementation of the backtracking search/algorithm, and it
must be done in an “object-oriented” manner. For the second part, we seek all
possible solutions to the problem, by modifying the code for the first part.
Assume you have gone through the necessary steps to define a n × n chessboard. You must do the following:
1. Write a function is this position safe(i, j), which returns “true” (resp. “false”)
if placing a queen in the (i, j)-th position in the n × n chessboard is safe
(resp. unsafe).
2. Implement a recursive back-tracking search procedure solve(i), as shown
in figure 2, which returns “true” if there is a way to place a queen at the
i-th column of the n × n chessboard, where 0 ≤ i ≤ n − 1 (notice: the
indexing starts from 0 and ends with n − 1). You call solve(0) to solve the
puzzle.
Finding one solution to the N-Queens Problem
Just to get us thinking in object-oriented terms, I want you to do the following:
1. Define a class called Board, it should have a private data member called
size (which is n in the n × n chessboard), and a integer-valued chessboard.
If there is a queen at the (i, j)-th position of the n × n chessboard, then
chessboard[i][j] = 1, otherwise, chessboard[i][j] = 0.
2. Keep in mind, the value of n(= size) is not known a priori – it will be
known at runtime when the user inputs it via the commandline (you should pay attention to this when I go over it in class). One
way is to accomplish this is to have a private data member declared as int
**chessboard, and once the size of the chessboard is known, you can declare
an array using a pointer-to-pointers approach. If you need help with this
1
Boolean Solve(column)
1: if column ≥ n then
2: You have solved the puzzle.
3: else
4: for 0 ≤ row ≤ n − 1 do
5: if is this position safe(row, column) then
6: Place queen at (row, column)-position in the n × n chessboard.
7: if Solve(column+1) then
8: Return true.
9: else
10: Remove queen at (row, column)-position in the n × n chessboard.
Placing it here was a bad idea.
11: end if
12: end if
13: end for
14: end if
{ /* If we got here then all assignments of the queen in (column-th column
are invalid. So, we return false*/}.
15: Return false.
Figure 1: Pseudo-code for the recursive implementation of the exhaustivesearch algorithm for the (n × n) Queens-puzzle. You solve the puzzle by calling
Solve(0), assuming the indices are in the range {0, 1, . . . , n − 1}.
2
// N Queens Problem v i a ( B ack t r ack ing , wh ich i s implemen ted by ) Recurs ion
// Wr i t ten by Pro f . S r e e n i v a s f o r IE523 : F i n a n c i a l Computing
#include
#include ” N queens . h”
int main ( int argc , char ∗ const argv [ ] )
{
Board x ;
int b o a r d s i z e ;
s s c a n f ( argv [ 1 ] , ”%d” , &b o a r d s i z e ) ;
x . nQueens ( b o a r d s i z e ) ;
return 0 ;
}
Figure 2: f16 prog1 hint.cpp: C++ code to help you with Programming Assignment #1.
part, you might want to see the handout “Programming Assignment 5:
Dynamic Arrays in C++” in the Bootcamp folder on Compass.
3. I also want you to write a member function that prints the (solved) chessboard. Although I do not want you to mimic my output exactly, something
similar will be sufficient.
4. I have provided partial code samples for the *.cpp file in figure 2, and the
*.h file in figure 3. Two sample outputs are shown in figure 4.
Here is what I want from you for the first part of the assignment
1. A well-commented C++ code that produces output that is similar to what
is shown in figure 4.
You will submit this electronically to the TA before the due date.
Finding all solutions to the N-Queens Problem
.
For this part of the assignment I want you to extend/modify the code for
the previous part of the assignment, where you found a single solution to the
N-Queens Problem, to find all solutions to the N-Queens problem.
Keep in mind that the number of solutions can grow to be very large very
quickly. Table 1 shows the number of solutions for different values of N. I am
looking for outputs along the lines of what is shown in figures 5, 6 and 7.
3
#i f n d e f N queen s
#de f ine N queen s
using namespace s t d ;
c l a s s Board
{
/ / p r i v a t e d a t a m em b e r : s i z e o f t h e b o a r d
i n t s i z e ;
/ / p o i n t e r −t o −p o i n t e r i n i t i a l i z a t i o n o f t h e b o a r d
i n t ∗∗ c h e s s b o a r d ;
/ / p r i v a t e m em b e r f u n c t i o n : r e t u r n s ’ f a l s e ’ i f
/ / t h e ( row , c o l ) p o s i t i o n i s n o t s a f e .
bool i s t h i s p o s i t i o n s a f e ( i n t row , i n t c o l )
{
/ / w r i t e t h e a p p r o p r i a t e c o d e on y o u r own t h a t r e t u r n s
/ / ” t r u e ” i f t h e ( row , c o l ) p o s i t i o n i s s a f e . I f i t i s
/ / u n s a f e ( i . e . s om e o t h e r q u e e n c a n t h r e a t e n t h i s p o s i t i o n )
/ / r e t u r n ” f a l s e ”
}
/ / p r i v a t e m em b e r f u n c t i o n : i n i t i a l i z e s t h e ( n x n ) c h e s s b o a r d
void i n i t i a l i z e ( i n t n )
{
s i z e = n ;
/ / w r i t e t h e a p p r o p r i a t e c o d e t h a t u s e s t h e p o i n t e r −t o −p o i n t e r
/ / m e t h o d t o i n i t i a l i z e t h e ( n x n ) c h e s s b o a r d . On c e i n i t i a l i z e d ,
/ / p u t z e r o s i n a l l e n t r i e s . L a t e r on , i f y o u p l a c e d a q u e e n i n
/ / t h e ( i , j )− t h p o s i t i o n , t h e n c h e s s b o a r d [ i ] [ j ] w i l l b e 1 .
}
/ / p r i v a t e m em b e r f u n c t i o n : p r i n t s t h e b o a r d p o s i t i o n
void p r i n t b o a r d ( )
{
s t d : : c o u t << s i z e << ”−Queens Problem S o l u t i o n ” << s t d : : e n d l ;
/ / w r i t e t h e a p p r o p r i a t e c o d e h e r e t o p r i n t o u t t h e s o l v e d
/ / b o a r d a s s h o w n i n t h e a s s i g n m e n t d e s c r i p t i o n
}
/ / p r i v a t e m em b e r f u n c t i o n : r e c u r s i v e b a c k t r a c k i n g
bool s o l v e ( i n t c o l )
{
/ / i m p l e m e n t t h e r e c u r s i v e b a c k t r a c k i n g p r o c e d u r e d e s c r i b e d i n
/ / p s e u d o c o d e f o r m a t i n f i g u r e 1 o f t h e d e s c r i p t i o n o f t h e f i r s t
/ / p r o g r a m m i n g a s s i g n m e n t
}
pub l ic :
/ / S o l v e s t h e n−Q u e e n s p r o b l e m b y ( r e c u r s i v e ) b a c k t r a c k i n g
void nQueens ( i n t n )
{
i n i t i a l i z e ( n ) ;
i f ( s o l v e ( 0 ) )
p r i n t b o a r d ( ) ;
e l s e
s t d : : c o u t << ” There i s no s o l u t i o n t o t h e ” << n << ”−Queens Problem ” << s t d : : e n d l ;
}
} ;
#end i f
Figure 3: f16 prog1 hint.h: C++ code to help you with Programming Assignment #1.
4
Figure 4: Sample output of the code shown in figure 2.
N × N Total #of Solutions
8 × 8 92
9 × 9 352
10 × 10 724
11 × 11 2,680
12 × 12 14,200
13 × 13 73,712
etc. etc
Table 1: #Solutions to the N-Queens problem as a function of N.
5
Figure 5: Sample output of the code that computes all solutions to the NQueens Problem. This is for N = 4.
6
Figure 6: Sample output of the code that computes all solutions to the NQueens Problem. This is for N = 8.
7
Figure 7: Sample output of the code that computes all solutions to the NQueens Problem. This is for N = 11.
8
