Someone who can help me has to enter the first queen to me. It\'s in the c ++ pr

Question

Someone who can help me has to enter the first queen to me. It's in the c ++ program

7.26 (Eight Queens) Another puzzler for chess buffs is the Eight Queens problem. Simply stated: Is it possible to place eight queens on an empty chessboard so that no queen is attacking any other, i.e., no two queens are in the same row, the same column, or along the same diagonal? Use the think ing developed in Exercise 7.24 to formulate a heuristic for solving the Eight Queens problem. Run 342 Chapter 7 Arrays and Vectors your program. (Hint It's possible to assign a value to each square ofthe chessboard indicating how many squares of an empty chessboard are eliminated if a queen is placed in that square. Each of the corners would be assigned the value 22, as in Fig. 7.29. Once these "elimination numbers" are placed in all 64 squares, an appropriate heuristic might be: Place the next queen in the square with the smallest elimination number. Why is this strategy intuitively appealing Fig. 7.29 The 22 squares eliminated by placing a queen in the upper-left corner.

Explanation / Answer

#include <iostream>
#include<stdio.h>
#include<string.h>
#define N 8

using namespace std;

void printQueenSolution(int board[N][N]);
bool isSafe(int row, int col, int crossCode[N][N],
int backcrossCode[N][N], bool rowLookup[],
bool crossCodeLookup[], bool backcrossCodeLookup[] );

// Solve Queens problem recursively
bool solveQueensUtil(int board[N][N], int col,
int crossCode[N][N], int backcrossCode[N][N], bool rowLookup[N],
bool crossCodeLookup[], bool backcrossCodeLookup[] )
{
if (col >= N)
return true;

for (int i = 0; i < N; i++)
{
if ( isSafe(i, col, crossCode, backcrossCode, rowLookup,
crossCodeLookup, backcrossCodeLookup) )
{
board[i][col] = 1;
rowLookup[i] = true;
crossCodeLookup[crossCode[i][col]] = true;
backcrossCodeLookup[backcrossCode[i][col]] = true;

if ( solveQueensUtil(board, col + 1, crossCode, backcrossCode,
rowLookup, crossCodeLookup, backcrossCodeLookup) )
return true;

board[i][col] = 0;
rowLookup[i] = false;
crossCodeLookup[crossCode[i][col]] = false;
backcrossCodeLookup[backcrossCode[i][col]] = false;
}
}

return false;
}

bool solveQueens()
{
int board[N][N];
   for(int i = 0; i < N; i++)
       for(int j = 0; j < N; j++)
           board[i][j] = 0;

int crossCode[N][N];
int backcrossCode[N][N];
bool rowLookup[N] = {false};
bool crossCodeLookup[2*N - 1] = {false};
bool backcrossCodeLookup[2*N - 1] = {false};

for (int r = 0; r < N; r++)
for (int c = 0; c < N; c++)
       {
crossCode[r][c] = r + c,
backcrossCode[r][c] = r - c + 7;
       }

if (solveQueensUtil(board, 0, crossCode, backcrossCode,
rowLookup, crossCodeLookup, backcrossCodeLookup) == false )
{
printf("Solution does not exist");
return false;
}
printQueenSolution(board);
return true;
}

int main()
{
solveQueens();
return 0;
}

bool isSafe(int row, int col, int crossCode[N][N],
int backcrossCode[N][N], bool rowLookup[],
bool crossCodeLookup[], bool backcrossCodeLookup[] )
{
if (crossCodeLookup[crossCode[row][col]] ||
backcrossCodeLookup[backcrossCode[row][col]] ||
rowLookup[row])
return false;

return true;
}

void printQueenSolution(int board[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
cout << board[i][j] << " ";
cout << endl;
}
}

// sample run

1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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