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

}

}

}