Skip to content

Instantly share code, notes, and snippets.

@jesterswilde
Created September 14, 2015 05:51
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jesterswilde/dcc061877f9c8948e36b to your computer and use it in GitHub Desktop.
Save jesterswilde/dcc061877f9c8948e36b to your computer and use it in GitHub Desktop.
nQuees with Comments
findNQueens = function(nSize){
//make an array, and fill it with ordered numbers to n
var rows = [];
// rows will have 0 - n pushed to it, non inclusive
for (var i = 0; i < n; i++){
rows.push(i);
}
// final array that gets returned
var results = [];
// storage for what we currently have
var storage = [];
// now define recursive function call
var comboBreaker = function(rowsArray, colIndex, majorDiagonalsArray, minorDiagonalsArray){
// base case, if rowsArray is empty
if (rowsArray.length === 0){
// push a copy of storage into results
results.push(storage.slice());
}
// loop over rowsArray
for (var j = 0; j < rowsArray.length; j++){
//major index = r + c
var majorIndex = rowsArray[j] + colIndex;
//minor index = r - c + size - 1
var minorIndex = rowsArray[j] - colIndex + obj['rows'].length - 1;
// if this is not a previously existing major diagonal AND if this is not a previously existing minor diagonal
if (!(majorDiagonalsArray[majorIndex]) && !(minorDiagonalsArray[minorIndex])) {
// mark the major and minor as taken, but on copies
var copyOfMajor = majorDiagonalsArray.slice();
copyOfMajor[majorIndex] = true;
var copyOfMinor = minorDiagonalsArray.slice();
copyOfMinor[minorIndex] = true;
// push current row and column into storage, this is the current spot picked
storage.push([rowsArray[j], colIndex]);
// remove the jth element from a copy of the array
var copyRowsArray = rowsArray.slice();
copyRowsArray.splice(j, 1);
// recursive call picks the next spot
comboBreaker(copyRowsArray, colIndex + 1, copyOfMajor, copyOfMinor);
storage.pop();
}
}
};
// initiate comboBreaker
comboBreaker(rows, 0, [], []);
// results is an array of all solutions
return results;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment