N-Queens Problem

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.."]
]