BFS: eight queens problem

Reprinted from C language Chinese website, only for easy viewing
http://c.biancheng.net/cpp/html/2799.html
The eight queens problem is an ancient and famous problem. The problem was put forward by the famous mathematician Gauss in the 19th century in 1850: on an 8 * 8 chess board, there are eight queens, each of which occupies one grid; It is required that there will be no mutual "attack" between queens, that is, there can be no two queens in the same row, column or diagonal. How many different methods are there?

Backtracking algorithm is also called heuristic method. It is a method to search the solution of the problem. The basic idea of backtracking algorithm is to search the solution space tree from the root node according to the depth first strategy in a solution space tree containing all solutions. When the algorithm searches any node of the solution space tree, it always judges whether the node does not contain the solution of the problem. If it is definitely not included, skip the system search of the subtree with this node as the root, and trace back to its ancestor node layer by layer. Otherwise, enter the subtree and continue to search according to the depth first strategy. When the backtracking method is used to find all solutions of the problem, it needs to backtrack to the root, and all subtrees of the root node have been searched.

There are many solutions to the eight queens problem, among which the backtracking method is one. Backtracking is also the most direct solution, which is easier to understand.

The backtracking algorithm of the eight queens problem can be processed by one-dimensional array. The subscript i of the array represents the ith column on the chessboard, and the value of a[i] represents the position of the queen in the ith column (I = column, a[i] = row). For example, a[1]=5 means that a queen is placed in the fifth row of the first column of the chessboard. In the program, first assume a[1]=1, which means that the first queen is placed on the first row of the first column of the chessboard, and then test the possible position of the queen in the second column. After finding the appropriate position, deal with the subsequent columns. In this way, through the repeated test of each column, we can finally find out all the placement methods of the queen.

The eight queens problem can be solved by backtracking method. The program is as follows:

#include<stdio.h>

#define Queens 8 / / defines the size of the result array, that is, the number of queens

int a[Queens+1];    //The position of the queen of the eight queens problem is calculated from 1, so add 1

int main(){
    int i, k, flag, not_finish=1, count=0;
    //The subscript of the element being processed indicates that the first i-1 elements have met the requirements and the ith element is being processed
    i=1;
    a[1]=1;  //Initial the first element of the array

    printf("The possible configuration of 8 queens are:\n");

    while(not_finish){  //not_finish=l: the process has not ended
        while(not_finish && i<=Queens){  //The processing has not ended and has not been processed to the Queens element
            for(flag=1,k=1; flag && k<i; k++) //Judge whether there are multiple queens in the same row / / * initial k=1, that is, start from the first column
            //a[k] indicates which row the queen of that column is in. Now you use K to cycle from 1 to i-1 to see if the queen in front of I will repeat with the ith row. If the queen of column K goes with the queen of column I, it is a[k]==a[i]

                if(a[k]==a[i])
                    flag=0;//Once there is the same loop, it ends, so the flag in the condition is equivalent to if(flag==0)break;

            for (k=1; flag&&k<i; k++)  //Determine whether there are multiple queens on the same diagonal
                if( (a[i]==a[k]-(k-i)) || (a[i]==a[k]+(k-i)) )
                    flag=0;

            if(!flag){  //If there are contradictions and the requirements are not met, the ith element needs to be reset
                if(a[i]==a[i-1]){  //If the value of a[i] has caught up with the value of a[i-1] after a circle
                    i--;  //Go back one step and rehash the previous element

                    if(i>1 && a[i]==Queens)
                        a[i]=1;  //When a[i] is Queens, set the value of a[i] to 1
                    else
                        if(i==1 && a[i]==Queens)
                            not_finish=0;  //Ends when the value of the first digit reaches Queens
                        else
                            a[i]++;  //Take a[il the next value
                }else if(a[i] == Queens)
                    a[i]=1;
                else
                    a[i]++;  //Take the value of a[i] to the next value
            }else if(++i<=Queens)
                if(a[i-1] == Queens )
                    a[i]=1;  //If the value of the previous element is Queens, then a[i]=l
                else
                    a[i] = a[i-1]+1;  //Otherwise, the value of the element is the next value of the previous element
        }

        if(not_finish){
            ++count;
            printf((count-1)%3 ? "\t[%2d]:" : "\n[%2d]:", count);

            for(k=1; k<=Queens; k++) //Output results
                printf(" %d", a[k]);
            
            if(a[Queens-1]<Queens )
                a[Queens-1]++;  //Modify the value of the penultimate digit
            else
                a[Queens-1]=1;

            i=Queens -1;    //Start looking for the next solution that meets the conditions
        }
    }
}

Posted by lenerd3000 on Thu, 05 May 2022 07:33:39 +0300