Implement the N-Queens Algorithm - Implement the N-Queens Algorithm

Curriculum Help
1

Tell us what’s happening:

My current solution only works until the board is 4x4, after that it doesn’t give all the solutions. The problem is that it explores one possible path, but doesn’t backtrack to search for other possible branching paths. But I’m not sure how to implement backtracking with the code the way it is

Your code so far

def dfs_n_queens(n: int) -> list[list[int]]: 
    solutions = [] 
    
    if n < 1:
        return solutions 
    def search(row_i: int, column_i: int, solution: list[int], board: list[list[int]]) -> None:
        board[row_i][column_i] = 1
        for i in range(n): 
            for j in range(n):
                # Mark row 
                if i == row_i and j != column_i:
                    board[i][j] = 2
                # Mark column
                if i != row_i and j == column_i:
                    board[i][j] = 2
        # Mark diagonals
        for l in range(n):
            if l != 0:
                if row_i+l < n and column_i+l < n:
                    board[row_i+l][column_i+l] = 2
                if row_i+l < n and column_i-l >= 0:
                    board[row_i+l][column_i-l] = 2
                if row_i-l >= 0 and column_i+l < n:
                    board[row_i-l][column_i+l] = 2
                if row_i-l >= 0 and column_i-l >= 0:
                    board[row_i-l][column_i-l] = 2
        # Print board for testing
        for row in board:
            print(row)
        print()
    
        queens = 0
        possible_paths = 0
        visited_paths = []
        for i in range(n):
            for j in range(n):
                if board[i][j] == 1:
                    queens += 1
                    solution[i] = j
                if queens == n and solution not in solutions:
                    solutions.append(solution)
                elif board[i][j] == 0:
                    possible_paths += 1
                    while len(visited_paths) < possible_paths:
                        if (i, j) not in visited_paths:
                            search(i, j, solution, board)
                            visited_paths.append((i, j))

    for i in range(n):
        for j in range(n):
            search(i, j, [0] * n, [[0] * n for _ in range(n)])
    return solutions
    
print(dfs_n_queens(5))

Your browser information:

User Agent is: Mozilla/5.0 (X11; Linux x86_64; rv:154.0) Gecko/20100101 Firefox/154.0

Challenge Information:

Implement the N-Queens Algorithm - Implement the N-Queens Algorithm

GitHub Link: freeCodeCamp/curriculum/challenges/english/blocks/lab-n-queens-problem/68dbc6b7e8f794a2ae69bc74.md at main · freeCodeCamp/freeCodeCamp · GitHub

2

Here’s a forum-style reply that guides without handing over the full solution:

Take a closer look at what happens to your board after a search() call returns. You mark cells as 2 for attacked rows/columns/diagonals when you place a queen — but where do those markings get undone once that branch of the search is done being explored?

Right now, once a cell gets marked 2, it stays 2 forever, even for branches that have nothing to do with the queen that caused the mark. At 4x4 you get lucky because there isn’t much room for that leftover state to cause damage before you land on your solutions — but as the board grows, more of your search space gets silently blocked off by “attacked” marks that don’t actually apply anymore.

That’s the missing half of backtracking: it’s not just “place → recurse,” it’s “place → recurse → undo the placement.” Ask yourself: right after your recursive call to search() returns, what would you need to reset so the board looks exactly like it did before you placed that queen?

Also worth checking: are board and solution the same list object across all your recursive calls, or fresh copies? If it’s the same object, think about what happens when one branch changes it — do sibling branches see that change too?