N-Queens Problem

{ 0,  1,  0,  0}
{ 0,  0,  0,  1}
{ 1,  0,  0,  0}
{ 0,  0,  1,  0}

while there are untried configurations
{
   generate the next configuration
   if queens don't attack in this configuration then
   {
      print this configuration;
   }
}

1) Start in the leftmost column
2) If all queens are placed
    return true
3) Try all rows in the current column.  Do following for every tried row.
    a) If the queen can be placed safely in this row then mark this [row, 
        column] as part of the solution and recursively check if placing  
        queen here leads to a solution.
    b) If placing queen in [row, column] leads to a solution then return 
        true.
    c) If placing queen doesn't lead to a solution then unmark this [row, 
        column] (Backtrack) and go to step (a) to try other rows.
3) If all rows have been tried and nothing worked, return false to trigger 
    backtracking.

/**
 * Class that represents queen position on the chessboard.
 */
export default class QueenPosition {
  /**
   * @param {number} rowIndex
   * @param {number} columnIndex
   */
  constructor(rowIndex, columnIndex) {
    this.rowIndex = rowIndex;
    this.columnIndex = columnIndex;
  }

  /**
   * @return {number}
   */
  get leftDiagonal() {
    // Each position on the same left (\) diagonal has the same difference of
    // rowIndex and columnIndex. This fact may be used to quickly check if two
    // positions (queens) are on the same left diagonal.
    // @see https://youtu.be/xouin83ebxE?t=1m59s
    return this.rowIndex - this.columnIndex;
  }

  /**
   * @return {number}
   */
  get rightDiagonal() {
    // Each position on the same right diagonal (/) has the same
    // sum of rowIndex and columnIndex. This fact may be used to quickly
    // check if two positions (queens) are on the same right diagonal.
    // @see https://youtu.be/xouin83ebxE?t=1m59s
    return this.rowIndex + this.columnIndex;
  }

  toString() {
    return `${this.rowIndex},${this.columnIndex}`;
  }
}

import QueenPosition from './QueenPosition';

/**
 * @param {QueenPosition[]} queensPositions
 * @param {number} rowIndex
 * @param {number} columnIndex
 * @return {boolean}
 */
function isSafe(queensPositions, rowIndex, columnIndex) {
  // New position to which the Queen is going to be placed.
  const newQueenPosition = new QueenPosition(rowIndex, columnIndex);

  // Check if new queen position conflicts with any other queens.
  for (let queenIndex = 0; queenIndex < queensPositions.length; queenIndex += 1) {
    const currentQueenPosition = queensPositions[queenIndex];

    if (
      // Check if queen has been already placed.
      currentQueenPosition
      && (
        // Check if there are any queen on the same column.
        newQueenPosition.columnIndex === currentQueenPosition.columnIndex
        // Check if there are any queen on the same row.
        || newQueenPosition.rowIndex === currentQueenPosition.rowIndex
        // Check if there are any queen on the same left diagonal.
        || newQueenPosition.leftDiagonal === currentQueenPosition.leftDiagonal
        // Check if there are any queen on the same right diagonal.
        || newQueenPosition.rightDiagonal === currentQueenPosition.rightDiagonal
      )
    ) {
      // Can't place queen into current position since there are other queens that
      // are threatening it.
      return false;
    }
  }

  // Looks like we're safe.
  return true;
}

/**
 * @param {QueenPosition[][]} solutions
 * @param {QueenPosition[]} previousQueensPositions
 * @param {number} queensCount
 * @param {number} rowIndex
 * @return {boolean}
 */
function nQueensRecursive(solutions, previousQueensPositions, queensCount, rowIndex) {
  // Clone positions array.
  const queensPositions = [...previousQueensPositions].map((queenPosition) => {
    return !queenPosition ? queenPosition : new QueenPosition(
      queenPosition.rowIndex,
      queenPosition.columnIndex,
    );
  });

  if (rowIndex === queensCount) {
    // We've successfully reached the end of the board.
    // Store solution to the list of solutions.
    solutions.push(queensPositions);

    // Solution found.
    return true;
  }

  // Let's try to put queen at row rowIndex into its safe column position.
  for (let columnIndex = 0; columnIndex < queensCount; columnIndex += 1) {
    if (isSafe(queensPositions, rowIndex, columnIndex)) {
      // Place current queen to its current position.
      queensPositions[rowIndex] = new QueenPosition(rowIndex, columnIndex);

      // Try to place all other queens as well.
      nQueensRecursive(solutions, queensPositions, queensCount, rowIndex + 1);

      // BACKTRACKING.
      // Remove the queen from the row to avoid isSafe() returning false.
      queensPositions[rowIndex] = null;
    }
  }

  return false;
}

/**
 * @param {number} queensCount
 * @return {QueenPosition[][]}
 */
