The "N-Queen Problem" from The Whispered World

queens.js

/**
 * Helper function: Creates a "range array" from 0 to n-1
 *
 * @param  {number} n Number of elements in range array
 * @return {Array}    The range array
 */
const range = n => [...Array(n+1).keys()].slice(1);

/**
 * Helper function: returns a random number between min and max
 *
 * @param  {number} min The minimum
 * @param  {number} max The maximum
 * @return {number}     The random number
 */
const random = (min, max) => Math.floor(Math.random() * (max - min + 1) + min);

/**
 * Helper function: Dumps a solution to the console
 *
 * @param  {Array} solution An array containing a solution
 */
const showSolution = solution => {
  const size = solution.length;
  const board = range(size).map(row => {
    return range(size)
      .map(c => solution[row-1] == c ? '♕' : '∙')
      .join(' ')
    ;
  }).join("\n");

  console.log(board);
}

/**
 * Checks if a queen may be put on specific column
 *
 * @param  {number}  col   The column
 * @param  {number}  n     The size of the board
 * @param  {Array}   board The current "board" so far
 * @return {Boolean}       True if valid, false if invalid
 */
const isValidColumn = (col, n, board) => {
  // empty board
  if (!board.length) {
    return true;
  }

  // sanity check
  if (col < 0) {
    return false;
  }

  // column already taken?
  if (board.indexOf(col) >= 0) {
    return false;
  }

  // check left diag
  if (col > 0) {
    for (i = 0; i < n; i++) {
      if (board[i] == col-i-1) {
        return false;
      }
    }
  }

  // check right diag
  if (col < n) {
    for (i = 0; i < n; i++) {
      if (board[i] == col+i+1) {
        return false;
      }
    }
  }

  return true;
}

/**
 * Adds a new queen to column
 *
 * @param {number} col               The column
 * @param {Array}  previousSolutions Previous solutions
 */
const addQueenToBoard = (col, previousSolutions) => {
  return previousSolutions.reduce((acc, solution) => {
    const ret = range(col)
      .filter(c => isValidColumn(c, col, solution))
      .map(c => [c, ...solution]);

    return acc.concat(ret);
  }, []);
}

/**
 * Start the algorithm
 *
 * @param  {number} rows The number of rows
 * @param  {number} cols The number of colums
 * @return {Array}       An array containing all solutions
 */
const queensProblem = (rows, cols) => {
  if (rows <= 0) {
    return [[]];
  }

  return addQueenToBoard(cols, queensProblem(rows-1, cols));
}

/**
 * B R I N G  D E M  Q U E E N S  !
 */

const size = 8;
const solutions = queensProblem(size, size);
const numSolutions = solutions.length || 0;
if (numSolutions == 0) {
  console.log(`There are no solutions for ${size}x${size}`);
  process.exit();
}

console.log(`There are ${numSolutions} solutions for ${size}x${size}`);
console.log('Here\'s a random solution');

showSolution(solutions[random(1, numSolutions)-1]);

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n=2 and n=3.

Source: Wikipedia

For context: https://twitter.com/b00giZm/status/899750686933569540 🤓