What's wrong in my N-Queens solution?

Question

class Solution:
    def solveNQueens(self, n):
        def n_queens_solver(row, visited_cols, unique_y_intercepts, res):
            if row == n:
                results.append(res)
                return 

            for col in range(n):
                if col not in visited_cols and (row + col) not in unique_y_intercepts and (col - row) not in unique_y_intercepts:
                    visited_cols_dup = visited_cols.copy()
                    unique_y_intercepts_dup = unique_y_intercepts.copy()
                    res_dup = res.copy()

                    visited_cols_dup.add(col)
                    unique_y_intercepts_dup.add(row + col)
                    unique_y_intercepts_dup.add(col - row)
                    this_row = '.' * col + 'Q' + '.' * (n - col - 1)
                    res_dup.append(this_row)

                    n_queens_solver(row + 1, visited_cols_dup, unique_y_intercepts_dup, res_dup)

        results = []
        n_queens_solver(0, set(), set(), [])
        return results

I haven't yet looked at an actual solution for this problem, and I imagine mine is pretty damn inefficient, but I don't know what I'm doing wrong.

Sample input:

n = 4

Correct output:

[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

My output: []

To account for unique diagonals, I figured for every valid place to insert a queen, we need to account for all lines with slope +1 and slope -1. Each of these lines has a unique y-intercept. Using y=x+b and y=-x+b, every potential point to insert a queen has to not have (y-x == b) or (y+x == b).

Anything glaringly incorrect with my rationale here?

Note - I'm not asking for a different or more optimal solution. Am only trying to figure out where my thought process is incorrect.

Answer 1

The mistake in the algorithm is as follows. Look at what happens when you try to mark diagonals as visited.

Let's draw the 4x4 board and assign each cell the number of positive-sloped diagonal it is located on (put i + j on the square located in the row i and col j):

0 1 2 3
1 2 3 4
2 3 4 5
3 4 5 6

Suppose that you put the first queen on the position (1,3). I know that your algorithm starts with row 0, but it doesn't matter in this case. Now the board looks as follows:

0 1 2 3
1 2 3 Q
2 3 4 5
3 4 5 6

Then you add 3 to visited_cols, add 3 + 1 = 4 to y_intercepts and add 3 - 1 = 2 to y_intercepts. We have cols = {3} and y_intercepts = {2,4}. Let's mark with X on the board the diagonal corresponding to the value 2 of y_intercept:

0 1 X 3
1 X 3 Q
X 3 4 5
3 4 5 6

Now suppose we proceed with algorithm to row 2 and we try to put the second queen on square (2,0). This is a valid position because the first queen doesn't attack this square. But your algorithm will reject this position, because row + col = 2 + 0 = 2 is in the y_intercepts set. What happened? We did a positive-slope test for the square (2, 0) and it failed because there was 2 in the y_intercepts set. But note that this 2 was added there after checking the negative-sloped diagonal (remember 3 - 1 = 2 ?). So the tests for positive-sloped and negative-sloped diagonals got mixed which resulted in the incorrect rejection of square (2, 0). This is the reason why your program outputs the empty results vector - at some point of the algorithm there is a row such that all its squares are rejected (some are rejected correctly and others are rejected incorrectly similarly to what we just observed).

One way to fix it is to create two separate sets for positive-sloped diagonals and negative-sloped diagonals and check row + col for positive-sloped ones and col - row for negative ones.