This article originated from personal public account: TechFlow, original is not easy, for attention


Today, in article 32 of LeetCode, we will look at an advanced version of the eight Queens problem — the N Queens problem.

Today’s article corresponds to questions 51 and 52 in LeetCode. The two questions have almost the same topic, they are both queen OF N. The difference is that question 51 requires the placement of all Queen of N, while question 52 only requires the number of all kinds of placement. So we combine these two questions in one article to share.

N Queen problem

N Queen question is a very classic algorithm problem, is also a frequent interview. In the early years, many interviewers liked to test the N-Queen question, essentially to test a candidate’s mastery of recursion and search. Recursion and search can be said to be the basis of algorithms, but also a high-level engineer must master the content. So it’s very important, and even though it shows up less in interviews these days, the essence of the algorithm behind it hasn’t changed.

Let’s go back to the N Queen problem. In chess, the queen is the most powerful. You can walk sideways, you can walk vertically, you can walk diagonally. If we want to put multiple queens on a board, as long as two of them are either in the same row or diagonally, their areas of action are considered to overlap and there is a “conflict.” However, we don’t want this to happen. So, given an N by N chessboard, what are the ways to place n queens on it?


When n=8, it’s the famous eight Queens problem. As we have shared in this post, if you are not familiar with it or are new to it, you can click on the portal below:

Recursion, backtracking, eight queens, all permutations, all in one article

Thought analysis

Eight queens problem has been a platitude, before we discuss the solution, let’s think about a problem, there are many problems solved by recursion or search, why only N queens problem is so classic?

Is it because chess is more popular? Is it because the problem is difficult? Is it clever? Since this question is put forward by myself, there is no relevant answer in the book, we need to think about it by ourselves. Let’s not publish the answer first, with this question to analyze the idea of this problem.

Personally, I like to ask questions when solving problems. In many cases, questions that seem to be vague and confusing can not find the clue, so I may find inspiration by asking a few more questions. If we’re sensitive to numbers, it’s easy to see the big question, why would they ask us to put n queens on an N by N board? Why n, not 2n, not n plus 1?

This question is not difficult to answer, because it is stipulated in the question that queens cannot be placed in the same row, so one queen can be placed at most in each row. There are n rows in total, so obviously, n queens can be placed at most. But if we continue to ask the question, given all these constraints, why do we have to find the answer, do we have n queens that don’t exist? It’s certainly possible, and it’s easy to see that there’s no solution for n equals 2 and 3.


If we follow this line of questioning, we can dig up a lot of questions. For example, what kind of n does it have to have a solution? Is there a pattern for each of these n’s? If all the questions can be answered, the question is thoroughly understood. In fact, there is a very complicated mathematical problem behind this problem, which will be explained in a separate article later.

Although it is possible to solve the problem without going deep into these questions, the gap between thinking and ability is often reflected in these seemingly useless thinking.

So let’s simplify things a little bit, let’s leave the existence of the solution for a second, because since they’re asking us to solve for it, they’re going to give us n that has a solution. And we can make a rough guess and conclude that when n is greater than or equal to 4, the queen of n problem must have a solution. So, how do we solve this?

Problems in modeling

We’re going to have to model the problem. Modeling is a tricky word, it sounds high-end, and it comes up in a lot of scenarios. For example, in machine learning, we need to model, there are special mathematical modeling contests, but few people will explain the word modeling.

After a series of reflections, I personally concluded that the so-called modeling is actually a process of finding and designing solutions to adaptive problems. The model is the logic abstracted from the problem. For example, the placement of queen N is the problem itself, but the logic of the placement method is the model. Models don’t just come out of thin air, we build them little by little. The process is a bit like building blocks, from scratch, from easy to difficult, and gradually perfecting the model.

N by n boards with n queens, that’s the problem, let’s do the first level of abstraction. Obviously, since queens cannot walk or be in the same column as each other, only one queen can be placed in each row and column. We cannot enumerate the rows and columns of a queen at the same time, we give priority to those rows. Let’s make an assumption that since there is no difference between queens, we can assume that the queens in each row are fixed. The first queen is placed in the first row, and the second queen in the second row.


After the first level of abstraction, the question becomes much clearer, but the answer remains elusive. Therefore, we also need to do the second level of abstraction and analysis. Fixing a queen in each row can guarantee that there will be no conflicts between queens, but it cannot guarantee that different columns and diagonals will be different. So we have to design a mechanism to guarantee that. We need to enumerate all the positions of the queen, so we can no longer fix the columns of the queen, since we can’t fix them, but we can record them. Since we have identified each row where the queen is placed, we can determine whether they form the same column and the same diagonal by recording the columns where they are placed.

So here we have the solution, but we can do a third level of abstraction. Since the queen already has a fixed line number, we can replace the queen with a subscript in the array. The location of subscript 0 is the column number of queen 0, 0 is the row number of Queen 0, so we use a one-dimensional array to store the two-dimensional information of queen 0.


So when we recurse, we just record the whole checkerboard in one array, which is a lot easier to do in code.

# code for leetcode 51

class Solution:

    

    def dfs(self, n, queen, ret):

        if len(queen) == n:

            ret.append(queen[:])

            return 

        

        for i in range(n):

            # if same column

            if i in queen:

                continue

            flag = False

            # Determine if there are diagonal lines

            for j, idx in enumerate(queen):

                # len(queen) indicates the current number of queens

                if abs(len(queen) - j) == abs(idx - i):

                    flag = True

                    break

            if flag:

                continue

            If it is valid, put it in column I

            queen.append(i)

            self.dfs(n, queen, ret)

            queen.pop()

            

    def transform(self, n, ret):

        res = []

        Restore the checkerboard according to the column number of each queen

        for arr in ret:

            s = []

            for i, idx in enumerate(arr):

                row = ['. ' for _ in range(n)]

                row[idx] = 'Q'

                s.append(' '.join(row))

            res.append(s)

        return res

        

    def solveNQueens(self, n: int) -> List[List[str]]:

        ret = []

        self.dfs(n, [], ret)

        return self.transform(n, ret)

Copy the code

conclusion

And finally, let’s go back to the original question, why are there so many recursively solved problems, and only queen N is a classic?

One of the reasons that I think is very important is the modeling process of this problem. We started from scratch, pieced together the whole problem, and built a model suitable for the current problem. And after our optimization, it is also the best model to implement recursively. For us, it is not important to AC the problem, but to master the ability to construct the idea, so that we can easily migrate to other problem scenarios. This is the essence of learning.

In a joke, the way LeetCode changed the title slightly to make it a new title is…

Today’s article is all of these, if you feel that there is a harvest, please feel free to point attention or forward, your help is very important to me.