# 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.

#### [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

# 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:

    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:

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)