global count # number of states generated

# Solve N-Queens problem
# Top-level function: Try all positions in first column
# Call recursive DFS to fill in the other cols.
def NQueensDFS(n):
    global count 
    count = 0
    board = [-1]*n
    for j in range(n):
        board[0] = j
        board, found = NQueensRec(board,1,n)
        if found:
            return board, count
    return [0], -1


# Depth-first search through space of boards
# The board has been partially filled in, up through col. i-1
# Try all possible values j such that <i,j> is not attacked in the current board
# Recursively fill in the rest of the board.

def NQueensRec(board,i,n):
    global count
    count += 1
    if i >= n:
        return board, True
    for j in range(n):
        attack = False
        for k in range(i):
            attack = QAttack(k,board[k],i,j)
            if attack: 
                break
        if not(attack):
            board[i]=j
            board, found = NQueensRec(board,i+1,n)
            if found:
                return board, True
    return board, False

# Return true if <k,m> attacks <i,j>
def QAttack(k,m,i,j):
    return (m==j) or (k+m == i+j) or (k-m == i-j)