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
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