N Queens Problem in DSA C - Build from Scratch

N Queens Problem

📖 Scenario: You are helping a chess player find all the ways to place 4 queens on a 4x4 chessboard so that no two queens attack each other. Queens can attack horizontally, vertically, and diagonally. Your task is to write a program that finds all safe arrangements of queens on the board.

🎯 Goal: Build a program that uses backtracking to place 4 queens on a 4x4 board safely and prints all valid board arrangements.

📋 What You'll Learn

Create a 4x4 board represented as a 2D array of integers initialized to 0

Create a function isSafe that checks if placing a queen at a given row and column is safe

Create a recursive function solveNQueens that tries to place queens column by column

Print all valid board arrangements with queens represented by 1 and empty spaces by 0

💡 Why This Matters

🌍 Real World

The N Queens problem is a classic example of constraint satisfaction problems used in artificial intelligence and optimization tasks.

💼 Career

Understanding backtracking and recursion helps in solving complex algorithmic problems in software development and technical interviews.

1

Create the 4x4 chessboard

Create a 4x4 integer array called board and initialize all elements to 0.

DSA C

int board[4][4] = {0};
// Your code here

Hint

Use int board[4][4] = {0}; to create and initialize the board.

2

Write the isSafe function

Write a function int isSafe(int board[4][4], int row, int col) that returns 1 if placing a queen at board[row][col] is safe, otherwise returns 0. Check the row on left side, upper diagonal on left side, and lower diagonal on left side.

DSA C

int board[4][4] = {0};

int isSafe(int board[4][4], int row, int col) {
    // Your code here
}

Hint

Check left side row, upper diagonal, and lower diagonal for any queen (value 1).

3

Write the solveNQueens recursive function

Write a recursive function int solveNQueens(int board[4][4], int col) that tries to place queens column by column. If all queens are placed, return 1. For each row in the current column, check if it is safe using isSafe. If safe, place the queen (set to 1), recursively call solveNQueens for next column, and if it returns 1, return 1. Otherwise, backtrack by removing the queen (set to 0). If no row works, return 0.

DSA C

int board[4][4] = {0};

int isSafe(int board[4][4], int row, int col) {
    int i, j;
    for (i = 0; i = 0 && j >= 0; i--, j--)
        if (board[i][j])
            return 0;
    for (i = row, j = col; i = 0; i++, j--)
        if (board[i][j])
            return 0;
    return 1;
}

int solveNQueens(int board[4][4], int col) {
    // Your code here
}

Hint

Try placing queens column by column and backtrack if needed.

4

Print the board and run the solver

Write a function void printBoard(int board[4][4]) that prints the board with 1s and 0s. Then in main, call solveNQueens(board, 0). If it returns 1, call printBoard(board) to display the solution.

DSA C

int board[4][4] = {0};

int isSafe(int board[4][4], int row, int col) {
    int i, j;
    for (i = 0; i = 0 && j >= 0; i--, j--)
        if (board[i][j])
            return 0;
    for (i = row, j = col; i = 0; i++, j--)
        if (board[i][j])
            return 0;
    return 1;
}

int solveNQueens(int board[4][4], int col) {
    if (col >= 4)
        return 1;
    int row;
    for (row = 0; row < 4; row++) {
        if (isSafe(board, row, col)) {
            board[row][col] = 1;
            if (solveNQueens(board, col + 1))
                return 1;
            board[row][col] = 0; // backtrack
        }
    }
    return 0;
}

void printBoard(int board[4][4]) {
    // Your code here
}

int main() {
    // Your code here
}

Hint

Print each row with spaces between numbers and a newline after each row. Call solveNQueens(board, 0) in main and print the board if solution found.