CODEWITHSUNDEEP
pythonalgorithmcomplexity-theorytime-complexitybacktracking
c2h5oh
c2h5oh

Reputation: 227

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

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.

Upvotes: 2

Views: 4945

Answers (2)

justhalf
justhalf

Reputation: 9107

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.

Upvotes: 4

chesslover
chesslover

Reputation: 347

The question of solving N-queens without backtracking has another interesting question attached to it. Are there almost perfect queen placing heuristics such that, in a backtracking framework, you nearly always find a valid configuration? This is equivalent to saying that the heuristic almost always tells you the correct square to place the next queen on the board. This heuristic is much more interesting than the known closed form solution that gives a valid configuration for all values of N (except N=2 and 3, obviously).

The analysis of almost perfect minimum backtracking heuristics is an issue which has been studied in literature. The most important references are [Kalé 90] and [San Segundo 2011]. The best heuristic to place the next queen in the backtracking framework seems to be the following:

  1. Choose the most-restricted row to place the next queen (i.e that with less squares available)
  2. Choose the square from the row in (1) which closes the least number of diagonals (a least-restricting strategy).

Here to close a diagonal refers to cancel all its available squares.

Upvotes: 2

Related Questions