NQueens.js

/* 
NQueens
https://leetcode.com/problems/n-queens/description/

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
*/    


/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
  var sol = [];
  solveNQueensAux(n, 0, new Set(), new Set(), new Set(), [], sol);
  return parseSolutions(sol, n);
};

var solveNQueensAux = function(n, row, diagonalDiffs, diagonalSums, cols, currentSol, sol) {
  if(row == n) { 
    sol.push(currentSol);  
    return; 
  }
  
  for(var i = 0; i < n; i++) {
    const diagonalDiff = i - row;
    const diagonalSum = i + row;
    if(!diagonalDiffs.has(diagonalDiff) && !cols.has(i) && !diagonalSums.has(diagonalSum)) {
      diagonalDiffs.add(diagonalDiff);
      diagonalSums.add(diagonalSum);
      cols.add(i);
      solveNQueensAux(n, row + 1, diagonalDiffs, diagonalSums, cols, [...currentSol, ...[[row, i]]], sol);
      cols.delete(i);
      diagonalDiffs.delete(diagonalDiff);
      diagonalSums.delete(diagonalSum);
    }
  }
}

var parseSolutions = function(sols, n) {
  var matrixes = [];
  for(var i = 0; i < sols.length; i++) {
    var sol = sols[i];
    var matrix = [];
    for(var row = 0; row < n; row++) {
      matrix[row] = []
      const queenPos = sol[row];
      for(var col = 0; col < n; col++) {
        matrix[row] += (queenPos[1] == col) ? "Q" : ".";
      }
    }

    matrixes.push(matrix);
  }

  return matrixes;
}

module.exports.solveNQueens = solveNQueens;