C language n queen problem

C Language N queens problem

Introduce ： What is? N queens problem

• In chess , The queen is a very powerful unit , It can be centered on the position of the Queen's pawn , Horizontal and vertical and The slope is 1 and -1 Move in the direction of ,N The Queen's question refers to n * n On my chessboard n A queen , And make any two The queen is different , Different columns are not on the same slash .

I use the method of backtracking to solve this problem ：
With 4x4 Take the chessboard of ：
Let's take the position of the first column in the first row , This position does not conflict with the walking range of other queens , So we can put

	1	2	3	4
1	Q	q	q	q
2	q	q
3	q		q
4	q			q

The second row also starts from the first column , When you get to the first column , Conflict , Second column , Conflict , The third column does not conflict , Place the second queen

	1	2	3	4
1	Q	q	q	q
2	q	q	Q	q
3	q	q	q	q
4	q		q	q

The third line repeats the operation of the second line , But any column found will conflict , Therefore, you can't put , Let's go back to the second line , Place the queen in the next column

Then come to the third row. At this time, there is no conflict in the second column , You can put

	1	2	3	4
1	Q	q	q	q
2	q	q	q	Q
3	q	Q	q	q
4	q	q	q	q

We found that there was no alternative in the fourth line . The first attempt failed , Go back one level , No columns available , Go back to the next level , No columns available , Finally, return to the first line .

Second retry
Let's go back to the first step , This shows that we have no solution to choose the first column in the first row , So we shouldn't choose the first column in the first row , Let's try the second column , And so on

	1	2	3	4
1	q	Q	q	q
2		q	q
3		q		q
4		q

Code implementation, such as

#include <bits/stdc++.h>// Lazy use C++ Universal head of , Actually sum C No difference ,.C Change the file if it fails to compile C The head of the 
using namespace std;

bool attack(int *chess, int col, int row)
{
    
	for(int i = 0; i < row; ++i){
    
		if(chess[i] == col){
    // Vertical conflict 
			return true;
		}
		if(col - chess[i] == row - i || chess[i] - col == row - i){
    
		// Slash conflict 
			return true;
		}
	}
	return false;
}

int nqueen()
{
    
	int queens = 0;
	cin>>queens;
	int col = 0, cnt = 0, row = 0;
	int chess[9] = {
    -1};
	// The topic requirements are the most 9 A queen , Moreover, the compiler of the website does not allow the array length to be a variable .
	while(!(col == queens && row == 0)){
    
		if(!attack(chess,col,row)){
    // Judge that there is no conflict 
			chess[row++] = col;
			if(row == queens){
    // All queens have been prevented 
				++cnt;
				col = chess[--row];// Go back to the previous line to find a new solution 
				++col;
				while(col == queens){
    // If the previous line is the last one, go back up 
					if(queens == 1){
    
						col = queens;
						row = 0;
						break;
					}	
					chess[row--] = -1;
					col = chess[row];
					col++;
				}
			}
			else{
    
				col = 0;
			}
		}
		else{
    
            ++col;// In case of conflict, the next column 
            while(col == queens && row != 0){
    // If there are conflicts in the whole column, go back 
                chess[row--] = -1;
				col = chess[row];
                col++;
            }
        }
	}
	return cnt;
}

int main()
{
    
	int cnt = 0;
	cnt = nqueen();
	cout<<cnt;
	return 0;
}

above ！

I hope I can give you some help .
thank