N Queens Problem Javascript / Typescript recursive

n-queens-recursive.ts

type Queen = { row: number; column: number };
type Board = Queen[];

// A solution tree is a queen and all possible board combinations that
// satisfy the n queens problem for that queen placement
type Tree = [Queen, Tree] | [Queen];

// Convert a tree into a flat board
const getBoard = (t: Tree): Board => [
  t[0],
  ...(t.length === 2 ? getBoard(t[1]) : []),
];

// Check if a new position on a board is safe
const isSafe = (newQueen: Queen, board: Board): boolean =>
  !board.find(
    (queen) =>
      queen.row === newQueen.row ||
      queen.column === newQueen.column ||
      // Diagonal test
      Math.abs(queen.column - newQueen.column) ===
        Math.abs(queen.row - newQueen.row)
  );

const findNQueens = (size: number, column: number): Tree[] => {
  const possibleQueens: Queen[] = new Array(size)
    .fill(0)
    .map<Queen>((_, row) => ({ row: row + 1, column }));

  // Base case, on the first column, all positions are valid
  if (column === 1) {
    return possibleQueens.map<Tree>((q) => [q]);
  }

  // Get all possible queen boards for column - 1 queens
  const restBoardQueens = findNQueens(size, column - 1);

  // For each queen board, try adding our new possible queen in the current column
  return possibleQueens.reduce<Tree[]>((treeAcc, possibleQueen) => {
    return treeAcc.concat(
      restBoardQueens.reduce<Tree[]>((acc, tree) => {
        const board = getBoard(tree);

        // If the combination of the new queen and the existing board is valid, save a new tree
        const canAdd = isSafe(possibleQueen, board);
        return canAdd ? acc.concat([[possibleQueen, tree]]) : acc;
      }, [])
    );
  }, []);
};

const printBoard = (size: number, board: Board): string => {
  return board
    .sort((a, b) => a.row - b.row)
    .map((queen) => {
      return new Array(size)
        .fill(0)
        .map((_, idx) => (idx + 1 === queen.column ? "⬜" : "⬛"))
        .join("");
    })
    .join("\n");
};

// Execute below

const boardSize = 8;
const res = findNQueens(boardSize, boardSize);

if (res.length > 1) {
  console.log(`For board size ${boardSize} found ${res.length} solutions.`)
  for (let i = 0; i < Math.min(5, res.length); i++) {
    console.log(`\nSolution ${i + 1}:`);
    console.log(printBoard(boardSize, getBoard(res[i])));
  }
  if (res.length > 5) {
    console.log(`\n...\n\nSolution ${res.length}:`);
    console.log(printBoard(boardSize, getBoard(res[res.length - 1])));
  }
} else {
  console.log("No solutions found for board of size", boardSize);
}