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

Python
1

Tell us what’s happening:

My approach is that I will perform start at each possible column in my first row, after placing a 1 in the first row I will populate all the affect nodes by that queen before DFS’ing to find the next available empty node, in the next level , but as I am writing this code my gut says I am over complicating my solution and I could maybe solve this in a neater way. Is my approach sound or should I be looking at the problem in a different way?

Your code so far

def dfs_n_queens(n:int):
    if not isinstance(n, int):
        print("Input must be an integer")
        return
    if n < 1 :
        print("Input must be 1 or greater")
        return

    board = [[0 for _ in range(n)] for _ in range(n)]
    print(board)
    
    def attkd_squares(loc, matrix):
        row,col = loc
        
        #fill vertical
        for i in range(len(matrix)):
            matrix[i][col] = 1
        #fill horizontal
        for i in range(len(matrix)):
            matrix[row][i] = 1
        #diagonals
        ##to do

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/143.0.0.0 Safari/537.36 Edg/143.0.0.0

Challenge Information:

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

2

If I understand you correctly. You want to verify if certain field (candidate for next node to visit) isn’t already ruled out? That doesn’t sound like complicating things. At some point such check is needed anyway - either when nodes are discovered, or when they are visited.

3

Thanks for your steer, having looked a bit further into the problem I think my gut was trying to tell me writing to code to fill all rows affected by the placed queen with 1’s might not be needed as it’s more about questioning the current row/column/previous diagonals and ignoring undiscovered rows/levels for until they are explored