September 18, 2014

Program Eight Queens Problem with esProc

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:

No comments:

Post a Comment