$ filename "nQueens.exe"
'uses rtl32
'uses rtl64

uses console

'#minormajor
'#majorminor

! GetTickCount lib "kernel32.dll"


int doprint
int solution
int size_of_board
double t1, t2
string ans
sys *index

sub printBoard(int col_in_row[], int size_of_board, solution)
    int x, row, col

    printl "Solution: " + solution
    print "   "
   
    for x = 1 to size_of_board : print chr(x+96) + " " : next x
    printl
    for row = 1 to size_of_board
        if row < 10 then print row + "  " else print row + " "
        for col = 1 to size_of_board
            if col_in_row[col] = row then print "Q " else print "- "
        next col
        printl
    next row
    printl
end sub

function is_free(int col_in_row[], int test_row, int current_row) as int
    int i
    for i = 1 to current_row
        if col_in_row[i-1] = test_row or                                 'beat queen in the vertical
            abs(col_in_row[i-1]-test_row) = abs(i-1-current_row) then    'beat queen in the diagonal
            return 0
        end if
    next i
    return 1
end function

' place queen in current row
sub try(int col_in_row[], int current_row)
    int test_row
    if current_row > size_of_board then
        solution += 1 : if doprint = 0 then copy &index, &col_in_row[], size_of_board*sizeof(int)
        if solution = 1 then printBoard(col_in_row[], size_of_board, solution)
        if solution > 1 and doprint then printBoard(col_in_row[], size_of_board, solution)
    else
        for test_row = 1 to size_of_board
            if is_free(col_in_row[], test_row, current_row) then
                col_in_row[current_row] = test_row
                try(col_in_row[], current_row+1)
            end if
        next test_row
    end if
end sub


sub main()
loop1:
    redim int col_in_row(0)
    redim int indexes(0)
    solution = 0

    cls
    print "Size of Board (1-16)? " : size_of_board = val(input())

    if size_of_board < 1 then size_of_board = 1
    if size_of_board > 16 then size_of_board = 16
    printl "Your input = " size_of_board
    print  "Show all solutions - default is first and last? (Y/N): " : ans=ltrim rtrim(input) : printl
    if lcase(ans) = "y" then doprint = 1 else doprint = 0

    redim int col_in_row(size_of_board)  'column of queen in row
    redim int indexes(size_of_board)
    @index = @indexes

    t1=GetTickCount
    try(col_in_row[], 1)
    t2=GetTickCount

    if doprint = 0 then 
       printBoard(indexes[], size_of_board, solution)
    endif   
    printl "Found " + solution + " Solutions, " + "used time: " + (t2-t1)/1000 + " seconds"

    print "Another Try? (Y/N) "
    ans = ltrim rtrim(input())
    if lcase(ans) = "y" then goto loop1
end sub

main()
