Eight queens problem: suppose you put eight queens on a chess board so that the two cannot attack each other. How many pendulum methods are there?

Basic knowledge:

In chess, the board is 8X8.

The queen can walk in any grid along the straight line or oblique line.

Train of thought:

1. if you want to put 8 queens in it, there must be only one queen in each row and one queen in each column.

2. Set a two-dimensional array chess [i] [J] to simulate the chessboard, and cas stores the pendulum method. i j is row I and column J:

Write a function for recursion, as follows

3. Put the queen from the top to the bottom row. When you put down a row, put it from the leftmost (column 0). If you can't put it, move it to the right and try again. Pay attention to judge whether there is a checkerboard crossing the border on the right.

4. Write a function to judge whether the current position can be put. Just judge the horizontal, vertical and two diagonal lines of the position, and whether there are other queens on these four lines.

5. If you have finished the last line, count this pendulum, cas + +. You can't judge the next line after the last line.

6. After playing one situation, we need to explore other situations. You can "take away" the queen who is now in place, and then try to explore the chessboard that has not been tested before.

Here is the recursive function section:

void queen(int i,int j){　　
    if(j>=line){　　//If the right side is out of bounds
    return ;
    }

    if(check(i,j)==1){//If it can be released
    chess[i][j]=1;//Empress the queen
        if(i==line-1){//If it's the last line, record the situation
        cas++;
        }
        else{
        queen(i+1,0);//It's not the last line. It's the next line
        }
    }

    chess[i][j]=0;//If this position cannot be placed, leave it blank (0) to judge the next grid.
    //If this position can be put, walking here means that all the above codes have been executed. Take the queen away (set to zero), discuss other situations, and take the next position to test.
    queen(i,j+1);

}

(to be continued, to be written tomorrow)

#include<stdio.h>
#define line 8
void queen(int i,int j);
int check(int i,int j);

int queennumber=8;
int chess[line][line];
int cas=0;

int main(){
queen(0,0);
printf("%d\n",cas);
return 0;
}

void queen(int i,int j){
    if(j>=line){
    return ;
    }

    if(check(i,j)==1){//If it can be released
    chess[i][j]=1;//Empress the queen
        if(i==line-1){//If it's the last line, record the situation
        cas++;
        }
        else{
        queen(i+1,0);//It's not the last line. It's the next line
        }
    }

    chess[i][j]=0;//If this position cannot be placed, leave it blank (0) to judge the next grid.
    //If this position can be put, walking here means that all the above codes have been executed. Take the queen away (set to zero), discuss other situations, and take the next position to test.
    queen(i,j+1);

}


int check(int i,int j){
int k;

    for(k=0;k<line;k++){
    if(chess[i][k]==1) return 0;//0=Cannot put
    }
    for(k=0;k<line;k++){
    if(chess[k][j]==1) return 0;
    }
    for(k=-line;k<=line;k++){//Two diagonal line
    if(i+k>=0&&i+k<line&&j+k>=0&&j+k<line)//Two four quadrant diagonal
        if(chess[i+k][j+k]==1) return 0;
    
    if(i-k>=0&&i-k<line&&j+k>=0&&j+k<line)//One three quadrant diagonal
        if(chess[i-k][j+k]==1) return 0;
    }
    return 1;
}