The title

Title source: N Queen – force buckle

Analysis of the

The prototype for this problem is the famous eight Queens problem, and in fact, it’s hard to find a good way to deal with it, except for enumerating violence. When it comes to violence enumeration, backtracking algorithm can be said to be a very good method, so here we use the perspective of backtracking to think about how to complete the problem.

Here’s an example of a 4 x 4 checkerboard:

The first thing to know is the queen’s range of attack:

  • peer
  • The same column
  • Same diagonal

Taking coordinate [1, 1], i.e. position 2 as an example, the queen’s attack range is shown in the figure:

What are the characteristics of these attack range cells (let’s say row, column COL)?

  • rowequal
  • colequal
  • row + colequal
  • row - colequal

Combined with the above points, we can try to traverse the map and find locations that cannot be accessed:

function find(row, chessboard = []) {
  for (let col = 0; col < n; col++) {
    const cantSet = chessboard.some((ci, ri) = > 
		  ri === row || ci === col || ri - ci === row - col || ri + ci === row + col
    );
    if (cantSet) continue;
    find(row + 1, [...chessboard, col]); }}Copy the code

Notable among them are:

  • chessboardIndex values are rows and values are columns
  • ci, riIt’s the line where the pieces were placed before
  • col, rowIs the index of the current location

How does the above code accomplish traceback?

In fact, it is not difficult to find carefully that when all the positions are not down, the loop will directly end and go back to the previous layer, that is, to complete the backtracking. You can print out the specific value to see.

When you find that all the positions in the second line can not be downloaded, the program goes back to the previous line and continues to try. At this stage, the whole search is basically completed, and then you need to set the termination condition, relatively speaking, this is relatively simple:

  • When does it stop? Nature isrow === nWhen, because inrow === (n - 1)You’re already looking for the last row.

It is also easy to terminate the checkerboard by converting it to a standard form and pushing it into the result set:

if (row === n) {
  result.push(
    chessboard.map(c= > {
      let arr = new Array(n).fill(".");
      arr[c] = "Q";
      return arr.join(""); })); }Copy the code

Finally, return the result set:

var solveNQueens = function (n) {
  const result = [];
  find(0);
  return result;
};
Copy the code

The results are as follows: