Can we solve N Queens without backtracking? and How to calculate and what will be the complexity of the backtracking solution?

Question

I have tried solving this problem with backtracking and it prints all possible solutions.

Two questions came up:

1.Can i implement n queen using other techniques?

2.Is it possible to make the code below print only the first solution and then terminate?

My current code uses backtracking:

n = 8

x = [-1 for x in range(n)]

def safe(k,i):
    for j in xrange(k):
          if x[j] == i  or abs(x[j] - i) == abs(k - j) :
          return False
    return True


def nqueen(k):
    for i in xrange(n):
        if safe(k,i):
            x[k] = i 
        if k == n-1:
            print "SOLUTION", x
        else:
            nqueen(k+1)

nqueen(0)

Note: I am interested in techniques that do not depend on a particular programming language.

Answer 1

According to Wikipedia, you can do using heuristics:

This heuristic solves N queens for any N ≥ 4. It forms the list of numbers for vertical positions (rows) of queens with horizontal position (column) simply increasing. N is 8 for eight queens puzzle.

1. If the remainder from dividing N by 6 is not 2 or 3 then the list is simply all even numbers followed by all odd numbers ≤ N
2. Otherwise, write separate lists of even and odd numbers (i.e. 2,4,6,8 - 1,3,5,7)
3. If the remainder is 2, swap 1 and 3 in odd list and move 5 to the end (i.e. 3,1,7,5)
4. If the remainder is 3, move 2 to the end of even list and 1,3 to the end of odd list (i.e. 4,6,8,2 - 5,7,9,1,3)
5. Append odd list to the even list and place queens in the rows given by these numbers, from left to right (i.e. a2, b4, c6, d8, e3, f1, g7, h5)

This heuristics is O(n) since it's just printing the result after some if statements.

Regarding your second question: "Is it possible to make code below to print only first solution and then terminate?"

You can just call sys.exit(0) after you print:

import sys
n = 8

x = [-1 for x in range(n)]

def safe(k,i):
    for j in xrange(k):
          if x[j] == i  or abs(x[j] - i) == abs(k - j) :
          return False
    return True


def nqueen(k):
    for i in xrange(n):
        if safe(k,i):
            x[k] = i 
            if k == n-1:
                print "SOLUTION", x
                sys.exit(0)
            else:
                nqueen(k+1)

nqueen(0)

or, alternatively you can return a value and then propagate the value if it indicates termination:

n = 8

x = [-1 for x in range(n)]

def safe(k,i):
    for j in xrange(k):
          if x[j] == i  or abs(x[j] - i) == abs(k - j) :
          return False
    return True


def nqueen(k):
    for i in xrange(n):
        if safe(k,i):
            x[k] = i 
            if k == n-1:
                print "SOLUTION", x
                return True # Found a solution, send this good news!
            else:
                if nqueen(k+1): # Good news!
                    return True # Share the good news to parent!
    return False # We have searched every possible combinations, and I regret to tell you that I could not find any solution.

nqueen(0)

As for the time complexity, since it's a complete search, it's n^n. Although due to the pruning (using safe(k,i)), in practice it's a lot faster.