The Queens Puzzle in QBasic

[sorceress]

#2918

B = 8

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
NEXT: NEXT

‘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
SLEEP
END IF

‘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
WEND

NEXT

[Mgoddard]

#2922

I’ll just stick with running GORILLAS.BAS thanks 🙂

[sorceress]

#2925

In the mathematical spirit of the puzzle, we can determine the number of solutions for different board sizes. Consider placing N queens on an NxN board:

N _ # Solutions _ as a % of all possible permutations

1 _ 1 _ 100%
2 _ 0 _ 0%
3 _ 0_ 0%
4 _ 2 _ 8.33%
5 _ 10 _ 8.33%
6 _ 4 _ 0.56%
7 _ 40 _ 0.79%
8 _ 92 _ 0.23%
9 _ 352 _ 0.097%
10 _ 724 _ 0.020%
11 _ 2680 _ 0.0067%
12 _ 14200 _ 0.0030%
13 _ 73712 _ 0.0012%
14 _ 365596 _ 0.00042%
15 _ 2279184 _ 0.00017%

The percentages in some way reflect the difficulty of finding a solution to each puzzle grid.

[sorceress]

#2933

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).

[dr_st]

#2939

Awesome analysis! I love working generalization and complete problem solutions. 🙂

[evilcommiedictator]

#2952

Nice work Sorceress! Sadly I was on the knight spacing but couldn’t get it to work, then just stumbled onto the solution 🙁