n Queen Programming Problems

n Queen Programming Problemsis a classic problem, remember that the on-line question for the PhD recruitment in the School of Computer Science of Beijing University of Aeronautics and Astronautics (BUAA) in 2018 is this one, and several implementation methods are given here:

import time
import itertools

Num =  8
# Num = 12   # 8

def f1():
    def test_queens(queens):
        for x in range(Num):
            for y in range(x+1, Num):
                if abs(queens[x]-queens[y])==abs(x-y):
                    return False
        return True
    
    counter = 0
    for i in range(12345678, 87654321, 1):
        s = str(i)
        if "0" in s or "9" in s:
            continue
        if len(set(s)) != 8:
            continue
        if test_queens([int(digit)-1 for digit in s]):
            counter += 1
    return counter


def f2():
    def conflict(state, nextX):
        nextY = len(state)
        for i in range(nextY):
            if abs(state[i]-nextX) in (0, nextY-i):
                return True
        return False

    def queens(num=Num, state=()):
        for pos in range(num):
            if not conflict(state, pos):
                if len(state) == num-1:
                    yield (pos, )
                else:
                    for result in queens(num, state+(pos, )):
                        yield (pos, ) + result

    return queens()


def f3():
    num = Num
    def conflict(queen):
        for x in range(num):
            for y in range(x+1, num):
                if abs(queen[x]-queen[y])==(y-x):
                    return True
        return False

    queens = []
    for queen in (range(num)):
        if not conflict(queen):
            (queen)
    return queens


_a = ()
print(f1())
_b = ()
print(_b - _a)


_a = ()
print(len([x for x in f2()]))
_b = ()
print(_b - _a)


_a = ()
print(len([x for x in f3()]))
_b = ()
print(_b - _a)

In the above implementation, when n=8, the running time of f1() function implementation, f2() function implementation, and f3() function implementation are as follows (in seconds):

92
11.19756269454956
92
0.005673408508300781
92
0.019522428512573242

It can be seen that the f1() function implementation is 2000 times more time-consuming than the f2 implementation, so in the following for n=12 we only give the time-consumption under the f2() and f3() function implementations:

14200
4.591862201690674
14200
295.7449884414673

It can be seen that the time taken under the f3() implementation is 60 times more than under the f2() implementation.

Summary:

The f2() method implementation is the one with the shortest running time.

The f3() method takes 60 times longer than f2().

The f1() method takes 2000 times longer than f2().

However, at n=8, which is the 8-queen problem, both f2() and f3() take the usual time (within 1 second or 5 seconds).

Since yield is used in f2(), which is not generic, it was changed to return and sss=[ ] was added as a state saver with the following code:

import time
import itertools
 
Num =  8

 
def f2():
    def conflict(state, nextX):
        nextY = len(state)
        for i in range(nextY):
            if abs(state[i]-nextX) in (0, nextY-i):
                return True
        return False
 
    def queens(num, state=()):
        sss = []
        for pos in range(num):
            if not conflict(state, pos):
                if len(state) == num-1:
                    # yield (pos, )
                    ((pos,))
                else:
                    for result in queens(num, state+(pos, )):
                        # yield (pos, ) + result
                        ( (pos, ) + result )
        return sss

    return queens(8)
 
_a = ()
print(len([x for x in f2()]))
_b = ()
print(_b - _a)

The results of the run are as follows:

However, considering that even changing the yield in f2() to return requires the use of a recursive algorithm, which can be replaced using a looping algorithm, the recursion in f2() is modified using a looping algorithm to get the following code:

import time
 
 
def f2():
    def conflict(state, nextX):
        nextY = len(state)
        for i in range(nextY):
            if abs(state[i]-nextX) in (0, nextY-i):
                return True
        return False
 
    def queens():
        s = [[i, ] for i in range(8)]  # initialization
        s_tmp = []

        count = 0

        while count<8-1:
            for state in s:
                for pos in range(8):
                    if not conflict(state, pos):
                        state_copy = ()
                        state_copy.append(pos)
                        s_tmp.append(state_copy)
            s = s_tmp
            s_tmp = []
            count += 1
        return s

    return queens()
 
_a = ()
print(len([x for x in f2()]))
_b = ()
print(_b - _a)

The results of the run are as follows:

Personal github blog address:
/