八皇后递归算法（Eight queens recursive algorithm）.doc

八皇后递归算法（Eight queens recursive algorithm） First, the purpose and content of the experiment Write a program to solve the eight queens problem: the 8 queens placed in 8 rows and 8 columns on the board, the queen can not eat any of the other 7 queens (Note: the queen can eat with her in the other pieces of the same row or column or on the same diagonal, the) and the results show in some way out. For example, when calculated following a solution, can output the following information to express the solution (the output of the coordinates of the location and the queen said put board state - the Queens board has placed a Q character, the other position for the + character). (1,1) (5,2) (8,3) (6,4) (3,5) () (7,6) (2,7) (4,8); Q + + + + + + + + + + + + Q + + + + + Q + + + + + + + + + + Q + Q + + + + + + + + Q + + + + + + + + + Q + + + + Q + + + + Two 、 design and structure of experiment program (1) by means of int, LineNum[9], bool, a[9], b[15], c[15], 4 arrays with global scopes are explained. Therein: LineNum[i] indicates the position where the queen of the column I is going to put (use only the column numbers 1 to 8); A[i] is true (I, =1, 2),... (8) indicates that the queen has not been put on line i; B[i] is true (I, =0, 1, 2),... (14) indicates that the queen has not been placed on the diagonal of the diagonal of the I (the diagonal line refers to the / diagonal line, and the sum of the ranks of the points on the diagonal is i+j as a constant); C[i] is true (i=0, 1, 2),... (14) indicates that the queen has not been placed on the skew diagonal of section I (the skew diagonal refers to the ` ` diagonal line, and the difference between the row and column at each point on the diagonal is a constant I-J). So when using the statement if (a[j] b[i+j-2] LineNum[i]=j; c[i-j+7]), which can be used to determine and implement safety: if placed queen in column I line j on it, will be a queen placed there. (2) compile a recursive function solve with the following prototype, which