package src;
import java.util.*;

public class tsp {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int c[][] = new int[10][10];
        int tour[] = new int[10]; 
        int i, j, cost;
        
        System.out.println("Enter no of cities"); 
        int n = sc.nextInt();
        
        if (n == 1) {
            System.out.println("Path is not possible");
            System.exit(0);
        }
        
        System.out.println("Enter the cost matrix"); 
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                c[i][j] = sc.nextInt();
            }
        }
        
        for (i = 1; i <= n; i++) {
            tour[i] = i; 
        }
        
        cost = tspdp(c, tour, 1, n);
        
        System.out.println("The optimal tour is = ");
        for (i = 1; i <= n; i++) {
            System.out.print(tour[i] + "->");
        }
        System.out.println("1");
        System.out.println("\tMin Cost = " + cost);
        
        sc.close();
    }
    
    static int tspdp(int c[][], int tour[], int start, int n) {
        int mintour[] = new int[10];
        int temp[] = new int[10]; // Fixed missing space here
        int mincost = 999, ccost, i, j, k; 
        
        if (start == n - 1) {
            return (c[tour[n - 1]][tour[n]] + c[tour[n]][1]); 
        }
        
        for (i = start + 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                temp[j] = tour[j]; 
            }
            
            // Swap cities to check a new permutation route
            temp[start + 1] = tour[i];
            temp[i] = tour[start + 1];
            
            ccost = tspdp(c, temp, start + 1, n);
            if ((c[tour[start]][tour[i]] + ccost) < mincost) { 
                mincost = c[tour[start]][tour[i]] + ccost;
                for (k = 1; k <= n; k++) {
                    mintour[k] = temp[k];
                }
            }
        }
        
        for (i = 1; i <= n; i++) {
            tour[i] = mintour[i]; 
        }
        
        return mincost;
    }
}

package src;

import java.util.*;

public class nqueen {

    public static boolean isSafe(int row, int col, char[][] board) {
        // Check horizontal row
        for (int j = 0; j < board.length; j++) {
            if (board[row][j] == 'Q') {
                return false;
            }
        }

        // Check vertical column
        for (int i = 0; i < board.length; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }

        int r = row;
        // Check top-left diagonal
        for (int c = col; c >= 0 && r >= 0; c--, r--) {
            if (board[r][c] == 'Q') {
                return false;
            }
        }

        r = row;
        // Check top-right diagonal
        for (int c = col; c < board.length && r >= 0; r--, c++) {
            if (board[r][c] == 'Q') {
                return false;
            }
        }

        r = row;
        // Check bottom-left diagonal
        for (int c = col; c >= 0 && r < board.length; r++, c--) {
            if (board[r][c] == 'Q') {
                return false;
            }
        }

        r = row;
        // Check bottom-right diagonal
        for (int c = col; c < board.length && r < board.length; c++, r++) {
            if (board[r][c] == 'Q') {
                return false;
            }
        }

        return true;
    }

    public static void saveBoard(char[][] board, List<List<String>> allBoards) {
        List<String> newBoard = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            String row = "";
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'Q') {
                    row += 'Q';
                } else {
                    row += '.';
                }
            }
            newBoard.add(row);
        }
        allBoards.add(newBoard);
    }

    public static void solve(char[][] board, List<List<String>> allBoards, int col) {
        if (col == board.length) {
            saveBoard(board, allBoards);
            return;
        }

        for (int row = 0; row < board.length; row++) {
            if (isSafe(row, col, board)) {
                board[row][col] = 'Q';
                solve(board, allBoards, col + 1);
                board[row][col] = '.'; // Backtrack
            }
        }
    }

    public static void solution(int n) {
        List<List<String>> allBoards = new ArrayList<>();
        char[][] board = new char[n][n];

        // Initialize the board with '.' otherwise it contains default null characters
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }

        solve(board, allBoards, 0);

        // Print all valid configurations
        for (List<String> aboard : allBoards) {
            for (int i = 0; i < aboard.size(); i++) {
                System.out.println(aboard.get(i));
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        solution(4);
    }														
}

package src;

import java.util.*;

public class subset {

    static int c = 0;

    public static void main(String[] args) {
        int w[] = new int[10];
        int n, d, i, sum = 0;
        int x[] = new int[10];
        Scanner sc = new Scanner(System.in);

        System.out.println("****SUBSET PROBLEM****");
        System.out.println("Enter the no of elements");
        n = sc.nextInt();

        System.out.println("Enter the elements in increasing order");
        for (i = 0; i < n; i++) {
            w[i] = sc.nextInt();
        }

        System.out.println("Enter the value of d:");
        d = sc.nextInt();

        for (i = 0; i < n; i++) {
            sum = sum + w[i];
        }
        System.out.println("SUM:" + sum);

        if (sum < d || w[0] > d) {
            System.out.println("Subset is not possible");
            System.out.println("*****************");
            System.exit(0);
        }

        finalsubset(0, 0, sum, x, w, d);

        if (c == 0) {
            System.out.println("subset is not possible");
        }
        
        System.out.println("\n *********");
        sc.close();
    }

    static void finalsubset(int cs, int k, int r, int x[], int w[], int d) {
        x[k] = 1;
        if (cs + w[k] == d) {
            c++;
            System.out.println("\nSolution " + c + " is {");
            for (int i = 0; i <= k; i++) {
                if (x[i] == 1) {
                    System.out.print(w[i] + " ");
                }
            }
            System.out.print("}");
        } 
        else if ((cs + w[k] + w[k + 1]) <= d) {
            finalsubset(cs + w[k], k + 1, r - w[k], x, w, d);
        }

        if ((cs + r - w[k]) >= d && (cs + w[k + 1]) <= d) {
            x[k] = 0;
            finalsubset(cs, k + 1, r - w[k], x, w, d);
        }
    }
}

