' Knight's Tour — solves knight's tour on a chessboard using Warnsdorff's heuristic
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL board(400) AS LONG
    LOCAL boardSize AS LONG
    LOCAL moveX(8) AS LONG
    LOCAL moveY(8) AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL k AS LONG
    LOCAL moveCount AS LONG
    LOCAL curX AS LONG
    LOCAL curY AS LONG
    LOCAL nextX AS LONG
    LOCAL nextY AS LONG
    LOCAL minDeg AS LONG
    LOCAL minIdx AS LONG
    LOCAL deg(8) AS LONG
    LOCAL nx AS LONG
    LOCAL ny AS LONG
    LOCAL totalMoves AS LONG
    LOCAL lineStr AS STRING
    LOCAL valStr AS STRING
    LOCAL testCount AS LONG
    LOCAL passCount AS LONG
    LOCAL failCount AS LONG
    testCount = 0
    passCount = 0
    failCount = 0
    moveX(1) = 2: moveY(1) = 1
    moveX(2) = 1: moveY(2) = 2
    moveX(3) = -1: moveY(3) = 2
    moveX(4) = -2: moveY(4) = 1
    moveX(5) = -2: moveY(5) = -1
    moveX(6) = -1: moveY(6) = -2
    moveX(7) = 1: moveY(7) = -2
    moveX(8) = 2: moveY(8) = -1
    PRINT "============================================"
    PRINT "        KNIGHT'S TOUR SOLVER"
    PRINT "============================================"
    PRINT ""
    PRINT "Using Warnsdorff's heuristic"
    PRINT ""
    boardSize = 5
    PRINT "Solving " + STR$(boardSize) + "x" + STR$(boardSize) + " knight's tour..."
    PRINT ""
    FOR i = 0 TO boardSize * boardSize - 1
        board(i) = -1
    NEXT i
    curX = 0
    curY = 0
    board(curY * boardSize + curX) = 1
    totalMoves = 1
    FOR moveCount = 2 TO boardSize * boardSize
        minDeg = 9
        minIdx = -1
        FOR k = 1 TO 8
            nx = curX + moveX(k)
            ny = curY + moveY(k)
            IF nx >= 0 AND nx < boardSize AND ny >= 0 AND ny < boardSize THEN
                IF board(ny * boardSize + nx) = -1 THEN
                    deg(k) = 0
                    FOR j = 1 TO 8
                        nextX = nx + moveX(j)
                        nextY = ny + moveY(j)
                        IF nextX >= 0 AND nextX < boardSize AND nextY >= 0 AND nextY < boardSize THEN
                            IF board(nextY * boardSize + nextX) = -1 THEN
                                deg(k) = deg(k) + 1
                            END IF
                        END IF
                    NEXT j
                    IF deg(k) < minDeg THEN
                        minDeg = deg(k)
                        minIdx = k
                    END IF
                END IF
            END IF
        NEXT k
        IF minIdx = -1 THEN
            EXIT FOR
        END IF
        curX = curX + moveX(minIdx)
        curY = curY + moveY(minIdx)
        board(curY * boardSize + curX) = moveCount
        totalMoves = moveCount
    NEXT moveCount
    PRINT "Tour result (" + STR$(totalMoves) + " of " + STR$(boardSize * boardSize) + " squares):"
    PRINT ""
    FOR i = 0 TO boardSize - 1
        lineStr = ""
        FOR j = 0 TO boardSize - 1
            valStr = STR$(board(i * boardSize + j))
            DO WHILE LEN(valStr) < 3
                valStr = " " + valStr
            LOOP
            lineStr = lineStr + valStr + " "
        NEXT j
        PRINT lineStr
    NEXT i
    PRINT ""
    IF totalMoves = boardSize * boardSize THEN
        PRINT "Complete tour found"
        testCount = testCount + 1
        passCount = passCount + 1
    ELSE
        PRINT "Partial tour (not all squares visited)"
    END IF
    PRINT ""
    PRINT "============================================"
    PRINT "     6x6 KNIGHT'S TOUR"
    PRINT "============================================"
    PRINT ""
    boardSize = 6
    FOR i = 0 TO boardSize * boardSize - 1
        board(i) = -1
    NEXT i
    curX = 0
    curY = 0
    board(curY * boardSize + curX) = 1
    totalMoves = 1
    FOR moveCount = 2 TO boardSize * boardSize
        minDeg = 9
        minIdx = -1
        FOR k = 1 TO 8
            nx = curX + moveX(k)
            ny = curY + moveY(k)
            IF nx >= 0 AND nx < boardSize AND ny >= 0 AND ny < boardSize THEN
                IF board(ny * boardSize + nx) = -1 THEN
                    deg(k) = 0
                    FOR j = 1 TO 8
                        nextX = nx + moveX(j)
                        nextY = ny + moveY(j)
                        IF nextX >= 0 AND nextX < boardSize AND nextY >= 0 AND nextY < boardSize THEN
                            IF board(nextY * boardSize + nextX) = -1 THEN
                                deg(k) = deg(k) + 1
                            END IF
                        END IF
                    NEXT j
                    IF deg(k) < minDeg THEN
                        minDeg = deg(k)
                        minIdx = k
                    END IF
                END IF
            END IF
        NEXT k
        IF minIdx = -1 THEN
            EXIT FOR
        END IF
        curX = curX + moveX(minIdx)
        curY = curY + moveY(minIdx)
        board(curY * boardSize + curX) = moveCount
        totalMoves = moveCount
    NEXT moveCount
    PRINT "6x6 tour result (" + STR$(totalMoves) + " of " + STR$(boardSize * boardSize) + "):"
    PRINT ""
    FOR i = 0 TO boardSize - 1
        lineStr = ""
        FOR j = 0 TO boardSize - 1
            valStr = STR$(board(i * boardSize + j))
            DO WHILE LEN(valStr) < 3
                valStr = " " + valStr
            LOOP
            lineStr = lineStr + valStr + " "
        NEXT j
        PRINT lineStr
    NEXT i
    PRINT ""
    PRINT "============================================"
    PRINT "     4x4 KNIGHT'S TOUR (no solution)"
    PRINT "============================================"
    PRINT ""
    boardSize = 4
    FOR i = 0 TO boardSize * boardSize - 1
        board(i) = -1
    NEXT i
    curX = 0
    curY = 0
    board(curY * boardSize + curX) = 1
    totalMoves = 1
    FOR moveCount = 2 TO boardSize * boardSize
        minDeg = 9
        minIdx = -1
        FOR k = 1 TO 8
            nx = curX + moveX(k)
            ny = curY + moveY(k)
            IF nx >= 0 AND nx < boardSize AND ny >= 0 AND ny < boardSize THEN
                IF board(ny * boardSize + nx) = -1 THEN
                    deg(k) = 0
                    FOR j = 1 TO 8
                        nextX = nx + moveX(j)
                        nextY = ny + moveY(j)
                        IF nextX >= 0 AND nextX < boardSize AND nextY >= 0 AND nextY < boardSize THEN
                            IF board(nextY * boardSize + nextX) = -1 THEN
                                deg(k) = deg(k) + 1
                            END IF
                        END IF
                    NEXT j
                    IF deg(k) < minDeg THEN
                        minDeg = deg(k)
                        minIdx = k
                    END IF
                END IF
            END IF
        NEXT k
        IF minIdx = -1 THEN
            EXIT FOR
        END IF
        curX = curX + moveX(minIdx)
        curY = curY + moveY(minIdx)
        board(curY * boardSize + curX) = moveCount
        totalMoves = moveCount
    NEXT moveCount
    PRINT "4x4 tour: " + STR$(totalMoves) + " of 16 squares (as expected)"
    PRINT ""
    PRINT "Knight's tour demonstration complete"
    FUNCTION = 0
END FUNCTION
