Gayan Hewa
PHANTOM DEV

PHANTOM DEV

Backtracking with N Queens

Backtracking with N Queens

Subscribe to my newsletter and never miss my upcoming articles

Backtracking with N Queens

07 Sep 2021 | 6 min read

What is a backtracking problem?

Backtracking is a general algorithm for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. (Source)

The N-Queens problem is a common problem used to explain the backtracking algorithms. It's straightforward and easy to understand. Here is a link to the problem on leetcode

The problem is defined as given n is a positive integer, derive the possible placement of n queens in a n x n chessboard such that no queens are attacking each other.

Arriving at a solution

The reason why we use backtracking is problems like these require you to run through all possible placements in order to figure out the placements.

For an instance for a 8 x 8 chessboard placing 8 queens has a staggering 4,426,165,368 (possibilities and only 92 valid placements. Attacking this problem with a brute-force approach would require too much computation to effectively solve this problem.

Backtracking allows you to reduce the possibilities by applying constraints, this helps reduce the number of possibilities really quickly. The first two constraints we add are no queens will be placed in the same column/row. This is a simple enough condition clear to anyone who understands the basic semantics of chess. This reduces the number of available permutations to 8! = 40,320 Next, we introduce the diagonal constraints and this gets further reduced.

  1. Attempt to solve one row at a time
    1. For each column in the row attempt to place the queen
      1. Check if the move is a valid move
      2. Explore the next row
      3. If the move is not valid discard the current solution
    2. Once we have reached the end of the rows store/print the result

From the pseudo solution explained, we can extrapolate that the solution we will write is going to contain 3 parts

  1. A list of solved boards
  2. A method to solve each row
  3. A method to check if a given move is valid

Let's start with checking the validity of a move. Since we understand the boundary conditions this is easy to explain.

// The inputs are the row and column of the new placement
// currentMoves represent an array of valid moves placed so far.
// newMove : { row: int, col: int }
// currentMoves Shape -> [{ row: int, col: int }]
function isValid(newMove, currentMoves) {
    for(let index = 0; index < currentMoves.length; index++) {
        // Lets check if currentMoves have anything placed in the same row/column
        if (currentMoves[index].row === newMove.row || 
                currentMoves[index].col === newMove.col) 
        {
          return false;
    }

         // Since the chessboard is like a matrix we will use 
     // Slope of a line formula to check if any of the existing
     // moves are placed in the same line.
     // slope = rise / run
     // When the slope is either -1 or +1 the items are diagnally attacking
       let slope = (newMove.row-currentMove[index].row) / (newMove.col-currentMove[index].col)

     // Using Math.abs so I can just check for 1 without having two parts for the 
     // if condition. Math.abs returns the positive value for an integer. 
     if (Math.abs(slope) == 1) {
             return false;
         }
  }

  return true;  
}

For those of you who want to clarify how the slope calculation works, you can find it here.

Next, let's discuss how we solve the board. Solving the whole board at once is hard so we are going to solve one row at a time to make it easier for us to understand and code. Basically what we want to do is go through all the possible combinations first.

// row : starting row
// n : number of queens
function solve(row, n) {

  if (row === n) {
    // we have a solution.
    return;
  }

    for(let col=0; col < n; col++) {
    // I am ignoring the currentMoves for the moment.
    if (isValid(row, col) && solve(row+1, n) {
            return;
      }
  }    
}

The code above might look a bit intimidating at first. But what we are trying to do here is, when the method solve(0,8) is invoked it will iterate through each column in the grid for that row. Check if the move isValid and if it's valid it will go to the next row. Why does it go to the next row? It's because you can only have one Queen in a single row. The attack radius for a queen spans across the whole row/column.

Next, the code block if (row === n) is the exit condition for the recursive function call. These problems are inherently complicated. Time complexity of this problem is O(n^n) we can only improve the complexity by adding the constraints, so it's better than the brute-force approach of trying out every possible combination.

// row : int
// validMoves: [{ row: int, col: int }]
// n is defined outside this function. So bear with me for a few moments.
function solve(row, validMoves) {
  if (row === n) {
        // At this point we can decide on how we want to produce the final result.
      // If a particular function reachers this point, it has succesfully iterated 
    // Through all the rows, and gather all the valid moves. 
    return;
  }

    for(let col=0; col < n; col++) {

        // This is the new move we are going to check.
        let newMove = { row, col };

        // Adding the new move to the list of valid new moves
        let newMoves = validMoves.push(newMove);

    if (isValid(newMove, validMoves) && 
                // The recursive call, we set the row to the next one
        // And send the newMoves as validMoves to the subsequent calls.
        // That is ok, because the 2nd part of the if condition only executes
        // if the first part is true. 
                solve(row+1, newMoves) 
        {
            return;
      }

        // Crap, the move is not valid. 
    newMove.pop();
  }    
}

So here is a complete solution, you can save and execute this file with node n-queens.js

'use strict';

function solveNQueens(n) {
    const boards = [];

    // The inputs are the row and column of the new placement
    // currentMoves represent an array of valid moves placed so far.
    // newMove : { row: int, col: int }
    // currentMoves Shape -> [{ row: int, col: int }]
    const isValid = (newMove, currentMoves) => {
        for(let index = 0; index < currentMoves.length; index++) {
            // Lets check if currentMoves have anything placed in the same row/column
            if (currentMoves[index].row === newMove.row ||
                    currentMoves[index].col === newMove.col)
            {
            return false;
        }

            // Since the chessboard is like a matrix we will use
        // Slope of a line formula to check if any of the existing
        // moves are placed in the same line.
        // slope = rise / run
        // When the slope is either -1 or +1 the items are diagonally attacking
        let slope = (newMove.row-currentMoves[index].row) / (newMove.col-currentMoves[index].col)

        // Using Math.abs so I can just check for 1 without having two parts for the
        // if condition. Math.abs returns the positive value for an integer.
        if (Math.abs(slope) == 1) {
                return false;
            }
        }

        return true;
    }

    // row : int
    // validMoves: [{ row: int, col: int }]
    // n is defined outside this function. So bear with me for a few moments.
    const solve = (row, validMoves = []) => {
        if (row === n) {
            // Init an empty board.
            let board = [];
            for (let i = 0; i < n; i++) {
                board[i] = [];
                for (let j = 0; j < n; j++) {
                    board[i][j] = '.';
                }
            }

            // At this point we can decide on how we want to produce the final result.
            // If a particular function reachers this point, it has successfully iterated
            // Through all the rows, and gather all the valid moves.
            validMoves.forEach(move => {
                board[move.row][move.col] = 'Q';
            });

            boards.push(board);

            return;
        }

        for(let col=0; col < n; col++) {

            // This is the new move we are going to check.
            let newMove = { row, col };

            // Adding the new move to the list of valid new moves
            let newMoves = [...validMoves, newMove];

            if (isValid(newMove, validMoves) &&
            // The recursive call, we set the row to the next one
            // And send the newMoves as validMoves to the subsequent calls.
            // That is ok, because the 2nd part of the if condition only executes
            // if the first part is true.
            solve(row+1, newMoves))
            {
                return;
            }

            // Crap, the move is not valid.
            newMoves.pop();
        }
    }

    solve(0);

    return boards;
}

In conclusion, n Queen's problems give a way to explore backtracking. For me, I personally find backtracking problems interesting. Understanding this took me some time, had to watch a couple of videos and introductions. Read a few blog posts. It's not like I magically understood this. I was never thought of this in school.

The next step for me is to explore a few medium problems in Backtracking before trying out the hard problems. You can find a good amount of problems in leetcode

Resources:

https://www.youtube.com/watch?v=DKCbsiDBN6c&t=5s

https://www.youtube.com/watch?v=Zq4upTEaQyM&t=510s

https://www.youtube.com/watch?v=Nabbpl7y4Lo

https://leetcode.com/tag/backtracking/

#nodejs #depth first search #n-queens #backtracking #algorithms

Maximum Sub-array Problem →

 
Share this