The N Queens Problem Using JavaScript

 The N-Queens problem is a classic puzzle that has intrigued mathematicians, computer scientists, and enthusiasts alike for decades. It poses a seemingly simple question: How can N queens be placed on an N×N chessboard in such a way that no two queens threaten each other?

The origin of the N-Queens problem can be traced back to the 19th century when the legendary mathematician Carl Friedrich Gauss first considered the challenge of placing eight queens on a chessboard without any conflicts. Since then, the problem has captured the attention of numerous mathematicians and has become a subject of intense study.

The objective of the N-Queens problem is to find a placement of N queens on an N×N chessboard, such that no two queens share the same row, column, or diagonal. Although the problem may seem simple at first glance, it quickly becomes apparent that finding a solution becomes increasingly difficult as the size of the chessboard and the number of queens increase.

Now I'm going to walk you in this step by step tutorial on how to solve the nqueens problem using backtracking in JavaScript:

Step 1: Initialize the Variables Start by declaring the variables needed for the solution. These variables include the size of the chessboard (N), an empty board (board), and an empty array to store the solutions (solutions).

let N = 0; // Size of the chessboard

let board = [];

let solutions = [];

Step 2: Define the isSafe() Function

Create a helper function called isSafe() that checks if it is safe to place a queen at a specific position (row, col) on the board. This function will iterate over the previously placed queens and check for any conflicts.

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] === 1) {

            return false;

        }

    }

    // Check if there is a queen in the upper-left diagonal

    for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {

        if (board[i][j] === 1) {

            return false;

        }

    }

    // Check if there is a queen in the upper-right diagonal

    for (let i = row, j = col; i >= 0 && j < N; i--, j++) {

        if (board[i][j] === 1) {

            return false;

        }

    }

    return true;

}

Step 3: Define the solveNQueens() Function

Create the main function, solveNQueens(), which will solve the N-Queens problem using backtracking. This function takes the size of the chessboard (n) as an argument and populates the solutions array with valid board configurations.

function solveNQueens(n) {

    N = n; // Set the size of the chessboard

    // Create an empty board

    board = new Array(N);

    for (let i = 0; i < N; i++) {

        board[i] = new Array(N).fill(0);

    }

    // Call the recursive function to find solutions

    findSolutions(0);

    return solutions;

}

Step 4: Implement the recursive function findSolutions(row) that finds all possible solutions by placing queens row by row. This function uses backtracking to explore all valid configurations.

function findSolutions(row) {

    // Base case: All queens are placed, add the solution to the solutions array

    if (row === N) {

        const solution = [];

        for (let i = 0; i < N; i++) {

            solution.push(board[i].join(""));

        }

        solutions.push(solution);

        return;

    }

    // Try placing a queen in each column of the current row

    for (let col = 0; col < N; col++) {

        if (isSafe(row, col)) {

            board[row][col] = 1; // Place the queen

            // Recursively try to place queens in the next row

            findSolutions(row + 1);

            board[row][col] = 0; // Remove the queen (backtrack)

        }

    }

}

Step 5: Test the Solution

You can now test the solution by calling the solveNQueens() function with the desired size of the chessboard. It will return an array of valid solutions.

const boardSize = 4; // Set the size of the chessboard

const solutions = solveNQueens(boardSize);

console.log(`Number of solutions for a ${boardSize}x${boardSize} chessboard: ${solutions.length}`);

console.log(solutions);

That's it! You have successfully implemented the N-Queens problem solver in JavaScript. The solutions array will contain all the valid board configurations for the given chessboard size.