Answered: 7 > void output(const int a[], const…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

I'm stuck on this question and I don't know how I should be approaching this. What should I do?

Question:

------------------

Solving the N-Queens Problem

Main Function

Create a one-dimensional array of size n and seed it with -1 values. This represents an empty n x n chess board. Develop the problem with n=4, test the solution up to n=24. Note that the array index represents the row, and array value the column.

Print Function

Print the array where all -1 values are empty spots on the board and all values not equal to -1 represent the position of a queen.

isSafePosition

Test if a specific row/col position is safe for a queen relative to all previous rows (row-1). If placing a queen into this specific row/col position would be dangerous return false, else return true.

Solve

Use backtracking to provide a solution for the current board size. This is a recursive function which repeatedly tests different queen layouts until it ultimately finds a working solution.

Your implementation should be based off of the following design:

My code so far:

------------------

#include <iostream>

using namespace std;

void print(const int a[], const int &SIZE) {

for(int i=0; i<SIZE; i++){

for(int j = 0; j<SIZE;j++){

if (j == a[i]){

cout<<"Q";

}

else{

cout<<".";

}

cout<<endl;

}

bool isSafePosition(const int a[], const int &SIZE, int row, int col){

for(int i=0; i<SIZE; i++){

for(int j = i+1; j<SIZE; j++){

if(a[i] == a[j])

returnfalse;

if (row - 1 == col)

returnfalse;

}

returntrue;

}

bool solve(int a[], const int &SIZE, int row){

if(row == SIZE){

returntrue;

}

else if(row < SIZE){

for(int row = 0; row<4; row++){

for(int col = 0; col<4; col++)

cout<<"Check: "<<row<<" "<<col<<endl;

cout<<endl;

print()

}

int main(){

cout<<endl;

const int SIZE = 4;

int a[SIZE];

for(int i=0; i<SIZE; i++){a[i] = -1;}

solve(a, SIZE, 0);

cout<<endl;

return0;

}

7 > void output(const int a[], const int &SIZE) {=}
19
20 > bool isSafePosition(const int a[], const int &SIZE, int row, int col) {-}
41
42 > bool solve(int a[], const int &SIZE, int row) {=}
75
76 v int main() {
cout <« endl;
77
78
79
// create an array and populate it with -1 to represent an empty board
80
const int SIZE = 8;
81
int a[SIZE];
32
for(int i=0; i<$IZE; i++) { a[i] = -1; }
// solve the recursive problem
solve(a, SIZE, 0);
64
85
86
87
cout <« endl;
88
return 0;
89

Last login: Thu Mar 26 15:19:40 on ttyse00
srtev - X /var/folders/nr/094m7xqx66j4hc1v96cjbhwce00@gn/T/separate_compilation_p2 ; exit;
check: e e
check: 1 0
check: 1 1
check: 1 2
check: 2 0
check: 2 1
check: 2 2
check: 2 3
BACKTRACK TO ROW 1
check: 1 3
check: 2 e
check: 2 1
check: 3 0
check: 3 1
check: 3 2
check: 3 3
BACKTRACK TO ROW 2
check: 2 2
check: 2 3
BACKTRACK TO ROW 1

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 3 steps with 3 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions