The Eight Queens Puzzle is a famous mathematical game. As shown in the following
ID: 3735586 • Letter: T
Question
The Eight Queens Puzzle is a famous mathematical game. As shown in the following figure, you need to place 8 queens on a 8x8 chess board, such that every row, column and diagonal contains at most one queen. You need to design algorithms to answer how many solutions exist on this 8x8 chess board.
The following is a non-recursive version of the search fuction. Fill out the numbered blanks in the function and highlight your answer with the corresponding numbers.The Eight Queens Puzzle is a famous mathematical game. As shown in the following figure, you need to place 8 queens on a 8x8 chess board, such that every row, column and diagonal contains at most one queen. You need to design algorithms to answer how many solutions exist on this 8x8 chess board.
The following is a non-recursive version of the search fuction. Fill out the numbered blanks in the function and highlight your answer with the corresponding numbers.
#include <stdio.h>
#include <iostream>
using namespace std;
int ans = 0; //count the number of answers
int queen[10] = {0}; //queen at i-th row is put at queen[i]-th column
bool check(int r, int c)
{ //check whether it is appropriate to put a queen at (r, c)
for (int i = 1; i < r; i++)
{
if (queen[i] == c)
return false; //check the column
if (queen[i] - c == i-r || queen[i] - c == r - i)
return false; //check the left-front and right-front
}
return true;
}
void search(int r){
int flag; //to indicate whether a solution is exist at this row
while (r <= 8){
flag = 0;
for (int c=queen[r]+1; c<=8; c++){
if ___1___ {
queen[r] = c; //find a solution at c-th column
flag = ___2___;
break; //jump out and search next row
}
}
if (flag == 0){ //no solution at this row
queen[r] = ___3___;
___4___; //backtrack to last row
if (r==0) break; //back to 0-th row, all the solutions are found
}
else {
if (r == ___5___) ans++; //find an answer for the chess board
else r++; //search next row
}
}
}
int main(){
search(1); //start from the first row
cout<<ans<<endl;
}
Explanation / Answer
1. check(r,c) (finding a solution at c-th column)
2. TRUE (solution found, set to TRUE)
3. 0 (No solution found, set queen[r] to 0 for that row)
4. r--
5. 8
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.