The title

The n Queens problem is the study of how to place n queens on an n by n board so that queens cannot attack each other. Given an integer n, return the number of different solutions to the queen of N problem.

Rule of queen’s move

The queen’s way of walking is: can walk horizontally and diagonally, the number of grids is not limited. So asking queens not to attack each other is equivalent to asking no two queens to be on the same row, column, and slash.

The sample

Example 1:

Enter n =4Output:2
Copy the code

Explanation: As shown in the figure above, there are two different solutions to the four queens problem.

Example 2:

Enter n =1Output:1
Copy the code

Tip: 1 <= n <= 9

Train of thought

  1. Define a test function to determine the current position, with constraints such as, not in a row, not in a column, not in a diagonal (45 degrees and 135 degrees)
  2. Define checkerboard; Standard backtracking;

Backtracking is used by placing a queen in each row in turn, with each newly placed queen having no attacks on the already placed queen, i.e., the newly placed queen cannot be in the same column and on the same slash as any already placed queen. When NNN queens are all placed, a possible solution is found and the number of possible solutions is added to 111.

photo

The problem solving code

var totalNQueens = function (n) {
    let count = 0; // Total number of queens that can be placed
    let isValid = (row, col, board, n) = > {
        // It moves down one line at a time
        // Check whether the same column contains data
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') {
                return false}}// Check whether the 45 degree diagonal is included
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') {
                return false}}// Check whether the 135 degree diagonal contains
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; j--, i--) {
            if (board[i][j] === 'Q') {
                return false}}return true
    }

    let backTracing = (row, board) = > {
        // Go to the last row, count the number of times
        if (row === n) {
            count++;
            return
        }

        for (let x = 0; x < n; x++) {
            // Determine if this position is suitable for the queen
            if (isValid(row, x, board, n)) {
                board[row][x] = 'Q'; // Place the queen
                backTracing(row + 1, board); / / recursion
                board[row][x] = '. '; // Backtrace, undo the result of processing
            }
        }
    }
    backTracing(0, board)
    let board = [...Array(n)].map(v= > v = ([...Array(n)]).fill('. ')) / / board
    return count
};
Copy the code

conclusion

The backtracking algorithm is mainly used. To solve a backtracking problem is actually a decision tree traversal process.

let backtracking=(Path, select list) = >{
    if(End condition satisfied) {store path;return;
    }
    for(Select: path, select list) {make a selection; Backtracking (path, select list);/ / recursionBacktrace, undo processing result}}Copy the code

That is:

  1. 1. Path: The choices already made.
  2. 2. Selection list: The choices you can currently make.
  3. 3. End condition: that is, the condition when you reach the bottom of the decision tree and can no longer make a choice.

Pruning function

  1. 1. Use constraints to cut off the subtree of viable solutions that cannot be obtained
  2. 2. Use the objective function to cut the subtree of the optimal solution that cannot be obtained

The general steps of backtracking:

  1. 1. Set the initialization scheme (assign initial values to variables, read known data, etc.)
  2. 2. Change the way to test. If all the tests are finished, turn to the side (7)
  3. 3. Judge whether this method is successful (by constraint function), if not, go to (2)
  4. 4. Try again before you succeed
  5. 5. If the correct scheme is not found, go to (2)
  6. 6. To find a solution to record and print
  7. 7. Step back (backtrack), if not back to the end, turn (2)
  8. 8. If it has retreated to the end, it will end or print no solution

Progress every day, continue to come on!