from array import array

solution_count = 0

def queen(current_row, num_row, solution_list):
    if current_row == num_row:
        global solution_count 
        solution_count = solution_count + 1
    else:
        current_row += 1
        next_moves = gen_nextpos(current_row, solution_list, num_row + 1)
        if next_moves:
            for move in next_moves:
                solution_list[current_row] = move
                queen(current_row, num_row, solution_list)
                solution_list[current_row] = 0
        else:
            return None

def gen_nextpos(a_row, solution_list, arr_size):
    cand_moves = []
    for column in range(1, arr_size):
        under_attack =  False
        for row in range(1, a_row):
            if (abs(a_row - row) == abs(column - solution_list[row]) 
                    or solution_list[row] == column):
                under_attack = True
                break
        if not under_attack:
            cand_moves.append(column)
    return cand_moves

def main():
    size=input('Ukazite razmeri stola:') 
    solution_list = array('i', [0]* (size + 1))
    queen(0, size, solution_list)
    print("Kol-vo vozmoznix raspolozenij: "+str(solution_count))


main()