

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


DOCU The N Queens Problem:
DOCU Place N Queens on an NxN chess board
DOCU such that they don't threaten each other.
 
N = 8 // try some other sizes
 
sub threat(q1r, q1c, q2r, q2c)
// do two queens threaten each other?
 
   if q1c = q2c then    return true
   elsif (q1r - q1c) = (q2r - q2c) then return true
   elsif (q1r + q1c) = (q2r + q2c) then return true
   elsif q1r = q2r then    return true
   else return false
   end if
end sub
 
sub conflict(r, c, queens$)
// Would square p cause a conflict with other queens on board so far?
   local r2, c2
 
   for i = 1 to len(queens$) step 2
       r2 = val(mid$(queens$,i,1))
       c2 = val(mid$(queens$,i+1,1))
       if threat(r, c, r2, c2) then
            return true
       end if
    next i
   return false
end sub
 
sub print_board(queens$)
// print a solution, showing the Queens on the board
   local k$
 
   print at(1, 1);
   print "Solution #", soln, "\n\n   ";
   for c = asc("a") to (asc("a") + N - 1)
        print chr$(c)," ";
   next c
   print
   for r = 1 to N
        print r using "##"," ";
        for c = 1 to N
            pos = instr(queens$, (str$(r)+str$(c)))
            if pos and mod(pos, 2) then
                queens$ = mid$(queens$,pos)
                print "Q ";
            else
                print ". ";
            end if
        next c
        print
    next r
    print "\nPress Enter. (q to quit) "
    while(true)
        k$ = inkey$
        if lower$(k$) = "q" then
           exit
        elsif k$ = "enter" then
           break
        end if
    wend
end sub
 