---
# System prepended metadata

title: Algorithm 09/26-09/27
tags: [MScCourses]

---

# Algorithm 09/26-09/27 Content
## N-Queens Problem

The N-Queens problem consists of placing `N` queens on an `N x N` chessboard so that no two queens can attack each other. This means:
- No two queens can be in the same row.
- No two queens can be in the same column.
- No two queens can be on the same diagonal (both the main and secondary diagonals).

> [!Note]
> Here provide image and code in Colab.

![image](https://hackmd.io/_uploads/Hy1GLNN0C.png)
#### [Go to Colab](https://colab.research.google.com/drive/1zPdUi0NInkoDRXo5Yy37CD2GtV774tKf?authuser=1)

### Algorithm Explanation

1. **`is_safe(board, row, col)` function**:
   - This function checks whether it is safe to place a queen at the position `(row, col)`.
   - It checks three conditions:
     - **Same Column**: No queen should already be placed in the same column (`board[i] == col`).
     - **Main Diagonal**: No queen should be on the same main diagonal (`board[i] == j` for `i` decreasing, and `j` decreasing).
     - **Anti-Diagonal**: No queen should be on the same anti-diagonal (`board[i] == j` for `i` decreasing, and `j` increasing).

2. **`solve_n_queens(n)` function**:
   - This function implements the backtracking algorithm.
   - It recursively places queens row by row, and for each row, it tries placing a queen in each column.
   - If a valid placement is found (checked by `is_safe()`), it proceeds to the next row.
   - If placing a queen in a certain position leads to a conflict, it backtracks (implicitly by returning from the recursive call without making any changes).
   - When a valid configuration is found (i.e., when queens have been placed in all rows), the solution is recorded.

3. **Backtracking Process**:
   - The board is represented as an array `board[]`, where each index represents a row, and the value at each index represents the column where the queen is placed for that row.
   - For example, if `board[0] = 1`, it means the queen in row 0 is placed at column 1.

4. **Output**:
   - The function `solve_n_queens(n)` returns all valid configurations (solutions) for placing `N` queens.
   - Each solution is printed in a visual format where `Q` represents a queen, and `.` represents an empty space.

### Python Code

```python!
# Check if a queen can be placed at row, col
def is_safe(board, row, col):
    # Check for the same column
    for i in range(row):
        if board[i] == col:
            return False
    
    # Check for the main diagonal
    for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
        if board[i] == j:
            return False

    # Check for the anti-diagonal
    for i, j in zip(range(row-1, -1, -1), range(col+1, len(board))):
        if board[i] == j:
            return False

    return True

# Backtracking algorithm to solve the N-Queens problem
def solve_n_queens(n):
    def solve(board, row):
        # If all queens are placed, record the solution
        if row == n:
            solution = []
            for i in range(n):
                row_str = ['.'] * n
                row_str[board[i]] = 'Q'
                solution.append(''.join(row_str))
            solutions.append(solution)
            return
        
        # Try placing the queen in every column of the current row
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                solve(board, row + 1)
                # No explicit backtracking step needed because board[row] is overwritten

    solutions = []
    board = [-1] * n  # Initialize the board where each element is a row, -1 means no queen is placed
    solve(board, 0)
    return solutions

# Solve for N=5 and print all solutions
solutions = solve_n_queens(5)
for index, solution in enumerate(solutions, start=1):
    print(f"Solution {index}:")
    for row in solution:
        print(row)
    print()
```

### How the Algorithm Works

1. **Initialization**:
   - We create an empty board where `board[row] = -1` for all rows. This indicates that no queens are placed initially.

2. **Recursive Backtracking**:
   - For each row, the algorithm tries to place a queen in every possible column.
   - After placing a queen, it checks if it is a valid placement using the `is_safe()` function.
   - If valid, it recursively attempts to place queens in the following rows.
   - If the placement leads to a solution, it stores the result.
   - If no valid placement is possible, it backtracks to the previous row and tries the next possible column.

3. **Backtracking Mechanism**:
   - Backtracking occurs automatically when a recursive call completes, as the previous placement of the queen is overwritten in the next iteration.

4. **Solution Output**:
   - The solutions are represented visually with `Q` marking the position of queens and `.` for empty spaces.
   - For example, one of the solutions for `N=5` looks like this:
    ```Text
    Solution 1:
    Q . . . .
    . . Q . .
    . . . . Q
    . Q . . .
    . . . Q .

    Solution 2:
    Q . . . .
    . . . Q .
    . Q . . .
    . . . . Q
    . . Q . .
    ```
### Time Complexity

The time complexity of the N-Queens problem is `O(N!)` since we try to place queens in each row, and for each row, there are `N` possibilities initially, reducing as the algorithm progresses due to conflicts.



## Prim’s Algorithm

Prim's Algorithm is a greedy algorithm that finds the Minimum Spanning Tree (MST) for a weighted undirected graph. The MST is a subset of the edges that connects all the vertices without any cycles and with the minimum possible total edge weight. 

> [!Note]
> Here provide program on Colab.

#### [Go to Colab](https://colab.research.google.com/drive/16ihqxHQoV4A4F1_X9Qp0KfZEC1ZXhzhP?usp=sharing)

### Steps of Prim’s Algorithm:

1. **Initialization**:
   - Start with a graph \( G \) that consists of vertices and edges.
   - Choose an arbitrary vertex as the starting point and mark it as part of the MST.

2. **Grow the MST**:
   - Repeat the following steps until all vertices are included in the MST:
     - Look for the edge with the smallest weight that connects a vertex in the MST to a vertex outside the MST.
     - Add this edge and the vertex it connects to the MST.

3. **Termination**:
   - The process ends when all vertices are included in the MST.

### Python Code Implementation

Here’s a Python implementation of Prim's Algorithm that you can run in Google Colab:

```python
import numpy as np
import heapq

def prims_algorithm(graph):
    num_vertices = len(graph)
    visited = [False] * num_vertices
    min_heap = [(0, 0)]  # (weight, vertex)
    total_cost = 0
    mst_edges = []

    while min_heap:
        weight, u = heapq.heappop(min_heap)
        
        if visited[u]:
            continue
        
        visited[u] = True
        total_cost += weight

        if weight > 0:  # Exclude the first edge
            mst_edges.append((prev_vertex, u, weight))

        for v, edge_weight in enumerate(graph[u]):
            if not visited[v] and edge_weight > 0:
                heapq.heappush(min_heap, (edge_weight, v))
                prev_vertex = u

    return total_cost, mst_edges

# Example Usage
graph = np.array([
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
])

cost, edges = prims_algorithm(graph)
print("Total cost of MST:", cost)
print("Edges in the MST:", edges)
```