bFact = 1: FOR i = 1 TO B: bFact = bFact * i: NEXT
DIM Q(16) AS LONG
FOR i = 0 TO B: Q(i) = i: NEXT ‘initial permutation
FOR n = 1 TO bFact – 1
‘permutations guarantee queens are on unique rows and columns
‘we only need to check diagonals
ok = 1
FOR i = 0 TO B – 2: FOR j = i + 1 TO B – 1
IF ABS(Q(j) – Q(i)) = j – i THEN ok = 0
‘print the permutation if it is a solution
IF ok = 1 THEN
s = s + 1
COLOR 7, 0: LOCATE 1, 1: PRINT “Solution: “; s
FOR y = 0 TO B – 1: FOR x = 0 TO B – 1
COLOR 14, 6 + ((x + y) MOD 2)
IF Q(y) = x THEN PRINT ” Q “; ELSE PRINT ” “;
NEXT: PRINT: NEXT
‘advance to the next permutation
i = B – 1: WHILE Q(i – 1) > Q(i): i = i – 1: WEND: mLo = i – 1
i = B – 1: WHILE Q(i) < Q(mLo): i = i – 1: WEND: mHi = i
k = Q(mLo): Q(mLo) = Q(mHi): Q(mHi) = k
i = mLo + 1: j = B – 1
WHILE i < j
k = Q(i): Q(i) = Q(j): Q(j) = k
i = i + 1: j = j – 1
The next obvious task is to find a solution to the general case, given any N>3.
I have found that some solutions create a pattern on the board which could be extended into solutions over larger boards.
For example, for even values of N, there is this very simple pattern of queens placed in two lines of “knights moves”. There is an exception however – it only works for N congruent to 0 or 4 mod 6, and not for 2 mod 6:
The pattern doesn’t work for N congruent to 2 mod 6, because of a diagonal clash between the two lines, as is discovered in the original N=8 problem.
It is seen that queens placed in a line of “knights moves” occupy a diagonal every three diagonals, and that a second such line will stand in opposition to the first line in 1 out of 3 even-sized boards, which is where my “mod 6” comes from.
However, with a small tweak to the pattern, I found it could be salvaged:
For odd N, a similar line pattern was found by swapping the two lines around, but this only works for N congruent to 1 or 5 mod 6. (The diagonals present the same problem in the 3 mod 6 case):
This leaves only the class N congruent to 3 mod 6, which caused me some head-scratching. But with a tweak similar to the 2 mod 6 case, albeit a little more complex, a working pattern was found:
So this provides a solution to all NxN boards, except for the two impossible cases (N=2 and N=3).