' Sudoku Solver — solves 9x9 Sudoku puzzles using backtracking
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL grid(81) AS LONG
    LOCAL original(81) AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL row AS LONG
    LOCAL col AS LONG
    LOCAL num AS LONG
    LOCAL boxRow AS LONG
    LOCAL boxCol AS LONG
    LOCAL found AS LONG
    LOCAL solved AS LONG
    LOCAL attempt AS LONG
    LOCAL isValid AS LONG
    LOCAL lineStr AS STRING
    LOCAL valStr AS STRING
    LOCAL testCount AS LONG
    LOCAL passCount AS LONG
    LOCAL failCount AS LONG
    LOCAL br AS LONG
    LOCAL bc AS LONG
    testCount = 0
    passCount = 0
    failCount = 0
    PRINT "============================================"
    PRINT "          SUDOKU SOLVER"
    PRINT "============================================"
    PRINT ""
    PRINT "Puzzle (easy):"
    PRINT ""
    grid(0)=5:grid(1)=3:grid(2)=0:grid(3)=0:grid(4)=7:grid(5)=0:grid(6)=0:grid(7)=0:grid(8)=0
    grid(9)=6:grid(10)=0:grid(11)=0:grid(12)=1:grid(13)=9:grid(14)=5:grid(15)=0:grid(16)=0:grid(17)=0
    grid(18)=0:grid(19)=9:grid(20)=8:grid(21)=0:grid(22)=0:grid(23)=0:grid(24)=0:grid(25)=6:grid(26)=0
    grid(27)=8:grid(28)=0:grid(29)=0:grid(30)=0:grid(31)=6:grid(32)=0:grid(33)=0:grid(34)=0:grid(35)=3
    grid(36)=4:grid(37)=0:grid(38)=0:grid(39)=8:grid(40)=0:grid(41)=3:grid(42)=0:grid(43)=0:grid(44)=1
    grid(45)=7:grid(46)=0:grid(47)=0:grid(48)=0:grid(49)=2:grid(50)=0:grid(51)=0:grid(52)=0:grid(53)=6
    grid(54)=0:grid(55)=6:grid(56)=0:grid(57)=0:grid(58)=0:grid(59)=0:grid(60)=2:grid(61)=8:grid(62)=0
    grid(63)=0:grid(64)=0:grid(65)=0:grid(66)=4:grid(67)=1:grid(68)=9:grid(69)=0:grid(70)=0:grid(71)=5
    grid(72)=0:grid(73)=0:grid(74)=0:grid(75)=0:grid(76)=8:grid(77)=0:grid(78)=0:grid(79)=7:grid(80)=9
    FOR row = 0 TO 8
        lineStr = ""
        FOR col = 0 TO 8
            valStr = STR$(grid(row * 9 + col))
            IF grid(row * 9 + col) = 0 THEN
                lineStr = lineStr + " ."
            ELSE
                lineStr = lineStr + valStr
            END IF
            lineStr = lineStr + " "
            IF col = 2 OR col = 5 THEN
                lineStr = lineStr + "|"
            END IF
        NEXT col
        PRINT lineStr
        IF row = 2 OR row = 5 THEN
            PRINT "-------+-------+-------"
        END IF
    NEXT row
    PRINT ""
    FOR i = 0 TO 80
        original(i) = grid(i)
    NEXT i
    solved = 1
    attempt = 0
    row = 0
    DO WHILE row < 9 AND attempt < 10000
        col = row
        found = 0
        FOR i = 0 TO 80
            IF grid(i) = 0 THEN
                row = i / 9
                col = i - row * 9
                found = 1
                EXIT FOR
            END IF
        NEXT i
        IF found = 0 THEN
            GOTO puzzleSolved
        END IF
        num = grid(row * 9 + col)
        num = num + 1
        DO WHILE num <= 9
            isValid = 1
            FOR j = 0 TO 8
                IF j <> col AND grid(row * 9 + j) = num THEN
                    isValid = 0
                END IF
            NEXT j
            IF isValid = 1 THEN
                FOR j = 0 TO 8
                    IF j <> row AND grid(j * 9 + col) = num THEN
                        isValid = 0
                    END IF
                NEXT j
            END IF
            IF isValid = 1 THEN
                boxRow = (row / 3) * 3
                boxCol = (col / 3) * 3
                FOR j = 0 TO 8
                    br = boxRow + j / 3
                    bc = boxCol + j - (j / 3) * 3
                    IF (br <> row OR bc <> col) AND grid(br * 9 + bc) = num THEN
                        isValid = 0
                    END IF
                NEXT j
            END IF
            IF isValid = 1 THEN
                EXIT DO
            END IF
            num = num + 1
        LOOP
        IF num > 9 THEN
            grid(row * 9 + col) = 0
            FOR i = row * 9 + col - 1 TO 0 STEP -1
                IF original(i) = 0 THEN
                    row = i / 9
                    col = i - row * 9
                    EXIT FOR
                END IF
            NEXT i
        ELSE
            grid(row * 9 + col) = num
            row = row + 1
        END IF
        attempt = attempt + 1
    LOOP
puzzleSolved:
    PRINT "Solved puzzle (attempts=" + STR$(attempt) + "):"
    PRINT ""
    FOR row = 0 TO 8
        lineStr = ""
        FOR col = 0 TO 8
            valStr = STR$(grid(row * 9 + col))
            lineStr = lineStr + valStr + " "
            IF col = 2 OR col = 5 THEN
                lineStr = lineStr + "|"
            END IF
        NEXT col
        PRINT lineStr
        IF row = 2 OR row = 5 THEN
            PRINT "-------+-------+-------"
        END IF
    NEXT row
    PRINT ""
    PRINT "============================================"
    PRINT "     VALIDATION"
    PRINT "============================================"
    PRINT ""
    solved = 1
    FOR row = 0 TO 8
        FOR col = 0 TO 8
            num = grid(row * 9 + col)
            IF num < 1 OR num > 9 THEN
                solved = 0
            END IF
            FOR j = 0 TO 8
                IF j <> col AND grid(row * 9 + j) = num THEN
                    solved = 0
                END IF
                IF j <> row AND grid(j * 9 + col) = num THEN
                    solved = 0
                END IF
            NEXT j
            boxRow = (row / 3) * 3
            boxCol = (col / 3) * 3
            FOR j = 0 TO 8
                br = boxRow + j / 3
                bc = boxCol + j - (j / 3) * 3
                IF (br <> row OR bc <> col) AND grid(br * 9 + bc) = num THEN
                    solved = 0
                END IF
            NEXT j
        NEXT col
    NEXT row
    IF solved = 1 THEN
        PRINT "PASS: Sudoku is correctly solved"
        passCount = passCount + 1
    ELSE
        PRINT "FAIL: Sudoku has errors"
        failCount = failCount + 1
    END IF
    testCount = testCount + 1
    PRINT ""
    PRINT "Sudoku solver complete"
    FUNCTION = 0
END FUNCTION
