Question_3:
Answer:
#include <iostream>
#include <vector>
using namespace std;
#define N 9
// Check if placing a number is valid
bool isSafe(vector<vector<int>>& grid, int row, int col, int num) {
// Check row and column
for (int x = 0; x < N; x++) {
if (grid[row][x] == num || grid[x][col] == num) return false;
// Check 3x3 subgrid
int startRow = row - row % 3, startCol = col - col % 3;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (grid[i + startRow][j + startCol] == num) return false;
return true;
// Solve Sudoku using backtracking
bool solveSudoku(vector<vector<int>>& grid) {
int row = -1, col = -1;
bool isEmpty = false;
// Find an empty cell
for (int i = 0; i < N && !isEmpty; i++)
for (int j = 0; j < N; j++)
if (grid[i][j] == 0) {
row = i; col = j;
isEmpty = true;
break;
// No empty cell means solved
if (!isEmpty) return true;
// Try numbers 1 to 9
for (int num = 1; num <= 9; num++) {
if (isSafe(grid, row, col, num)) {
grid[row][col] = num;
if (solveSudoku(grid)) return true;
grid[row][col] = 0; // Backtrack
return false; // No solution
int main() {
// Sample 9x9 Sudoku grid (0 means empty)
vector<vector<int>> grid = {
{5,3,0,0,7,0,0,0,0},
{6,0,0,1,9,5,0,0,0},
{0,9,8,0,0,0,0,6,0},
{8,0,0,0,6,0,0,0,3},
{4,0,0,8,0,3,0,0,1},
{7,0,0,0,2,0,0,0,6},
{0,6,0,0,0,0,2,8,0},
{0,0,0,4,1,9,0,0,5},
{0,0,0,0,8,0,0,7,9}
};
if (solveSudoku(grid)) {
cout << "Sudoku Solved:\n";
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << grid[i][j] << " ";
cout << endl;
} else {
cout << "No solution exists\n";
}
return 0;
Technique to Solve Sudoku
To fill a 9×9 Sudoku grid while following the rules (each row, column, and 3×3 subgrid must
contain unique digits 1–9), we use backtracking, a systematic search algorithm:
1. Find an Empty Cell: Locate a cell with value 0.
2. Try Numbers: For the empty cell, try digits 1–9, ensuring the placement is valid (using
isSafe to check row, column, and 3×3 subgrid).
3. Recursively Solve: Place the digit, move to the next empty cell, and repeat. If a solution
is found, return true.
4. Backtrack on Failure: If no digit works, reset the cell to 0 and backtrack to the previous
cell to try a different number.
Handling Invalid States and Exploring Solution Space
Invalid States: The isSafe function checks if a number violates Sudoku rules. If a
placement leads to an invalid state (e.g., no number fits), backtracking reverts the cell to
0 and tries a different number at the previous step.
Efficient Exploration: Backtracking explores the solution space depth-first, pruning
branches early when a placement is invalid. This avoids exploring all possibilities
unnecessarily. For efficiency, we can add constraint propagation (e.g., maintaining bitsets
for each row/column/subgrid), but the basic approach is sufficient for a 9×9 grid.
Time Complexity (Worst Case)
Analysis: For a 9×9 grid, there are 81 cells. In the worst case (e.g., an empty grid), we try
all numbers 1–9 for each cell:
o At each cell, we try 9 possibilities.
o Total possibilities: 9819^{81}981, but backtracking prunes many invalid paths.
Practical Complexity: With pruning, the complexity is exponential but manageable for
9×9 grids. Worst-case time complexity is O(9m)O(9^m)O(9m), where mmm is the
number of empty cells. For a typical puzzle with 30–40 empty cells, this is feasible due to
early pruning.
Summary
Backtracking solves Sudoku by systematically trying numbers and backtracking on invalid
states, efficiently exploring the solution space. The C++ implementation ensures rule
compliance, and the worst-case time complexity is O(9m)O(9^m)O(9m), where mmm is the
number of empty cells, made practical by pruning.
Question 4:
Answer:
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
#define N 4 // Number of locations
// Dynamic Programming for TSP
int tsp(vector<vector<int>>& dist, int pos, int visited, vector<vector<int>>& dp) {
if (visited == (1 << N) - 1) return dist[pos][0]; // Return to start
if (dp[pos][visited] != -1) return dp[pos][visited];
int minCost = INT_MAX;
for (int next = 0; next < N; next++) {
if (!(visited & (1 << next))) {
int cost = dist[pos][next] + tsp(dist, next, visited | (1 << next), dp);
minCost = min(minCost, cost);
return dp[pos][visited] = minCost;
int main() {
// Distance matrix (0 is the starting point)
vector<vector<int>> dist = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
// DP table: dp[pos][visited] stores min cost
vector<vector<int>> dp(N, vector<int>(1 << N, -1));
int minCost = tsp(dist, 0, 1, dp); // Start at position 0, visited = 1 (start)
cout << "Minimum cost of the route: " << minCost << endl;
return 0; }
Approach to Find the Optimal Route
The problem is a Traveling Salesman Problem (TSP), where a delivery system must visit each
location exactly once and return to the starting point with minimum cost. We use Dynamic
Programming (DP) to solve it:
State: dp[pos][visited], where pos is the current location, and visited is a bitmask of
visited locations.
Transition: For each unvisited location, compute the cost of visiting it next and
recursively solve for the remaining locations.
Base Case: When all locations are visited, return the cost to the starting point.
The C++ implementation uses a distance matrix and computes the minimum cost route
starting from location 0.
Implications as Number of Destinations Increases
Scalability: TSP is NP-hard. For nnn destinations, there are (n−1)!(n-1)!(n−1)! possible
routes (excluding the start). DP reduces this by memoization but still has:
o Time Complexity: O(n2⋅2n)O(n^2 \cdot 2^n)O(n2⋅2n), where 2n2^n2n states
(subsets of visited locations) and nnn transitions per state.
o Space Complexity: O(n⋅2n)O(n \cdot 2^n)O(n⋅2n) for the DP table.
Implications: As nnn increases (e.g., from 4 to 20):
o The exponential factor 2n2^n2n grows rapidly (e.g., 220≈1 million2^{20} \approx
1 \text{ million}220≈1 million), making the solution infeasible for large nnn.
o For n>15n > 15n>15, exact solutions become impractical, and heuristic
algorithms (e.g., nearest neighbor, genetic algorithms) are preferred, trading
optimality for speed (e.g., O(n2)O(n^2)O(n2) time but suboptimal routes).
Summary
The DP approach optimally solves TSP for small nnn (e.g., 4 locations, as shown), with
O(n2⋅2n)O(n^2 \cdot 2^n)O(n2⋅2n) time complexity. However, as the number of destinations
increases, the exponential growth makes it inefficient, necessitating heuristic methods for large-
scale delivery optimization.
