# Using most constraining variable and least constraining value for N-queens challenge

I was trying to solve the N-Queens(Only 1 solution) problem and I succeeded but my program could only calculate up to N = 47 in a good amount of time so I tried to implement least constraining value and most constraining variable and even though it got faster, it was still slow. What can I do to be able to calculate up to N = 1000?

def solve(n, x, board, mid_rows, sd_squares):
# If we are on the last row, it means we have put all the queens:
if x >= n:
print_board(board)
sys.exit(0)

for i in sd_squares:
# If we can put a queen on the current square, do it
if isOk(board, mid_rows[x], i, n):
board[mid_rows[x]][i] = 1

# Do the same thing for the next row
solve(n, x + 1, board, mid_rows, sd_squares)

# If we are here, it means we put the queen in the wrong square so we have to remove that queen
board[mid_rows[x]][i] = 0


I can't post the whole code because it's too long but please note that isOk(board, x, y, n) is a function that tells if we put a queen on the x row and y column it threatens other queens or not.

mid_rows is an array that includes the most middle rows to the side rows so like let's say n = 5, then it's [2,3,1,4,0] or when n = 6 it's [3,2,4,1,5,0].

sd_squares is a list that contains the side squares to middle squares. Like when n = 5 it's [0,4,1,3,2] or when n = 6 it's [0,5,1,4,2,3].

• An educated guess is that isOK is suboptimal. Please post it as well. – vnp Oct 7 '18 at 19:04
• @vnp actually the time complexity of isOk is only O(2n). So I don’t think so – Borna Ghahnoosh Oct 7 '18 at 19:14
• "I tried to implement least constraining value and most constraining variable": I can't see any evidence of this in the code. Could you clarify? – Peter Taylor Oct 15 '18 at 16:14