problem must be solved using the general type of algorithm described below. Spec

Question

problem must be solved using the general type of algorithm described below. Specific steps may be modified where indicated. If you'd like to pursue a method that isn't discussed below, you wit This h me beforehand to get it cleared (including that you demonstrate that your algorithm satisfies the objectives of this programming assignment). Algorithm Begin the code using a variable that defines the board size- we want our code to be flexible enough to handle boards ranging in size from 4x4 up to NxN. Based on this variable, create a "board" by initializing a matrix that is size NxN using the 'zeros' command. te code that will randomly place N queens on the board. Use the number '1' to indicate a pace on the board that contains a queen. If you have a 4x4 board, your matrix should now contain four entries that are a 1' - these represent your queens. The remaining entries in the matrix should still be zeros. Note: This 'random' placement is one area of the code that you are allowed to modify. If you truly allow your code to randomly place the queens, it might take a long time to find a solution (especially for large N); the benefit of simple random placement is that the code for the placement of the queens will be much easier to write. Examples of modifications that you can make to the code that will "guide" the placement of queens: i. ii. ili. Only allow 1 queen to be placed in each row Only allow 1 queen to be place in each column After the placement of any single queen, you may also mark off any spaces that she attacks as being unfit for future placement. iv. (Note: If you program too many restrictions, then your code may not be able to finish placing queens on the board. If you find yourself in this situation, your code must be able to recognize what has happened and should then re-set the board to all zeros and start the placement process once again.) If you haven't implemented an attack procedure as part of the above restrictions, your code will now have to go through an attack procedure (and even if you did, you may still have to do this 3. step depending on the "completeness" of your attack procedure). That is, once you have a board that has N queens placed on it, you have to evaluate whether any queen threatens another occupied position on the board. Write code that iterates through your matrix and looks for a queen (i.e, a 1', then have that queen 'attack in all possible directions. To do this, change all positions that she is capable of threatening into an .8, (in other words, all other entries in her row, column, and in both diagonals will become an '8') Note: If another queen was in the way, this attack sequence just eliminated her from the board. You can stop that particular solution there, or... a. After executing the attack sequence for every queen on the board, count how many are remaining. If you still have N queens, you've found a solution-congratulations! If you have less than N queens on the board, re-set the board (turn it to all zeros) and go back to step 2. 4. Your code should be able to run for any size of N greater than or equal to 4. However, I would highly recommend that you initially program/debug with a small N to save computational time

Explanation / Answer

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define NQ 4
using namespace std;
int solveNQ(int board[NQ][NQ],int);
void print(int board[NQ][NQ]);
int safe(int board[NQ][NQ],int,int);
int main()
{
int board[NQ][NQ] = {0};
if (solveNQ(board, 0) == 0)
{
cout<<"Solution does not exist"<<endl;
return 0;
}
print(board);
return 1;
}
/*UTILITY FUNCTION to solve N Queen problem */
int solveNQ(int board[NQ][NQ],int COL)
{
if (COL>=NQ)
return 1;
for (int i=0;i<NQ;i++)
{
if ( safe(board, i, COL) )
{
board[i][COL] = 1;
if (solveNQ(board, COL + 1) == 1)
return 1;
board[i][COL] = 0;
}
}
return 0;
}
/* check if a queen can be placed on board[ROW][COL]*/
int safe(int board[NQ][NQ], int ROW, int COL)
{
int i, j;
for (i = 0; i < COL; i++)
{
if (board[ROW][i])
return 0;
}
for (i = ROW, j = COL; i >= 0 && j >= 0; i--, j--)
{
if (board[i][j])
return 0;
}

for (i = ROW, j = COL; j >= 0 && i < NQ; i++, j--)
{
if (board[i][j])
return 0;
}

return 1;
}
/* print board */
void print(int board[NQ][NQ])
{
for (int i = 0; i < NQ; i++)
{
for (int j = 0; j < NQ; j++)
cout<<board[i][j]<<" ";
cout<<endl;
}
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.