N Queens Problem in DSA Typescript - Build from Scratch

N Queens Problem

📖 Scenario: You are helping a chess player place 8 queens on a chessboard so that no two queens can attack each other. Queens can move any number of squares vertically, horizontally, or diagonally. Your task is to find one valid arrangement of queens on the board.

🎯 Goal: Build a program that finds one valid way to place 8 queens on an 8x8 chessboard so that no two queens threaten each other. The program will print the board showing queen positions.

📋 What You'll Learn

Create an 8x8 board represented as a 2D array of numbers

Use a helper function to check if placing a queen is safe

Implement a recursive function to place queens row by row

Print the final board with queens marked as 1 and empty spaces as 0

💡 Why This Matters

🌍 Real World

The N Queens problem helps understand how to solve complex puzzles using backtracking, a technique useful in scheduling, resource allocation, and game AI.

💼 Career

Backtracking algorithms and recursive problem solving are common in software engineering roles, especially in algorithm design, optimization, and coding interviews.

1

Create the chessboard

Create a variable called board that is an 8x8 two-dimensional array filled with zeros. Each zero represents an empty square on the chessboard.

DSA Typescript

const board: number[][] = Array(8).fill(0).map(() => Array(8).fill(0));
// Your code here

Hint

Use Array(8).fill(0) to create an array of length 8, then map each element to another array of 8 zeros.

2

Write the safety check function

Write a function called isSafe that takes three parameters: board, row, and col. It should return true if placing a queen at board[row][col] is safe (no other queens attack it), otherwise false. Check the column, upper left diagonal, and upper right diagonal for existing queens.

DSA Typescript

const board: number[][] = Array(8).fill(0).map(() => Array(8).fill(0));

function isSafe(board: number[][], row: number, col: number): boolean {
    // Your code here
}

Hint

Check vertically above, and diagonally left and right above the current position for any queens (1s).

3

Implement the recursive queen placement

Write a function called solveNQueens that takes board and row as parameters. It should try to place a queen in each column of the current row if it is safe. If a queen is placed, recursively call solveNQueens for the next row. Return true if all queens are placed successfully, otherwise false. Use backtracking to remove queens if needed.

DSA Typescript

const board: number[][] = Array(8).fill(0).map(() => Array(8).fill(0));

function isSafe(board: number[][], row: number, col: number): boolean {
    for (let i = 0; i = 0 && j >= 0; i--, j--) {
        if (board[i][j] === 1) return false;
    }
    for (let i = row - 1, j = col + 1; i >= 0 && j < 8; i--, j++) {
        if (board[i][j] === 1) return false;
    }
    return true;
}

function solveNQueens(board: number[][], row: number): boolean {
    // Your code here
}

Hint

Try placing a queen in each column of the current row. If safe, place it and move to next row. If stuck, remove the queen and try next column.

4

Print the final board

Call solveNQueens(board, 0) to start placing queens from the first row. Then print the board array to show the final arrangement. Each row should be printed as a space-separated string of 0s and 1s.

DSA Typescript

const board: number[][] = Array(8).fill(0).map(() => Array(8).fill(0));

function isSafe(board: number[][], row: number, col: number): boolean {
    for (let i = 0; i = 0 && j >= 0; i--, j--) {
        if (board[i][j] === 1) return false;
    }
    for (let i = row - 1, j = col + 1; i >= 0 && j < 8; i--, j++) {
        if (board[i][j] === 1) return false;
    }
    return true;
}

function solveNQueens(board: number[][], row: number): boolean {
    if (row === 8) return true;
    for (let col = 0; col < 8; col++) {
        if (isSafe(board, row, col)) {
            board[row][col] = 1;
            if (solveNQueens(board, row + 1)) return true;
            board[row][col] = 0; // backtrack
        }
    }
    return false;
}

solveNQueens(board, 0);
for (let row = 0; row < 8; row++) {
    // Your code here
}

Hint

After solving, print each row of the board as a string of numbers separated by spaces.