Among lots of chess puzzles, the problem of the eight queens is the most well-known example. Eight queens must be placed on a 8×8 chessboard so that no queen attacks any others. Well, how many solutions are there?
A queen attacks any other queen that sits on the same row, column or diagonal. Thus a solution requires that no two queens share the same row, column or diagonal.
Since there is only one queen in each row, a sequence, the length of which is 8, can be employed to set in turn the sequence number of the column on which a queen on each row sits. For a row on which no queen has been placed, the column number is zero; every time when we put a new queen on the board, if the sequence number of the column is not one of the existing members of the sequence, then no other queen sits on the same column.
At the same time, we need to make sure there is no other queen on a diagonal when we place a new queen on it. If the queen sits on row m of column k, there are two squares at most on row m+n that share the same diagonal with it; and the horizontal distance between either of the squares and the queen equals the vertical distance between them. This means there are two squares (m+n,k+n) and (m+n,k-n) at most share the same diagonal with it.
So, we will know the number of solutions by looking at all squares of a row on which a queen is placed.
esProc does this by performing loop operation, as shown below:
| A | B | C | D | |
| 1 | =[0]*8 | >i=1 | ||
| 2 | for i>0 | >A1(i)=A1(i)+1 | ||
| 3 | if A1(i)==9 | >A1(i)=0,i=i-1 | next | |
| 4 | if i==1 | >i=2 | next | |
| 5 | =A1(i) | =A1.to(i-1) | ||
| 6 | if C5.pos(B5)>0 | next | ||
| 7 | else if C5.pselect(i-#==abs(B5-~))>0 | next | ||
| 8 | >i=i+1 | |||
| 9 | if i==9 | >C1=C1|A1.conj@s() | >A1(8)=0,i=7 | |
| 10 | =C1.len() |
i is used during the computation to represent the sequence number of the current row where a queen is placed. The code in the 2nd line executes loops, in which after each loop the queen on the current row will move to the next column. In this way, every square of the current row is traversed. About the code in the 3rd line: When the queen moves to the 9th column, the traversal of all squares in the current row has completed; at this point, reset the sequence number of column for traversing through the row to zero and subtract 1 from i and begin loop on the next row. In particular, when all the squares of the first row are looped through, the entire traversal is completed. Now i is reset to zero and the loop exits. About the code in the 4th line: when moving the queen along the first row, there is no need to judge if a square is eligible for holding a queen; just place the second queen. The code in the 6th line judges if there is any column shared by the settled queens, and the code in the 7th line judges whether there is any diagonal shared by them. If results of both judgments are true, we can go on to place the queen on the next row. When all the eight queens are settled, store their current places with the code in the 9th line.
The computed result in A10 is:
We can see detailed result in C1:
We can also solve the problem by recursively calling a subroutine:
| A | B | C | D | E | |
| 1 | =[0]*8 | >func(A2,A1,1) | =C1.len() | ||
| 2 | func | =A2.to(B2-1) | |||
| 3 | for 8 | if C2.pos(B3)>0 | next | ||
| 4 | if B2==1 | >A2(B2)=B3 | |||
| 5 | >func(A2,A2,B2+1) | next | |||
| 6 | for C2 | if B2-#C6==abs(C6-B3) | next B3 | ||
| 7 | >A2(B2)=B3 | ||||
| 8 | if B2==8 | >C1=C1|A2.conj@s() | |||
| 9 | else | >func(A2,A2,B2+1) |
In A2’s subroutine, a queen is placed on a row. B3 loops through every possible column. C3 judges if there is already a queen on the current column. The 6th line judges if a queen already exists on the diagonals, and if it exists, try next column. If a certain column is eligible, then call the subroutine recursively and move on to the next row to place the queen. Store places of the eight queens in C1 after they are all settled. This approach produces the same result but easier code.