package src;
import java.util.Scanner;
public class hamimlton {


    static int[] x = new int[25];

    static void Next_Vertex(int G[][], int n, int k) {
        int j;
        while (true) {
            x[k] = (x[k] + 1) % (n + 1);
            if (x[k] == 0) {
                return;
            }
            
            if (G[x[k - 1]][x[k]] != 0) {
                for (j = 1; j <= k - 1; j++) {
                    if (x[j] == x[k]) {
                        break;
                    }
                }
                if (j == k) {
                    if ((k < n) || ((k == n) && (G[x[n]][x[1]] != 0))) {
                        return;
                    }
                }
            }
        }
    }

    static void H_Cycle(int G[][], int n, int k) {
        int i;
        while (true) {
            Next_Vertex(G, n, k);
            if (x[k] == 0) {
                return;
            }
            if (k == n) {
                System.out.println();
                for (i = 1; i <= n; i++) {
                    System.out.print(x[i] + "-->");
                }
                System.out.println(x[1]);
            } else {
                H_Cycle(G, n, k + 1);
            }
        }
    }

    public static void main(String[] args) {
        int i, j, n;
        int[][] G = new int[25][25];
        Scanner read = new Scanner(System.in);

        System.out.println("Enter the number of vertices of the graph");
        n = read.nextInt();

        System.out.println("Enter thJe Path adjacency matrix");
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= n; j++) {
                G[i][j] = read.nextInt();
                x[i] = 0;
            }
        }

        x[1] = 1; // Start the cycle from vertex 1
        System.out.println("\nHamiltonian Cycles are");
        H_Cycle(G, n, 2);
        
        read.close();
    }
}

package src;
import java.util.Scanner;
public class zoknapsack {


    int n, c, p[], w[], v[][];

    public zoknapsack (int n, int c, int[] p, int[] w) {
        this.n = n;
        this.c = c;
        this.p = p;
        this.w = w;
        this.v = new int[n + 1][c + 1];
    }

    void compute() {
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= c; ++j) {
                if (i == 0 || j == 0) {
                    v[i][j] = 0;
                } else {
                    if (j - w[i] >= 0) {
                        v[i][j] = max(v[i - 1][j], p[i] + v[i - 1][j - w[i]]);
                    } else {
                        v[i][j] = v[i - 1][j];
                    }
                }
            }
        }
        System.out.println("Optimal Solution: " + v[n][c]);
        traceback();
    }

    void traceback() {
        System.out.println("The objects picked up into knapsack are: ");
        int i = n;
        int j = c;
        while (i > 0) {
            if (v[i][j] != v[i - 1][j]) {
                System.out.print(i + " ");
                j = j - w[i];
            }
            i--;
        }
    }

    private int max(int i, int j) {
        return (i > j) ? i : j;
    }

    public static void main(String[] args) {
        int n;
        int c;
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter number of objects");
        n = sc.nextInt();
        int[] p = new int[n + 1];
        int[] w = new int[n + 1];
        System.out.println("Enter capacity of knapsack");
        c = sc.nextInt();
        System.out.println("Enter the profit for each of the " + n + " objects");
        for (int i = 1; i <= n; i++) {
            p[i] = sc.nextInt();
        }
        System.out.println("Enter weight for each of the " + n + " objects");
        for (int i = 1; i <= n; i++) {
            w[i] = sc.nextInt();
        }
        zoknapsack  dk = new zoknapsack (n, c, p, w);
        dk.compute();
        sc.close();
    }
}

package src;
import java.util.*;
public class dijkstra {




    public int distance[] = new int[10];
    public int cost[][] = new int[10][10];

    public void calc(int n, int s) {
        int flag[] = new int[n + 1];
        int i, minpos = 1, k, c, minimum;

        for (i = 1; i <= n; i++) {
            flag[i] = 0;
            this.distance[i] = this.cost[s][i];
        }

        c = 2;
        while (c <= n) {
            minimum = 999;
            for (k = 1; k <= n; k++) {
                // Fixed: replaced 'i' with 'k' in minimum = this.distance[k]
                if (this.distance[k] < minimum && flag[k] != 1) {
                    minimum = this.distance[k];
                    minpos = k;
                }
            }
            
            flag[minpos] = 1;
            c++;

            for (k = 1; k <= n; k++) {
                if (this.distance[minpos] + this.cost[minpos][k] < this.distance[k] && flag[k] != 1) {
                    this.distance[k] = this.distance[minpos] + this.cost[minpos][k];
                }
            }
        }
    }

    public static void main(String[] args) {
        int nodes, source, i, j;
        Scanner in = new Scanner(System.in);

        System.out.println("Enter the number of nodes");
        nodes = in.nextInt();

        dijkstra d = new dijkstra();

        System.out.println("Enter the cost Matrix Weights");
        for (i = 1; i <= nodes; i++) {
            for (j = 1; j <= nodes; j++) {
                d.cost[i][j] = in.nextInt();
                if (d.cost[i][j] == 0) {
                    d.cost[i][j] = 999;
                }
            }
        }

        System.out.println("Enter the source vertex");
        source = in.nextInt();

        d.calc(nodes, source);

        System.out.println("The shortest path from source " + source + " to all other vertices are:");
        for (i = 1; i <= nodes; i++) {
            if (i != source) {
                System.out.println("Source: " + source + " destination : " + i + " Mincost : " + d.distance[i]);
            }
        }
    }
}