Leetcode 51. N-Queens Explained (Python)

Photo by Ashton Mullins on Unsplash

N-Queens - LeetCode

When initializing the board, don’t “time the first row by four” like this:

[['.'] * self.size] * self.size

strs are immutable. So we can do * self.size to create four dots. But the list itself is mutable. So if we time the list (i.e., the first row) four times, all four rows are pointing to the same instant in memory. That means, later on, if we update the first row, all other rows will take on the same update as well.

Inside put_queen() remember to do a deep copy of the board whenever we move down to the next row. Otherwise, the board for the current solution will spill over to be the board that the next solution is based on.

b = copy.deepcopy(board)

Logic inside is_safe():

1. a Queen has been put in the same column
2. a Queen has been put in the upper left diagonally
3. a Queen has been put in the upper right diagonally

Why only upper? We work down from row#1. No Queen will be in the lower rows yet.

The above solution is the most straightforward solution. At the same time, maintaining a two-dimension board and deep copying every time while we fork to a new solution takes time.

Another solution is to use a one-dimension list to keep track of the Queens placement in terms of the column number. Such as, for a size 4 board, the list [1,3,0,2] refers to a solution that Queens are placed at (0,1), (1,3), (2,0) and (3,2) , or

.Q..
...Q
Q...
..Q.

There is a trick here.

For example, a size 4 board, for(2, 3), one diagonal line is (0, 1), (1, 2). Notice that,

3 - 2 = 1, 1 - 0 = 1, and 2 - 1 = 1

every pair, col - row is the same. Similarly, another diagonal line is (3, 2). Notice that,

2 + 3 = 5, and 3 + 2 = 5

every pair, col + row is the same.

So we have this logic inside is_safe():

if cols[i] == col or \
    cols[i] - i == col - row or \
    cols[i] + i == col + row: