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

Python
1

Tell us what’s happening:

I’ve been trying to solve this for the past few days without any tutorial and am completely stuck at this point. Is this a dead end or can I still salvage a miracle out of this?

Your code so far

from copy import deepcopy
def dfs_n_queens(n):
    solutions = []
    if n < 1:
        return solutions
    board = []
    for _ in range(n):
        board.append([0] * n)
    indices = []
    def insert_queen(queens_left, board_to_edit):
        _board = deepcopy(board_to_edit)
        nonlocal solutions
        nonlocal indices
        nonlocal n
        if queens_left == 0:
            if indices not in solutions:
                solutions.append(deepcopy(indices))
            indices.clear()
            return
        for a, row in enumerate(_board):
            for b, _ in enumerate(row):
                if queens_left == n:
                    _board = deepcopy(board_to_edit)
                    indices.clear()
                if _ == 0:
                    indices.append(b)
                    _board[a] = [1] * n
                    for i in _board:
                        i[b] = 1
                    dri = a
                    dci = b
                    while dri >= 0 and dci >= 0 and dri < n and dci < n:
                        _board[dri][dci] = 1
                        dri += 1
                        dci += 1
                    dri = a
                    dci = b
                    while dri >= 0 and dci >= 0 and dri < n and dci < n:
                        _board[dri][dci] = 1
                        dri -= 1
                        dci += 1
                    dri = a
                    dci = b
                    while dri >= 0 and dci >= 0 and dri < n and dci < n:
                        _board[dri][dci] = 1
                        dri += 1
                        dci -= 1
                    dri = a
                    dci = b
                    while dri >= 0 and dci >= 0 and dri < n and dci < n:
                        _board[dri][dci] = 1
                        dri -= 1
                        dci -= 1
                    length = len(indices)
                    insert_queen(queens_left - 1, _board)
                    _board = deepcopy(board_to_edit)
                    while length < len(indices):
                        indices.pop()
                    
    insert_queen(n, board)
    return solutions

print(dfs_n_queens(4))

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:146.0) Gecko/20100101 Firefox/146.0

Challenge Information:

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

2

Could you explain what’s your general idea here?

3

So basically, the child function has 2 parameters, number of queens left to place on the board and a board showing the spaces blocked by queens already placed on the board.

Each square on the board is either marked 0 (not blocked by a queen) or 1 (blocked by a queen).

If there’s a valid space on the board, a queen is placed on that board and the function will be called again and again with updated parameters until either a valid solution or a dead end is reached.

5 
print(dfs_n_queens(4))

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

The first result in the output is valid, but the second result isn’t.

Are you able to follow the logic of your program and explain why the 2 is placed in the second group [1, 3, 2, 0] ? That’s the first mis-step.

Sounds like a good idea, can you explain how it works? Maybe print this step and ensure it’s working correctly.

1 Like
6

I found the issue, it would tend to skip a row if no valid spaces were there and would incorrectly mark that space later on. I fixed it and am getting the correct solutions now but I think my code is too demanding to pass the test case that checks for 8 queens.

7

I created a cache variable to store previously computed boards which took my runtime from 14 seconds to less than 1 second. All my testcases are successful now.

1 Like