There are quite a lot of chess problems, among
which the Eight Queens Problem is the most famous one. Put eight Queens in a 8×8 chessboard, the requirement is no attack between any of them. How
many layouts are there to achieve this?
As a Queen's striking range is limited to a row, a
column and an oblique line, only one Queen is allowed to appear in a single
line, otherwise it is ineligible.
Since there is only one Queen in any single line, a
sequence, 8 in length, could be employed. Set in turn the column number
a Queen in each row is located. If there is not a Queen in a certain row, mark
with zero; when we place a new Queen in the board, and the column number is not
within the sequence, which means there is no Queen in this column.
At the same time, we also need to make sure the new
Queen has no counterpart in the diagonal. If a Queen is located in row m of column
k, there are two places at most in row m+n of the same oblique line. Between the two places and the
Queen, the horizontal distance is equal to the vertical distance, which means
there are at most two places (m+n,k+n) and (m+n,k-n) are
in the same oblique line with the Queen.
So, we would know the number of eligible conditions
after examining status of each Queen in every line.
esProc can do all the work with loop computation,
as shown in the following form:
i is employed during the computation to record the serial number of the
current row where a Queen is placed. The code in the 2nd line of the above form
shows that with each loop of the code, the Queen will move to the next column,
and in this way, traversal of every place of the current row will be completed.
For the code in the 3rd line, when the Queen move to the 9th column, its
traversal in all places in the current row has completed; the record of the
current row restores to zero and i equals i-1 and return to
continue with traversal in the last row. Here note that when the entire loop in
the first line is done, the traversal is completed, i will be reset as zero,
and the loop is over. For the code of in the 4th line, when moving the queen in
the first row, we could locate the second Queen without making any judgments.
The code of in the 6th line judges whether there is any located Queen in a same
column; and the code in the 7th line judges whether there is any located Queen
in a same oblique line. If the answers of both judgment are no, we could locate
the Queen in the next row. When all the eight Queens are located, record their
current places with the code in the 9th line.
The computed
result in A10 is:
Check detailed
result in C1:
没有评论:
发表评论