' N-Queens — solves the N-Queens problem using backtracking
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL board(100) AS LONG
    LOCAL n AS LONG
    LOCAL row AS LONG
    LOCAL col AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL testCol AS LONG
    LOCAL conflict AS LONG
    LOCAL solutionCount AS LONG
    LOCAL lineStr AS STRING
    LOCAL testCount AS LONG
    LOCAL passCount AS LONG
    LOCAL failCount AS LONG
    testCount = 0
    passCount = 0
    failCount = 0
    PRINT "============================================"
    PRINT "           N-QUEENS SOLVER"
    PRINT "============================================"
    PRINT ""
    FOR n = 4 TO 8
        PRINT "Solving " + STR$(n) + "-Queens..."
        PRINT ""
        FOR i = 0 TO n - 1
            board(i) = -1
        NEXT i
        row = 0
        col = 0
        solutionCount = 0
        DO WHILE row >= 0
            IF row < n THEN
                IF col >= n THEN
                    row = row - 1
                    IF row >= 0 THEN
                        col = board(row) + 1
                        board(row) = -1
                    END IF
                ELSE
                    conflict = 0
                    FOR i = row - 1 TO 0 STEP -1
                        IF board(i) = col THEN
                            conflict = 1
                            EXIT FOR
                        END IF
                        IF board(i) = col - (row - i) THEN
                            conflict = 1
                            EXIT FOR
                        END IF
                        IF board(i) = col + (row - i) THEN
                            conflict = 1
                            EXIT FOR
                        END IF
                    NEXT i
                    IF conflict = 0 THEN
                        board(row) = col
                        row = row + 1
                        col = 0
                    ELSE
                        col = col + 1
                    END IF
                END IF
            ELSE
                solutionCount = solutionCount + 1
                PRINT "Solution " + STR$(solutionCount) + ":"
                FOR i = 0 TO n - 1
                    lineStr = ""
                    FOR j = 0 TO n - 1
                        IF board(i) = j THEN
                            lineStr = lineStr + " Q"
                        ELSE
                            lineStr = lineStr + " ."
                        END IF
                    NEXT j
                    PRINT lineStr
                NEXT i
                PRINT ""
                row = row - 1
                IF row >= 0 THEN
                    col = board(row) + 1
                    board(row) = -1
                END IF
            END IF
        LOOP
        PRINT STR$(n) + "-Queens has " + STR$(solutionCount) + " solutions"
        PRINT ""
        IF n = 4 AND solutionCount = 2 THEN
            testCount = testCount + 1
            passCount = passCount + 1
        END IF
        IF n = 5 AND solutionCount = 10 THEN
            testCount = testCount + 1
            passCount = passCount + 1
        END IF
    NEXT n
    PRINT "============================================"
    PRINT "     ALL SOLUTIONS COUNT VERIFICATION"
    PRINT "============================================"
    PRINT ""
    PRINT "Expected solution counts:"
    PRINT "  4-Queens: 2 solutions"
    PRINT "  5-Queens: 10 solutions"
    PRINT "  6-Queens: 4 solutions"
    PRINT "  7-Queens: 40 solutions"
    PRINT "  8-Queens: 92 solutions"
    PRINT ""
    PRINT "Verifying with backtracking..."
    PRINT ""
    FOR n = 4 TO 8
        FOR i = 0 TO n - 1
            board(i) = -1
        NEXT i
        row = 0
        col = 0
        solutionCount = 0
        DO WHILE row >= 0
            IF row < n THEN
                IF col >= n THEN
                    row = row - 1
                    IF row >= 0 THEN
                        col = board(row) + 1
                        board(row) = -1
                    END IF
                ELSE
                    conflict = 0
                    FOR i = row - 1 TO 0 STEP -1
                        IF board(i) = col THEN
                            conflict = 1
                            EXIT FOR
                        END IF
                        IF board(i) = col - (row - i) THEN
                            conflict = 1
                            EXIT FOR
                        END IF
                        IF board(i) = col + (row - i) THEN
                            conflict = 1
                            EXIT FOR
                        END IF
                    NEXT i
                    IF conflict = 0 THEN
                        board(row) = col
                        row = row + 1
                        col = 0
                    ELSE
                        col = col + 1
                    END IF
                END IF
            ELSE
                solutionCount = solutionCount + 1
                row = row - 1
                IF row >= 0 THEN
                    col = board(row) + 1
                    board(row) = -1
                END IF
            END IF
        LOOP
        PRINT STR$(n) + "-Queens: " + STR$(solutionCount) + " solutions"
    NEXT n
    PRINT ""
    PRINT "============================================"
    PRINT "     FIRST SOLUTION FOR 8-QUEENS"
    PRINT "============================================"
    PRINT ""
    n = 8
    FOR i = 0 TO n - 1
        board(i) = -1
    NEXT i
    row = 0
    col = 0
    DO WHILE row >= 0 AND row < n
        IF col >= n THEN
            row = row - 1
            IF row >= 0 THEN
                col = board(row) + 1
                board(row) = -1
            END IF
        ELSE
            conflict = 0
            FOR i = row - 1 TO 0 STEP -1
                IF board(i) = col THEN
                    conflict = 1
                    EXIT FOR
                END IF
                IF board(i) = col - (row - i) THEN
                    conflict = 1
                    EXIT FOR
                END IF
                IF board(i) = col + (row - i) THEN
                    conflict = 1
                    EXIT FOR
                END IF
            NEXT i
            IF conflict = 0 THEN
                board(row) = col
                row = row + 1
                col = 0
            ELSE
                col = col + 1
            END IF
        END IF
    LOOP
    PRINT "First 8-Queens solution:"
    PRINT ""
    FOR i = 0 TO n - 1
        lineStr = ""
        FOR j = 0 TO n - 1
            IF board(i) = j THEN
                lineStr = lineStr + " Q"
            ELSE
                lineStr = lineStr + " ."
            END IF
        NEXT j
        PRINT lineStr
    NEXT i
    PRINT ""
    testCount = testCount + 1
    passCount = passCount + 1
    PRINT "Results: " + STR$(passCount) + " passed, " + STR$(failCount) + " failed of " + STR$(testCount)
    FUNCTION = 0
END FUNCTION
