1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ An educated guess is that isOK is suboptimal. Please post it as well. \$\endgroup\$ – vnp Oct 7 '18 at 19:04
  • \$\begingroup\$ @vnp actually the time complexity of isOk is only O(2n). So I don’t think so \$\endgroup\$ – Borna Ghahnoosh Oct 7 '18 at 19:14
  • \$\begingroup\$ "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? \$\endgroup\$ – Peter Taylor Oct 15 '18 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.