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
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
#include
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 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< } (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 } } }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started