{"size": 1157, "ext": "js", "max_stars_repo_path": "more-like-interview-questions/queens-x8.js", "max_stars_repo_name": "hchiam/javascriptSandbox", "max_stars_repo_stars_event_min_datetime": "2019-09-22T21:59:19.000Z", "max_stars_repo_stars_event_max_datetime": "2019-09-22T21:59:19.000Z", "max_issues_repo_path": "more-like-interview-questions/queens-x8.js", "max_issues_repo_name": "hchiam/javascriptSandbox", "max_issues_repo_issues_event_min_datetime": "2021-11-11T22:51:38.000Z", "max_issues_repo_issues_event_max_datetime": "2022-03-29T22:39:48.000Z", "max_forks_repo_path": "more-like-interview-questions/queens-x8.js", "max_forks_repo_name": "hchiam/learning-js", "max_forks_repo_forks_event_min_datetime": null, "max_forks_repo_forks_event_max_datetime": null}
{"max_stars_count": 1, "max_issues_count": 3, "max_forks_count": null, "avg_line_length": 22.6862745098, "max_line_length": 86, "alphanum_fraction": 0.5756266206}
// to run this file: node queens-x8.js

// CtCI, 6th ed., ch. 8 q. 8.12

const GRID_SIZE = 8;
const results = [];

// for (let c = 0; c < 8; c++) {
//   console.log(valid([1], 1, c), `c = ${c}`);
// }
queens8(0, [], results);
const numberOfResults = results.length;

console.log(results);
console.log(
  `\nShould have 92 results. Found ${numberOfResults}. ${
    numberOfResults === 92
  }!`
);

function queens8(r, cols, res) {
  if (r === GRID_SIZE) {
    res.push(clone(cols));
  } else {
    for (let c = 0; c < GRID_SIZE; c++) {
      if (valid(cols, r, c)) {
        cols[r] = c;
        const nextRow = r + 1;
        queens8(nextRow, cols, res);
      }
    }
  }
}

function clone(cols) {
  return [...cols];
}

function valid(cols, r, c) {
  for (let rPrev = 0; rPrev < r; rPrev++) {
    const cPrev = cols[rPrev];
    const isSameCol = cPrev === c;
    if (isSameCol) return false;
    const colDist = Math.abs(c - cPrev);
    const rowDist = r - rPrev; // no need for absolute value, assuming going down rows
    const isSameDiag = colDist === rowDist;
    if (isSameDiag) return false;
  } // checked all previous rows' cells
  return true;
}
