## N-Queens Problem

Sunday, February 19th 2023

A good example of a backtracking algorithm is the N-Queens problem, which is a classic problem in computer science and combinatorial optimization. The problem is to find a way to place `n` queens on an `n` x `n` chessboard such that no two queens threaten each other. In other words, no two queens can be placed on the same row, column, or diagonal.

Here is an example implementation of the N-Queens problem using backtracking in JavaScript:

``````function nQueens(n) {
const board = Array.from(Array(n), () => new Array(n).fill(0));
const result = [];

function canPlace(row, col) {
for (let i = 0; i < row; i++) {
if (board[i][col] === 1) {
return false;
}
if (col - (row - i) >= 0 && board[i][col - (row - i)] === 1) {
return false;
}
if (col + (row - i) < n && board[i][col + (row - i)] === 1) {
return false;
}
}
return true;
}

function backtrack(row) {
if (row === n) {
result.push([...board].map(row => row.join('')));
return;
}
for (let col = 0; col < n; col++) {
if (canPlace(row, col)) {
board[row][col] = 1;
backtrack(row + 1);
board[row][col] = 0;
}
}
}

backtrack(0);
return result;
}

console.log(nQueens(4));
// Output:
// [
//   [ '0100', '0010', '1000', '0001' ],
//   [ '0010', '1000', '0001', '0100' ]
// ]
``````

Another implementation:

``````function solveNQueens(n) {
const results = [];
const board = new Array(n).fill().map(() => new Array(n).fill("."));

function isSafe(row, col) {
// Check if there is a queen in the same column
for (let i = 0; i < row; i++) {
if (board[i][col] === "Q") {
return false;
}
}

// Check if there is a queen on the diagonal
for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] === "Q") {
return false;
}
}

// Check if there is a queen on the other diagonal
for (let i = row, j = col; i >= 0 && j < n; i--, j++) {
if (board[i][j] === "Q") {
return false;
}
}

// Otherwise, it is safe to place a queen
return true;
}

function backtrack(row) {
// If we have placed N queens, add the current solution to the results array
if (row === n) {
const solution = board.map((row) => row.join(""));
results.push(solution);
return;
}

// Try to place a queen in each column of the current row
for (let col = 0; col < n; col++) {
if (isSafe(row, col)) {
board[row][col] = "Q";
backtrack(row + 1);
board[row][col] = ".";
}
}
}

// Start the backtracking algorithm from the first row
backtrack(0);

// Return all the solutions found
return results;
}

// Example usage
console.log(solveNQueens(4));``````

In this implementation, the `solveNQueens(n)` function takes an integer `n` and returns an array of all possible solutions to the N-Queens problem on an `n` x `n` chessboard. The algorithm uses a backtracking approach to explore all possible combinations of queen placements.

The `board` variable represents the chessboard, and the `isSafe(row, col)` function checks if it is safe to place a queen at the given position on the board. The `backtrack(row)` function recursively tries to place queens in each column of the current row, backtracking when a solution is found to be invalid. When a valid solution is found, it is added to the `results` array.

In the example usage, `solveNQueens(4)` finds all possible solutions to the N-Queens problem on a 4 x 4 chessboard. The output of this function would be:

``````[
[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]
]``````