Не могу сказать разницу между двумя растворами Python N-Queens ⇐ Python

[Anonymous]

Чтение на обратной обработке привело меня к странице на Geeksforgeeks.org о решении проблемы N-Queens. Первое решение вводится как «наивный подход», который генерирует все возможные перестановки и является наименее эффективным при O (n! * N). Второе решение - «вместо того, чтобы генерировать все возможные перестановки, мы строим решение постепенно, при этом мы можем убедиться, что на каждом этапе частичное решение остается достоверным. Если возникнет конфликт, мы немедленно отступим, это поможет избежать ненужных вычислений». и предположительно, это O (n!).
Анализируя код, я просто не могу видеть разницу между двумя (с точки зрения рекурсии/обратной связи/обрезки), помимо различий в комментариях, некоторыми именами переменных, путем диагонального конфликта рассчитываются/зарегистрированы, и некоторые другие тривиальные вещи, которые не используют различие, а не из. (наименьшее эффективное): < /p>
#Python program to find all solution of N queen problem
#using recursion

# Function to check if placement is safe
def isSafe(board, currRow, currCol):
for i in range(len(board)):
placedRow = board
placedCol = i + 1

# Check diagonals
if abs(placedRow - currRow) == \
abs(placedCol - currCol):
return False # Not safe

return True # Safe to place

# Recursive utility to solve N-Queens
def nQueenUtil(col, n, board, res, visited):

# If all queens placed, add to res
if col > n:
res.append(board.copy())
return

# Try each row in column
for row in range(1, n+1):

# If row not used
if not visited[row]:

# Check safety
if isSafe(board, row, col):

# Mark row
visited[row] = True

# Place queen
board.append(row)

# Recur for next column
nQueenUtil(col+1, n, board, res, visited)

# Backtrack
board.pop()
visited[row] = False

# Main N-Queen solver
def nQueen(n):
res = []
board = []
visited = [False] * (n + 1)
nQueenUtil(1, n, board, res, visited)
return res

if __name__ == "__main__":
n = 4
res = nQueen(n)
for row in res:
print(row)
< /code>
Второе решение (возврат с обрезкой, якобы более эффективным): < /p>
# Python program to find all solutions of the N-Queens problem
# using backtracking and pruning

def nQueenUtil(j, n, board, rows, diag1, diag2, res):

if j > n:
# A solution is found
res.append(board[:])
return

for i in range(1, n + 1):
if not rows and not diag1[i + j] and not diag2[i - j + n]:

# Place queen
rows = diag1[i + j] = diag2[i - j + n] = True
board.append(i)

# Recurse to the next column
nQueenUtil(j + 1, n, board, rows, diag1, diag2, res)

# Remove queen (backtrack)
board.pop()
rows = diag1[i + j] = diag2[i - j + n] = False

def nQueen(n):
res = []
board = []

# Rows occupied
rows = [False] * (n + 1)

# Major diagonals (row + j) and Minor diagonals (row - col + n)
diag1 = [False] * (2 * n + 1)
diag2 = [False] * (2 * n + 1)

# Start solving from the first column
nQueenUtil(1, n, board, rows, diag1, diag2, res)
return res

if __name__ == "__main__":
n = 4
res = nQueen(n)

for temp in res:
print(temp)


Подробнее здесь: https://stackoverflow.com/questions/795 ... -solutions