The Eight Queens Puzzle is a famous mathematical game. As shown in the following
ID: 3735339 • 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.
(1) The following program is a recursive solution. Fill out the numbered blanks in the program 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 ==___1___|| queen[i] - c ==___2___) return false; //check the left-front and right-front
}
return ___3___;
}
void search(int r){ //search the solution at the r-th row
if(r > 8){
ans++;
return;
}
for(int i = 1; i<=8; i++){ //search every column
if(check(r, i)){
queen[r] = ___4___;
search(r+1); //search next row
queen[r] = ___5___; //backtrack
}
}
}
int main(){
search(1); //start from the first row
cout<<ans<<endl;
}
(2) 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.
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 ___6___ {
queen[r] = c; //find a solution at c-th column
flag = ___7___;
break; //jump out and search next row
}
}
if (flag == 0){ //no solution at this row
queen[r] = ___8___;
___9___; //backtrack to last row
if (r==0) break; //back to 0-th row, all the solutions are found
}
else {
if (r == ___10___) ans++; //find an answer for the chess board
else r++; //search next row
}
}
}
Explanation / Answer
#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)
{ //search the solution at the r-th row
if (r > 8)
{
ans++;
return;
}
for (int i = 1; i <= 8; i++)
{ //search every column
if (check(r, i))
{
queen[r] = i;
search(r + 1); //search next row
queen[r] = 0; //backtrack
}
}
}
int main()
{
search(1); //start from the first row
cout << ans << endl;
}
output: 92
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.