n-queens puzzle in Python

I want to increase the efficiency and reduce the time complexity for the n-queen problem in nn matrix chess. I am able to run only still (1111) in normal time otherwise for the big number it is taking much more time. How can I improve performance?

import time

start_time = time.time()

def queensproblem(rows, columns):
    solutions = [[]]
    for row in range(rows):
        solutions = add_one_queen(row, columns, solutions)
    return solutions

def add_one_queen(new_row, columns, prev_solutions):
    return [solution + [new_column]
            for solution in prev_solutions
            for new_column in range(columns)
            if no_conflict(new_row, new_column, solution)]

def no_conflict(new_row, new_column, solution):
    return all(solution[row]       != new_column           and
               solution[row] + row != new_column + new_row and
               solution[row] - row != new_column - new_row
               for row in range(new_row))

count = 0
r = input("Enter number of ROWS for Chess/Matrix: ")
c = input("Enter number of COLUMNS for Chess/Matrix: ")

for solution in queensproblem(int(r), int(c)):
    count += 1
    print(solution)

print("\n Total number of solution is: ", count)

print("--- Time: %s seconds ---" % (time.time() - start_time))

Output

For a 4x4 matrix

Enter number of ROWS for Chess/Matrix: 4
Enter number of COLUMNS for Chess/Matrix: 4
[1, 3, 0, 2]
[2, 0, 3, 1]

Total number of solution is: 2
--- Time: 2.3161020278930664 seconds ---


For a 12x12 matrix

Enter number of ROWS for Chess/Matrix: 12
Enter number of COLUMNS for Chess/Matrix: 12
[0, 2, 4, 7, 9, 11, 5, 10, 1, 6, 8, 3]
[0, 2, 4, 9, 7, 10, 1, 11, 5, 8, 6, 3]

Total number of solution is: 14200
--- Time: 29.522358894348145 seconds ---


To my surprise, rewriting no_conflict as

def no_conflict(new_row, new_col, solution):
    for row, col in enumerate(solution):
        if col == new_col or row + col == new_row + new_col or row - col == new_row - new_col:       
            return False
    return True

resulted in a factor of 2 speedup. I have no explanation.

Other tweaks I tried gave very marginal performance changes.

As for the general review, the code is quite straightforward and readable. The only recommendation is to compute start_time after taking inputs. As written, you are timing not only the algorithm but also user's typing skills.

StackExchange Code Review Q#122673, answer score: 4