N-Queen with Backtrack

nQueenBT.js

function printBoard(board, method = "log") {
  console[method](board.map((e) => e.join("")).join("\n"));
}

function createDiagonalMatrix(_) {
  _.takenDiagonal = [];
  _.diagonalMatrix = new Array(_.n).fill().map(() => new Array(_.n).fill(-1));

  // first row
  for (let y = 0; y < _.n; y++) {
    for (let x = 0; x < _.n; x++) {
      _.takenDiagonal.push(0);
      const diagonalId = _.takenDiagonal.length - 1;
      let diagonalIdUsed = false;

      for (let i = 0; i < _.n; i++) {
        const _x = x + i;
        const _y = y + i;
        if (_x < 0 || _y < 0 || _x >= _.n || _y >= _.n) continue; // skip oob
        if (_.diagonalMatrix[_y][_x] === -1) {
          _.diagonalMatrix[_y][_x] = diagonalId;
          diagonalIdUsed = true;
        }
      }

      if (!diagonalIdUsed) {
        _.takenDiagonal.pop();
      }
    }
  }
}

function nQueenInternal(_) {
  console.log("start when Y = ", _.cursorY);
  printBoard(_.board);

  for (let x = 0; x < _.n; x++) {
    const y = _.cursorY;
    console.log(`step`, x, y);

    if (_.takenX[x]) {
      console.log(`cant place, X=${x} is taken`);
      continue;
    }
    if (_.takenDiagonal[_.diagonalMatrix[y][x]] > 0) {
      console.log(`cant place, diagonal=#${_.diagonalMatrix[y][x]} is taken`);
      continue;
    }

    _.board[y][x] = 1;
    _.takenX[x] = 1;
    _.takenDiagonal[_.diagonalMatrix[y][x]]++;
    _.positions.push({ x, y });

    console.log("placing queen at ", x, y);
    printBoard(_.board);

    _.cursorY++;

    if (_.cursorY < _.n) {
      if (nQueenInternal(_)) {
        return true;
      }
    }
  }

  // Check success
  if (_.positions.length === _.n) {
    console.log("success!");
    return true;
  }

  // Didn't find a spot for this cursorY, undo last action
  const pop = _.positions.pop();
  if (!pop) {
    return false;
  }

  const { x, y } = pop;

  console.log(`cant find a spot for Y = ${_.cursorY}, undoing`, pop);
  _.board[y][x] = 0;
  _.takenX[x] = 0;
  _.takenDiagonal[_.diagonalMatrix[y][x]]--;
  _.cursorY--;

  printBoard(_.board);

  return false;
}

function nQueen(n) {
  console.warn(`nQueen(${n})`);

  const board = new Array(n).fill().map(() => new Array(n).fill(0));
  const _ = {
    board,
    n,
    cursorY: 0,
    takenX: {},
    positions: [],
  };

  createDiagonalMatrix(_);

  if (nQueenInternal(_)) {
    printBoard(_.board, "warn");
    return _.positions.map((e) => e.x);
  }

  return [];
}

if (process.argv) {
  console.warn(nQueen(Number(process.argv[2])));
}