Department of Computer Science and
Engineering
Assignment
Subject: Data Strictures and Algorithms
(CS-621)
MTech – IInd Semester
(Batch 2024-26)
National Institute of Technology
Hamirpur, Himachal Pradesh – 177055
Submitted By: Submitted To:
Dr. Nitin Gupta
Himanshu Kumar (24MCS009)
Divyanshu Verma (24MCS022)
Vishal Sharma (24MCS003)
Problem Statement: N-Knights Problem
Objec&ve:
Design and implement a solu0on for placing N knights on an N × N chessboard such that:
1. No two knights threaten each other (i.e., no knight can a;ack another knight).
2. Every empty cell on the board is under a=ack by at least one knight.
A knight in chess moves in an L-shape (two squares in one direc0on and one square in a
perpendicular direc0on). Therefore, for any knight placed on the board, it can poten0ally a;ack
the squares that are 2 steps away in one direc0on and 1 step away in the perpendicular direc0on.
Requirements:
1. Your solu0on should return the posi0ons of the knights as a list of tuples, where each
tuple represents the (row, column) posi0on of a knight on the board.
2. Write a func0on to visually print the board:
• 'K' to represent a knight.
• '_' to represent an empty cell.
Key Ideas and Approach:
2. Backtracking Approach:
• Try placing knights on the board, star0ng from the top-leM.
• For each knight placed, check if its posi0on is safe, meaning it doesn't a;ack any
other knight already placed.
• If the knight placement is safe, move on to the next knight.
• If a valid configura0on is found, check if every empty cell is under a=ack by at
least one knight.
• If not, backtrack and try placing the knights in a different arrangement.
3. Tracking the A=ack Range:
• Knights a;ack in an L-shape, so we need to track cells that are under a;ack.
• Maintain a set of a=acked cells to ensure all empty cells are covered by knights.
Algorithm Details:
1. Safety Check:
For each knight being placed, ensure no other knight is a;acking that cell. The a;ack
range of a knight can be represented as the set of cells it can reach.
2. Backtracking:
• Try placing knights row by row.
• If a knight is placed safely, move to the next row.
• If placing the knight leads to an invalid configura0on (i.e., some empty cells are not
covered), backtrack by removing the knight and trying another posi0ons Code:
Problem Statement:
Design and implement a solution for the N-Queens Problem using backtracking. The goal is
to place N queens on an N×N chessboard such that no two queens threaten each other. A
queen can attack another queen if they are in the same row, column, or diagonal.
Requirements:
• Your solution must return the positions of queens in the form of a tuple containing the
column index of the queen for each row.
• Write a function to print the board visually, with 'Q' for queen and '_' for empty.
The N-Queens problem is a classic example of backtracking.
Key Ideas:
• We try to place one queen in each row.
• For each row, we attempt to place a queen in all columns one by one.
• If placing a queen is safe, we move to the next row.
• If it leads to a conflict, we backtrack and try the next column.
We maintain:
• cols → used_columns: Keeps track of columns already occupied by queens.
• pos_diagonals (row + col) → used_diagonals_lr: Diagonals from top-left to
bottomright (\).
• neg_diagonals (row - col) → used_diagonals_rl: Diagonals from top-right to
bottomleft (/).
Code:
def solve_n_queens(n):
result = []
def backtrack(row, used_columns, used_diagonals_lr, used_diagonals_rl,
current_positions): if row == n:
[Link](tuple(current_positions)) return
for col in
range(n):
if (col in used_columns or
(row + col) in used_diagonals_lr or
(row - col) in used_diagonals_rl):
continue
# Place queen
used_columns.add(col)
used_diagonals_lr.add(row + col)
used_diagonals_rl.add(row - col)
current_positions.append(col)
# Move to next row
backtrack(row + 1, used_columns, used_diagonals_lr, used_diagonals_rl,
current_positions)
# Backtrack (remove the queen and try another column)
used_columns.remove(col) used_diagonals_lr.remove(row
+ col) used_diagonals_rl.remove(row - col)
current_positions.pop() backtrack(0, set(), set(), set(), [])
return result[0] if result else None
def print_board(queen_positions):
n = len(queen_positions)
for row in range(n):
row_display = [] for
col in range(n):
row_display.append("Q" if queen_positions[row] == col else "_")
print(" ".join(row_display))
n =
4
solution = solve_n_queens(n) print("Queen positions
(column index per row):", solution) print("\nBoard:")
print_board(solution)
Output:
Q. Given an undirected graph with VVV ver4ces, find the chroma'c number — the minimum
number of colors needed to color the graph so that no two adjacent ver4ces share the same color.
SOLUTION -: The chroma'c number of a graph is the minimum number of colors needed to color all
ver4ces such that no two adjacent ver4ces share the same color.
package main
import (
"fmt"
type Graph struct {
ver4ces int
edges [][]bool
func NewGraph(ver4ces int) *Graph {
edges := make([][]bool, ver4ces) for i := range
edges { edges[i] = make([]bool,
ver4ces)
return &Graph{ver4ces, edges}
func (g *Graph) AddEdge(u, v int) {
[Link][u][v] = true
[Link][v][u] = true
}
func (g *Graph) isSafe(v int, color []int, c int) bool
{ for i := 0; i < g.ver4ces; i++ {
if [Link][v][i] && color[i] == c {
return false
return true
func (g *Graph) graphColoringU4l(m int, color []int, v int) bool {
if v == g.ver4ces {
return true
for c := 1; c <= m; c++ { if [Link](v,
color, c) {
color[v] = c
if g.graphColoringU4l(m, color, v+1) {
return true
color[v] = 0
return false
func (g *Graph) FindChroma4cNumber() int {
color := make([]int, g.ver4ces)
for m := 1; m <= g.ver4ces; m++ {
if g.graphColoringU4l(m, color, 0) {
return m
return g.ver4ces
func main() {
g := NewGraph(4)
[Link](0, 1)
[Link](0, 2)
[Link](1, 2)
[Link](2, 3)
chroma4cNumber := g.FindChroma4cNumber() [Link]("Chroma4c Number
of the graph is: %d\n", chroma4cNumber)
OUTPUT-: