One Pager Cheat Sheet

• You should design an N-Queen problem solver that can place n queens on a n x n square board in a way that no queen is in a mutual attacking position, with a minimum value of n = 4 and a maximum value of n = 100, in O(n^2) time and O(n) space complexity.
• We need to use a backtracking algorithm to solve the NP-Complete 8-Queen problem due to its large search space ruling out a naive brute force solution.
• A Board Validation Function is used to check if we can place a Queen in a cell of the board by looping through the rows and checking if there is a Queen in the same column, and by checking if a Queen appears in the first and second diagonals by observing the row and col variables in a loop.
• We will returnTrue if a Queen is validly placed at a given row and col position.
• We will start from the first element in the board and attempt to place Queens, incrementing the row until row is greater than n, at which point a solution is found and the board is saved for further backtracking.
• The algorithm will recursively evaluate row-by-row for valid positions to place the Queen and add each solution to a list of results before backtracking to the next feasible place.
• We will create a board by multiplying a string of size n and duplicating it n times, then start the backtracking process at row=0 and col=0.
• We will recursively select Queen positions and build up the solution list, res, with a time complexity of O(n^2) and space complexity of board size times res.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function solveNQueens(n) {

  var board = new Array(n);

  // Setup thhe board

  for (i = 0; i < n; i++) {

    board[i] = new Array(n);

    for (j = 0; j < n; j++) {

      board[i][j] = '.';

    }

  }

​

  res = recursiveSolveNQueens([], board, 0);

  console.log('board', res);

  return res;

}

​

function copyBoard(board) {

  let newBoard = new Array(board.length);

  for (i = 0; i < board.length; i++) {

    newBoard[i] = new Array(board[i].length);

    for (j = 0; j < board[i].length; j++) {

      newBoard[i][j] = board[i][j];

    }

  }

  return newBoard;

}

​

function recursiveSolveNQueens(res, board, row, cols = []) {

  if (row === board.length) {

    // A solution! add a copy of it

    res.push(copyBoard(board));

That's all we've got! Let's move on to the next tutorial.

If you had any problems with this tutorial, check out the main forum thread here.