85 lines
2.0 KiB
Plaintext
85 lines
2.0 KiB
Plaintext
'N queens
|
|
'>10 would not work due to way permutations used
|
|
'anyway, 10 doesn't fit in memory
|
|
Input "Input N for N queens puzzle (4..9) ";N
|
|
if N<4 or N>9 then print "N out of range - quitting": end
|
|
|
|
ABC$= " "
|
|
dash$ = ""
|
|
for i = 0 to N-1
|
|
ABC$=ABC$+" "+chr$(asc("a")+i)
|
|
dash$ = dash$+"--"
|
|
next
|
|
|
|
dim q(N)
|
|
t0=time$("ms")
|
|
|
|
fact = 1
|
|
for i = 1 to N
|
|
fact = fact*i
|
|
next
|
|
|
|
dim anagram$(fact)
|
|
global nPerms
|
|
print "Filling permutations array"
|
|
t0=time$("ms")
|
|
res$=permutation$("", left$("0123456789", N))
|
|
t1=time$("ms")
|
|
print "Created all possible permutations ";t1-t0
|
|
|
|
t0=time$("ms")
|
|
'actually fact = nPerms
|
|
for k=1 to nPerms
|
|
for i=0 to N-1
|
|
q(i)=val(mid$(anagram$(k),i+1,1))
|
|
'print q(i);
|
|
next
|
|
'print
|
|
|
|
fail = 0
|
|
for i=0 to N-1
|
|
for j=i+1 to N-1
|
|
'check rows are different
|
|
if q(i)=q(j) then fail = 1: exit for
|
|
'check diagonals are different
|
|
if i+q(i)=j+q(j) then fail = 1: exit for
|
|
'check other diagonals are different
|
|
if i-q(i)=j-q(j) then fail = 1: exit for
|
|
next
|
|
if fail then exit for
|
|
next
|
|
|
|
if not(fail) then
|
|
num=num+1
|
|
print " ";dash$
|
|
for i=0 to N-1
|
|
print N-i; space$(2*q(i));" *"
|
|
next
|
|
print " ";dash$
|
|
print ABC$
|
|
end if
|
|
|
|
next
|
|
|
|
t1=time$("ms")
|
|
print "Time taken ";t1-t0
|
|
print "Number of solutions ";num
|
|
|
|
'----------------------------------
|
|
'from
|
|
'http://babek.info/libertybasicfiles/lbnews/nl124/wordgames.htm
|
|
'Programming a Word Game by Janet Terra,
|
|
'The Liberty Basic Newsletter - Issue #124 - September 2004
|
|
Function permutation$(pre$, post$)
|
|
'Note the variable nPerms must first be stated as a global variable.
|
|
lgth = Len(post$)
|
|
If lgth < 2 Then
|
|
nPerms = nPerms + 1
|
|
anagram$(nPerms) = pre$;post$
|
|
Else
|
|
For i = 1 To lgth
|
|
tmp$=permutation$(pre$+Mid$(post$,i,1),Left$(post$,i-1)+Right$(post$,lgth-i))
|
|
Next i
|
|
End If
|
|
End Function
|