Difference between 2 solutions for n-queen puzzle in Python
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?
Автор: kjubus Источник Размещён: 11.03.2017 02:04
from itertools import permutations import time punkt1 = time.time() N=8 sol=0 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)
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 [, , , ] 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