export default function nQueens(queensCount) {
  // Init NxN chessboard with zeros.
  // const chessboard = Array(queensCount).fill(null).map(() => Array(queensCount).fill(0));

  // This array will hold positions or coordinates of each of
  // N queens in form of [rowIndex, columnIndex].
  const queensPositions = Array(queensCount).fill(null);

  /** @var {QueenPosition[][]} solutions */
  const solutions = [];

  // Solve problem recursively.
  nQueensRecursive(solutions, queensPositions, queensCount, 0);

  return solutions;
}

/**
 * Checks all possible board configurations.
 *
 * @param {number} boardSize - Size of the squared chess board.
 * @param {number} leftDiagonal - Sequence of N bits that show whether the corresponding location
 * on the current row is "available" (no other queens are threatening from left diagonal).
 * @param {number} column - Sequence of N bits that show whether the corresponding location
 * on the current row is "available" (no other queens are threatening from columns).
 * @param {number} rightDiagonal - Sequence of N bits that show whether the corresponding location
 * on the current row is "available" (no other queens are threatening from right diagonal).
 * @param {number} solutionsCount - Keeps track of the number of valid solutions.
 * @return {number} - Number of possible solutions.
 */
function nQueensBitwiseRecursive(
  boardSize,
  leftDiagonal = 0,
  column = 0,
  rightDiagonal = 0,
  solutionsCount = 0,
) {
  // Keeps track of the number of valid solutions.
  let currentSolutionsCount = solutionsCount;

  // Helps to identify valid solutions.
  // isDone simply has a bit sequence with 1 for every entry up to the Nth. For example,
  // when N=5, done will equal 11111. The "isDone" variable simply allows us to not worry about any
  // bits beyond the Nth.
  const isDone = (2 ** boardSize) - 1;

  // All columns are occupied (i.e. 0b1111 for boardSize = 4), so the solution must be complete.
  // Since the algorithm never places a queen illegally (ie. when it can attack or be attacked),
  // we know that if all the columns have been filled, we must have a valid solution.
  if (column === isDone) {
    return currentSolutionsCount + 1;
  }

  // Gets a bit sequence with "1"s wherever there is an open "slot".
  // All that's happening here is we're taking col, ld, and rd, and if any of the columns are
  // "under attack", we mark that column as 0 in poss, basically meaning "we can't put a queen in
  // this column". Thus all bits position in poss that are '1's are available for placing
  // queen there.
  let availablePositions = ~(leftDiagonal | rightDiagonal | column);

  // Loops as long as there is a valid place to put another queen.
  // For N=4 the isDone=0b1111. Then if availablePositions=0b0000 (which would mean that all places
  // are under threatening) we must stop trying to place a queen.
  while (availablePositions & isDone) {
    // firstAvailablePosition just stores the first non-zero bit (ie. the first available location).
    // So if firstAvailablePosition was 0010, it would mean the 3rd column of the current row.
    // And that would be the position will be placing our next queen.
    //
    // For example:
    // availablePositions = 0b01100
    // firstAvailablePosition = 100
    const firstAvailablePosition = availablePositions & -availablePositions;

    // This line just marks that position in the current row as being "taken" by flipping that
    // column in availablePositions to zero. This way, when the while loop continues, we'll know
    // not to try that location again.
    //
    // For example:
    // availablePositions = 0b0100
    // firstAvailablePosition = 0b10
    // 0b0110 - 0b10 = 0b0100
    availablePositions -= firstAvailablePosition;

    /*
     * The operators >> 1 and 1 << simply move all the bits in a bit sequence one digit to the
     * right or left, respectively. So calling (rd|bit)<<1 simply says: combine rd and bit with
     * an OR operation, then move everything in the result to the left by one digit.
     *
     * More specifically, if rd is 0001 (meaning that the top-right-to-bottom-left diagonal through
     * column 4 of the current row is occupied), and bit is 0100 (meaning that we are planning to
     * place a queen in column 2 of the current row), (rd|bit) results in 0101 (meaning that after
     * we place a queen in column 2 of the current row, the second and the fourth
     * top-right-to-bottom-left diagonals will be occupied).
     *
     * Now, if add in the << operator, we get (rd|bit)<<1, which takes the 0101 we worked out in
     * our previous bullet point, and moves everything to the left by one. The result, therefore,
     * is 1010.
     */
    currentSolutionsCount += nQueensBitwiseRecursive(
      boardSize,
      (leftDiagonal | firstAvailablePosition) >> 1,
      column | firstAvailablePosition,
      (rightDiagonal | firstAvailablePosition) << 1,
      solutionsCount,
    );
  }

  return currentSolutionsCount;
}

/**
 * @param {number} boardSize - Size of the squared chess board.
 * @return {number} - Number of possible solutions.
 * @see http://gregtrowbridge.com/a-bitwise-solution-to-the-n-queens-problem-in-javascript/
 */
export default function nQueensBitwise(boardSize) {
  return nQueensBitwiseRecursive(boardSize);
}