$29
Programming Assignment 1: N Queens Problem Solution
The original version of this problem goes like this { You have a 8 8 chess-board, 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 rst 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 rst part.
Assume you have gone through the necessary steps to de ne a n n chess-board. 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 gure 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. De ne 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 command-line (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
f /* If we got here then all assignments of the queen in (column-th column are invalid. So, we return false*/g.
15: Return false.
Figure 1: Pseudo-code for the recursive implementation of the exhaustive-search algorithm for the (n n) Queens-puzzle. You solve the puzzle by calling Solve(0), assuming the indices are in the range f0; 1; : : : ; n 1g.
2
//
N Queens Problem
v i a
( B a c k t r a c k i n g , which i s implemented by ) R e c u r s i o n
// W r i t t e n by Prof .
S r e e n i v a s f o r
IE523 : F i n a n c i a l Computing
#include <i o s t r e a m >
#include " N queens . h"
int
main
( int
argc ,
char
const
argv [ ] )
f
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 ) ;
g
return 0 ;
Figure 2: f16 prog1 hint.cpp: C++ code to help you with Programming Assign-ment #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) chess-board. Although I do not want you to mimic my output exactly, something similar will be su cient.
4. I have provided partial code samples for the *.cpp le in gure 2, and the *.h le in gure 3. Two sample outputs are shown in gure 4.
Here is what I want from you for the rst part of the assignment
1. A well-commented C++ code that produces output that is similar to what is shown in gure 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 nd 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 di erent values of N. I am looking for outputs along the lines of what is shown in gures 5, 6 and 7.
3
#i f n d e f
N queens
#define
N queens
using namespace s t d ;
c l a s s Board
f
/ / p r i v a t e d a t a m e m b e r : s i z e o f t h e b o a r d
int 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
int
c h e s s
b o a r d ;
/ / p r i v a t e m e m 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 ( int
row ,
int c o l )
f
/ / w r i t e
t h e
a p p r o p r i a t e c o d e
o n 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 o m 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 "
g
/ / p r i v a t e m e m 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 ( int n )
f
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 .
O n 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
g
/ / 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 e m 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 ( )
f
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
g
/ / p r i v a t e m e m 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 ( int c o l )
f
/ / 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
g
/ / p r o g r a m m i n g a s s i g n m e n t
public :
/ / 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 ( int n )
f
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
g
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 ;
g;
#endif
Figure 3: f16 prog1 hint.h: C++ code to help you with Programming Assign-ment #1.
4
Figure 4: Sample output of the code shown in gure 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 N-Queens Problem. This is for N = 4.
6
Figure 6: Sample output of the code that computes all solutions to the N-Queens Problem. This is for N = 8.
7
Figure 7: Sample output of the code that computes all solutions to the N-Queens Problem. This is for N = 11.
8
