Nextrp [CPP] RU + Many GEOs Игра на карте России | NEXTRP

Difference between 2 solutions for n-queen puzzle in Python

python n-queens

260 просмотра

1 ответ

145 Репутация автора

I have 2 - seemingly identical solutions to the n-queen problem. Both produce exactly same results (I found both online), but the second one takes more than double the time the first one does. could you please help me and explain, where is the difference?

from itertools import permutations
import time

punkt1 = time.time()
cols = range(N)
for combo in permutations(cols):                      
    if N==len(set(combo[i]+i for i in cols))==len(set(combo[i]-i for i in cols)):
        sol += 1
        print('Solution '+str(sol)+' : '+str(combo)+'\n')  
        #print("\n".join(' o ' * i + ' X ' + ' o ' * (N-i-1) for i in combo) + "\n\n\n\n")
punkt2 = time.time()
czas = punkt2 - punkt1

def queensproblem(rows, columns):
    solutions = [[]]
    for row in range(rows):
        solutions = add_one_queen(row, columns, solutions)
    return solutions

def add_one_queen(new_row, columns, prev_solutions):
    return [solution + [new_column]
            for solution in prev_solutions
            for new_column in range(columns)
            if no_conflict(new_row, new_column, solution)]

def no_conflict(new_row, new_column, solution):
    return all(solution[row]       != new_column           and
               solution[row] + row != new_column + new_row and
               solution[row] - row != new_column - new_row
               for row in range(new_row))
punkt3 = time.time()
i = 1

for solution in queensproblem(8, 8):
    print('Solution', i,':', solution, '\n')
    i = i + 1

punkt4 = time.time()
czas2 = punkt4 - punkt3
print ("Czas wykonania pierwszej metody:")
print (czas,'\n')
print ("Czas wykonania drugiej metody:")
print (czas2)
Автор: kjubus Источник Размещён: 11.03.2017 02:04

Ответы (1)

2 плюса

3373 Репутация автора


At first glance, you seemed to be saying these algorithms produce the same results and differ in time by a constant factor, which is irrelevant when talking about algorithms.

However, if you make N a function parameter and check the timing for N=9 or N=10, you will see them diverge significantly. At N=11 the itertools.permutations version took 12 minutes, vs the other's 28 seconds. It becomes an algorithm problem if they grow at different rates, which they do.

The function which calls "for combo in permutations" is literally looking at every possible board, so you could line up three queens in a row, and it still thinks "I gotta keep adding queens and see if it works out". (That's every possible board representable by the notation. The notation itself eliminates a lot, but not enough.)

The other function is able to stop checking bad combinations and thus eliminate many bad candidates at once. Look at this printout of the decision tree for N=4, generated by adding print (row, solutions) in the queensproblem for loop:

0 [[0], [1], [2], [3]]
1 [[0, 2], [0, 3], [1, 3], [2, 0], [3, 0], [3, 1]]
2 [[0, 3, 1], [1, 3, 0], [2, 0, 3], [3, 0, 2]]
3 [[1, 3, 0, 2], [2, 0, 3, 1]]

Early in the logic, it looked at [0, 0] and [0, 1] and simply eliminated them. Therefore it never looked at [0, 0, 0] or ... many others. It continued to add new queens only for the solutions which passed the earlier checks. It also saves a lot of time by not even looking at all the subproblems it is eliminating inside no_conflit, because of short circuit boolean logic of "all" and "and".

Автор: Kenny Ostrom Размещён: 11.03.2017 04:27
Вопросы из категории :