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:
- 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).
- 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:
- 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.
- 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 If you need help with this
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}.
// N Queens Problem via ( Backtracking , which is implemented by ) Recursion
// Written by Prof . Sreenivas for IE523 : Financial Computing
#include <iostream>
#include ”N queens .h”
int main ( int argc , char ∗ const argv [ ] )
{ Board x ;
int board size ; sscanf ( argv [1] , ”%d” , &board size );
x . nQueens( board size );
return 0;
}
Figure 2: f16 prog1 hint.cpp: C++ code to help you with Programming Assign-
part, you might want to see the handout “Programming Assignment 5: Dynamic Arrays in C++” in the Bootcamp folder on Compass.
- 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.
- 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
- 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.
#ifndef N queens
#define N queens using namespace std ;
class Board
{
// p r i v a t e data member : s i z e o f t h e board int size ;
// p o i n t e r −to−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 board int ∗∗chess board ;
// p r i v a t e member 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 not s a f e . bool is this position safe (int row , int col )
{
// w r i t e t h e a p p r o p r i a t e code on your 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 . some o t h e r queen can | 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 | member | 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 initialize (int n)
{
size = n;
// w r i t e t h e a p p r o p r i a t e code t h a t u s e s t h e p o i n t e r −to−p o i n t e r
// method to 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 . Once i n i t i a l i z e d , // put z e r o s in a l l e n t r i e s . L a t e r on , i f you p l a c e d a queen in // t h e ( i , j )− th p o s i t i o n , then c h e s s b o a r d [ i ] [ j ] w i l l be 1 .
}
// p r i v a t e member f u n c t i o n : p r i n t s t h e board p o s i t i o n void print board ()
{
std :: cout << size << ”−Queens Problem Solution” << std :: endl ;
// w r i t e t h e a p p r o p r i a t e code here to p r i n t out t h e s o l v e d
// board as shown in 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 member 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 solve (int col ) {
// implement 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 in
// p s e u d o c o d e format in 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
// programming a s s i g n m e n t }
public :
// S o l v e s t h e n−Queens problem by ( 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)
{ initialize (n);
if ( solve (0)) print board ();
else
std :: cout << ”There is no solution to the ” << n << ”−QueensProblem” << std :: endl ;
}
};
#endif
Figure 3: f16 prog1 hint.h: C++ code to help you with Programming Assign-
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.
Figure 5: Sample output of the code that computes all solutions to the NQueens Problem. This is for N = 4.
Figure 6: Sample output of the code that computes all solutions to the NQueens Problem. This is for N = 8.
Figure 7: Sample output of the code that computes all solutions to the NQueens Problem. This is for N = 11.
