Scribd
Upload
5 views3 pages

N-Queens Problem C++ Backtracking Solution

The document presents a C++ implementation of the N-Queens problem using backtracking, starting with a queen placed at a specified position on an n x n chessboard. It includes functions to check if a position is safe for placing a queen, to solve the problem recursively, and to print the board configuration. The output shows one of the valid configurations for a 4x4 board with the first queen at position (0,1).

Uploaded by

Yash Jogdand
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
5 views3 pages

N-Queens Problem C++ Backtracking Solution

The document presents a C++ implementation of the N-Queens problem using backtracking, starting with a queen placed at a specified position on an n x n chessboard. It includes functions to check if a position is safe for placing a queen, to solve the problem recursively, and to print the board configuration. The output shows one of the valid configurations for a 4x4 board with the first queen at position (0,1).

Uploaded by

Yash Jogdand
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Practical No.

05
Name – Yash Jogdand Batch – B3
Roll – 2059 Class – BE
Comp

Problem Statement -

Given an 𝑛 × 𝑛 chessboard with the first queen placed at a specified position, use
backtracking to place the remaining queens so that no two queens threaten each
other. The solution must return the final configuration of the board.

Code –
C++ Code with First Queen Placed and Backtracking
#include <iostream>

#include <vector>

using namespace

std;

bool isSafe(const vector<vector<int>>& board, int row, int col, int

n) { for (int i = 0; i < row; i++)

if (board[i][col] == 1) return false;

for (int i = row, j = col; i >= 0 && j >= 0; i--,

j--) if (board[i][j] == 1) return false;

for (int i = row, j = col; i >= 0 && j < n; i--,

j++) if (board[i][j] == 1) return false;

return true;

bool solveNQueensBacktracking(vector<vector<int>>& board, int row,

int n) { if (row == n) return true;

bool queenAlreadyPlaced = false;

for(int col = 0; col < n; col++) {


if(board[row][col] == 1)

{ queenAlreadyPlaced = true;

if(solveNQueensBacktracking(board, row + 1, n))

return true;

else

return false;

for (int col = 0; col < n; col++)

{ if (isSafe(board, row, col,

n)) {

board[row][col] = 1;

if (solveNQueensBacktracking(board, row + 1,

n)) return true;

board[row][col] = 0;

return false;

void printBoard(const vector<vector<int>>& board, int

n) { for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

cout << (board[i][j] == 1 ? "Q " : ". ");

cout << endl;

int main() {

int n = 4;

vector<vector<int>> board(n, vector<int>(n, 0));

board[0][1] = 1;
if (solveNQueensBacktracking(board, 1, n)) {

cout << "One of the solutions with first queen placed at (0,1):\n";

printBoard(board, n);

} else {

cout << "No solution exists with first queen placed at given
position.\n";

return 0;

Output -
One of the solutions with first queen placed at (0,1):

.Q..
...Q
Q...
..Q.

You might also like