

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


 
DIM SHARED QUEENS AS INTEGER
PRINT "# of queens:";: INPUT QUEENS
IF QUEENS = 0 THEN END
OPEN LTRIM$(STR$(QUEENS)) + "queens.dat" FOR OUTPUT AS #1
PRINT "Queens: Calculates"; QUEENS; " queens problem."
DIM SHARED arrayqcol(QUEENS) AS LONG ' columns of queens
DIM SHARED nsolutions AS LONG
CALL dorow(1) ' start with row 1
LOCATE 22, 1
PRINT STR$(nsolutions) + " solutions"
END
SUB dorow (irow) ' starts with row irow
    FOR icol = 1 TO QUEENS
        FOR iqueen = 1 TO irow - 1 ' check for conflict with previous queens
            IF arrayqcol(iqueen) = icol THEN GOTO continue1 ' same column?
            ' iqueen is also row of queen
            IF iqueen + arrayqcol(iqueen) = irow + icol THEN GOTO continue1 ' right diagonal?
            IF iqueen - arrayqcol(iqueen) = irow - icol THEN GOTO continue1 ' left diagonal?
        NEXT iqueen
        ' at this point we can add a queen
        arrayqcol(irow) = icol ' add to array
        LOCATE irow + 2, icol: PRINT "x"; ' show progress
        _DELAY (.001) ' slows processing
        IF irow = QUEENS THEN ' solution?
            nsolutions = nsolutions + 1
            PRINT #1, "Solution #" + MID$(STR$(nsolutions), 2) + "."
            FOR i1 = 1 TO QUEENS ' rows
                s1$ = STRING$(QUEENS, ".") ' columns
                MID$(s1$, arrayqcol(i1), 1) = "x" ' x in queen column
                PRINT #1, s1$
            NEXT i1
            PRINT #1, ""
        ELSE
            CALL dorow(irow + 1) ' recursive call to next row
        END IF
        LOCATE irow + 2, icol: PRINT "."; ' remove queen
        continue1:
    NEXT icol
END SUB
 