Shulou(Shulou.com)06/01 Report--

This article mainly explains "how to use C language to solve the problem of eight queens". The content of the explanation in the article is simple and clear, and it is easy to learn and understand. let's study and learn how to use C language to solve the problem of eight queens.

Preface

The problem of eight queens is an ancient and famous problem. This problem was put forward by Gauss, a famous mathematician in the 19th century, in 1850: on an 880 chess board, there were eight queens, each occupying a grid, requiring that queens would not "attack" each other, that is, there could not be two queens in the same row, column or diagonal. How many different methods are there?

Backtracking algorithm, also known as heuristic, is a method of searching for the solution of a problem. The basic idea of tracing algorithm is to search the solution space tree from the root node in a solution space tree containing all solutions according to the depth-first strategy. When searching for any node of the solution space tree, the algorithm always judges whether the node definitely does not contain the solution of the problem. If definitely not, the systematic search for the subtree rooted at the node is skipped and traced 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 the solutions to the problem, it should be traced back to the root, and all the subtrees of the root node have been searched before the end.

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

The backtracking algorithm of the eight queens problem can be processed by an one-dimensional array. The subscript I of the array represents column I on the chessboard, and the value of a [I] indicates the position of the queen in column I. For example, a [1] = 5 means to put a queen in the fifth row of the chessboard. In the program, it is assumed that a [1] = 1, which means that the first queen is placed on the first row of the first column of the chessboard, and then try to find out the possible position of the queen in the second column, and then deal with the subsequent columns after finding the appropriate position. in this way, through the repeated exploration of each column, we can finally find out the whole placement method of the queen.

The eight queens problem can be solved by backtracking method, and the program is as follows:

# include#define Queens 8 / / defines the size of the result array, that is, the number of queens int a [Queens+1]; / / the position of queens in the row of eight queens, counting from 1 to 1, so add 1int main () {int I, k, flag, not_finish=1, count=0;// to the element subscript being processed, indicating that the former iLue 1 element has met the requirements, and is processing the I th element. / / assign the initial value printf to the first element of the array ("the possible configuration of the eight queens is:\ n"); while (not_finish) {/ / not_finish=l: processing is not finished while (not_finish & & I)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.