Início / user-13824855

retpoline's questions

Martin Hope
retpoline
Asked: 2025-04-26 16:31:41 +0800 CST
  • 6

Ler sobre retrocesso me levou a uma página no geeksforgeeks.org sobre soluções para o problema das n-rainhas. A primeira solução é apresentada como a "abordagem ingênua", que gera todas as permutações possíveis e é a menos eficiente em O(n! * n). A segunda solução é "Em vez de gerar todas as permutações possíveis, construímos a solução incrementalmente, garantindo assim, a cada passo, que a solução parcial permaneça válida. Se ocorrer um conflito, retrocederemos imediatamente, o que ajuda a evitar cálculos desnecessários." e supostamente é O(n!).

Analisando o código, simplesmente não consigo ver a diferença entre os dois (em termos de recursão/retrocesso/poda), além das diferenças nos comentários, alguns nomes de variáveis, a maneira como os conflitos diagonais são calculados/registrados e algumas outras coisas triviais que não fazem diferença, como usar [:] em vez de .copy().

Primeira solução (menos eficiente):

#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[i]
        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)

Segunda solução (retrocesso com poda, supostamente mais eficiente):

# 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[i] and not diag1[i + j] and not diag2[i - j + n]:

            # Place queen
            rows[i] = 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[i] = 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)
python