RaqForum 80 No.
1 Reply  •  28 View  • 
     ...

Eight Queens

 
calculate(9)

The Eight Queens problem is a classic and well-known problem. Specifically, place eight queens on an 8x8 chessboard so that no two queens can attack each other, which means no two queens can be on the same row, the same column, or the same diagonal. The question is: how many solutions are there?

A

B

C

D

1

8

=[0]*A1

>i=1

2

for i>0

>B1(i)+=1

3

if B1(i)>A1

>B1(i)=0,i-=1

next

4

if i==1 && A1>1

>i=2

next

5

=B1(i)

=B1.to(i-1)

6

if C5.pselect(~==B5|| i-# ==abs(B5-~))

next

7

if (i+=1)>A1

=@|B1.concat@c()

>i-=1

8

=C7.len()


Consider each row of an N*N chessboard as a sequence. Number the cells in each column sequentially from 1 to N. Each queen must be placed in a unique row, with one queen per row. A1 specifies the number of queens, N, to be placed. A2 initializes the position of the queen in each row to 0. C1 defines the index of the current row being checked, i, starting from row 1.

A2 starts executing a loop, which terminates when the row index i is not greater than 0. B2 moves the queen in the current row to the next position. B3 determines if the column position of the queen in the current row is greater than N; if so, it indicates all positions in the current row have been tried. In this case, remove the queen in the current row, and return to the previous row to continue adjusting the queen’s position. In line 4, for the case of only one row, there’s no need to check for validity; proceed directly to placing the queen on the second row. If N is 1, then directly proceed to the subsequent checks.

A5 obtains the position of the queen in the current row. C5 obtains the positions of the queens in all preceding rows.

B6 determines if the current queen is on the same column or diagonal as any previously placed queen; if so, it is invalid. In this case, proceed to determine the next position.

If the current queen’s position is not in conflict with any previously placed queens, then increment the row index i in B7, and determine if all queens have been placed correctly. If so, record the positions of all queens in C7 and continue to check if there is other valid position; otherwise, start placing the next queen. In SPL, using A.concat@c() can concatenate the members of a sequence to a comma-separated string.

Once the loop ends, all possible solutions can be seen in C7.

..

The total number of members in C7 sequence is the number of solutions. If there is no solution, then both C7 and A8 will contain null values.

..

It is also possible to recursively call a subroutine to attempt to place the queen in the next row:

A

B

C

D

1

8

[]

>queen([0]*A1,1)

=A1.len()

2



3

func queen(a,r)

if r>A1

>B1|=a.concat@c()

return

4

for A1

if r>1 && a.to(r-1).pselect(~==B4 || r-#==abs(B4-~))

next

5

>a(r)=B4

>queen(a,r+1)

A3 defines a subroutine queen(a, r), where the sequence a records the positions of every queen, and r represents the row where the queen is currently placed. B3 determines if all queens have been placed correctly. If true, record the current solution in B1 and return. B4 loops through each column in the current row. C4 determines if the current position is on the same column or diagonal as any queen already placed in previous rows; if so, it indicates the current position is invalid, and the next position is checked. If the current queen’s position is valid, record this position in a, and proceed to place the queen in the next row.

C1 calls a subroutine to begin placing queens starting with the first row. After execution, the placement results can be obtained in B1, and the total number of solutions can be obtained in D1.

In SPL, subroutines can be called recursively, making the code written in this way more concise and easier to read.


calculate(9)
 
 •  28 View  •