

Solve the eight queens puzzle.



You can extend the problem to solve the puzzle with a board of size   NxN.

For the number of solutions for small values of   N,   see   OEIS: A000170.



Related tasks

 A* search algorithm
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Knight's tour
 Peaceful chess queen armies
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


 
'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
 
 