Question

Print all possible solutions to N Queens problem Print all Possible Knight's Tours in a chessboard Magnet Puzzle Find Shortest Path in Maze Find Longest Possible Route in a Matrix Find path from source to destination in a matrix that satisfies given constraints Find total number of unique paths in a maze from source to destination Print All Hamiltonian Path present in a graph Print all k-colorable configurations of the graph (Vertex coloring of graph) Find all Permutations of a given string All combinations of elements satisfiying given constraints Find all binary strings that can be formed from given wildcard pattern

DO ALL OR DON'T ANSWER.

Answer 1

1) Print all possible solutions to N Queens problem:

import java.util.Arrays; class NQueen {        // N x N chessboard     public static final int N = 8;  // Function to check if two queens threaten each other or not   private static boolean isSafe(char mat[][], int r, int c)       {               // return false if two queens share the same column             for (int i = 0; i < r; i++)                  if (mat[i][c] == 'Q')                           return false;           // return false if two queens share the same \ diagonal                 for (int i = r, j = c; i >= 0 && j >= 0; i--, j--)                        if (mat[i][j] == 'Q')                           return false;           // return false if two queens share the same / diagonal                 for (int i = r, j = c; i >= 0 && j < N; i--, j++)                         if (mat[i][j] == 'Q')                           return false;           return true;    }       private static void nQueen(char mat[][], int r)         {               // if N queens are placed successfully, print the solution              if (r == N)             {                       for (int i = 0; i < N; i++)                  {                               for (int j = 0; j < N; j++)                                  System.out.print(mat[i][j] + " ");                              System.out.println();                   }                       System.out.println();                   return;                 }               // place Queen at every square in current row r                 // and recur for each valid movement            for (int i = 0; i < N; i++)          {                       // if no two queens threaten each other                         if (isSafe(mat, r, i))                  {                               // place queen on current square                                mat[r][i] = 'Q';                                // recur for next row                           nQueen(mat, r + 1);                             // backtrack and remove queen from current square                               mat[r][i] = '-';                        }               }       }       public static void main(String[] args)  {               // mat[][] keeps track of position of Queens in                 // the current configuration            char[][] mat = new char[N][N];          // initialize mat[][] by '-'            for (int i = 0; i < N; i++) {                        Arrays.fill(mat[i], '-');               }               nQueen(mat, 0);         } }

2) Print all possible Knight's Tours in a chessboard:

class KnightTour {   // N x N chessboard     public static final int N = 5;  // Below arrays details all 8 possible movements for a knight.  // Don't change the sequence of below arrays    public static final int row[] = { 2, 1, -1, -2, -2, -1, 1, 2 , 2 };     public static final int col[] = { 1, 2, 2, 1, -1, -2, -2, -1, 1 };      // Check if (x, y) is valid chess board coordinates     // Note that a knight cannot go out of the chessboard   private static boolean isValid(int x, int y)    {               if (x < 0 || y < 0 || x >= N || y >= N)                     return false;           return true;    }       private static void print(int[][] visited)      {               for (int i = 0; i < N; i++)          {                       for (int j = 0; j < N; j++) {                                System.out.print(visited[i][j] + " ");                  }                       System.out.println();           }               System.out.println();   }       // Recursive function to perform the Knight's tour using backtracking   public static void knightTour(int visited[][], int x, int y, int pos)   {               // mark current square as visited               visited[x][y] = pos;            // if all squares are visited, print the solution               if (pos >= N*N)              {                       print(visited);                         // backtrack before returning                   visited[x][y] = 0;                      return;                 }               // check for all 8 possible movements for a knight              // and recur for each valid movement            for (int k = 0; k < 8; k++)          {                       // Get the new position of Knight from current                  // position on chessboard                       int newX = x + row[k];                  int newY = y + col[k];                  // if new position is a valid and not visited yet                       if (isValid(newX, newY) && visited[newX][newY] == 0)                            knightTour(visited, newX, newY, pos + 1);               }               // backtrack from current square and remove it from current path                visited[x][y] = 0;      }       public static void main(String[] args)  {               // visited[][] serves two purpose -             // 1. It keep track of squares involved the Knight's tour.              // 2. It stores the order in which the squares are visited              int visited[][] = new int[N][N];                int pos = 1;            // start knight tour from corner square (0, 0)          knightTour(visited, 0, 0, pos);         } }

3) Magnet puzzle:

import java.util.Arrays; class MagnetPuzzle {    // M x N matrix         private static final int M = 5;         private static final int N = 6;         // A utility function to print solution         private static void printSolution(char board[][])       {               for (int i = 0; i < M; i++)          {                       for (int j = 0; j < N; j++)                          System.out.print(board[i][j] + " ");                    System.out.println();           }       }       // A utility function to count number of characters ch in current column j      private static int countInColumns(char board[][], char ch, int j)       {               int count = 0;          for (int i = 0; i < M; i++)                  if (board[i][j] == ch)                          count++;                return count;   }       // A utility function to count number of characters ch in current row i         private static int countInRow(char board[][], char ch, int i)   {               int count = 0;          for (int j = 0; j < N; j++)                  if (board[i][j] == ch)                          count++;                return count;   }       // Function to check if it safe to put 'ch' at board[row][col]  private static boolean isSafe(char board[][], int row, int col, char ch,                                                        int top[], int left[], int bottom[], int right[])       {               // check for adjacent cells             if ((row - 1 >= 0 && board[row - 1][col] == ch) ||                           (col + 1 < N && board[row][col + 1] == ch) ||                                (row + 1 < M && board[row + 1][col] == ch) ||                                (col - 1 >= 0 && board[row][col - 1] == ch))                         return false;           // count ch in current row              int rowCount = countInRow(board, ch, row);              // count ch in current column           int colCount = countInColumns(board, ch, col);          // if given character is '+', check top[] & left[]          if (ch == '+')          {                       // check top                    if (top[col] != -1 && colCount >= top[col])                          return false;                   // check left                   if (left[row] != -1 && rowCount >= left[row])                                return false;           }               // if given character is '-', check bottom[] & right[]              if (ch == '-')          {                       // check bottom                         if (bottom[col] != -1 && colCount >= bottom[col])                            return false;                   // check left                   if (right[row] != -1 && rowCount >= right[row])                              return false;           }               return true;    }       // Function to validate Configuration of output board   private static boolean validateConfiguration(char board[][],                                            int top[], int left[], int bottom[], int right[])       {               // check top            for (int i = 0; i < N; i++)                  if (top[i] != -1 && countInColumns(board, '+', i) != top[i])                            return false;           // check left           for (int j = 0; j < M; j++)                  if (left[j] != -1 && countInRow(board, '+', j) != left[j])                              return false;           // check bottom                 for (int i = 0; i < N; i++)                  if (bottom[i] != -1 && countInColumns(board, '-', i) != bottom[i])                              return false;           // check right          for (int j = 0; j < M; j++)                  if (right[j] != -1 && countInRow(board, '-', j) != right[j])                            return false;           return true;    }       // Main function to solve the Bipolar Magnets puzzle    private static boolean solveMagnetPuzzle(char board[][], int row, int col,                              int top[], int left[], int bottom[], int right[], char str[][])         {               // if we have reached last cell                 if (row >= M - 1 && col >= N - 1)                 {                       return validateConfiguration(board, top, left, bottom, right);          }               // if last column of current row is already processed,          // go to next row, first column                 if (col >= N)                {                       col = 0;                        row = row + 1;          }               // if current cell contains 'R' or 'B' (end of horizontal               // or vertical slot) recur for next cell                if (str[row][col] == 'R' || str[row][col] == 'B')               {                       if (solveMagnetPuzzle(board, row, col + 1, top,                                         left, bottom, right, str))                              return true;            }               // if horizontal slot contains L and R          if (str[row][col] == 'L' && str[row][col + 1] == 'R')           {                       // put ('+', '-') pair and recur                        if (isSafe(board, row, col, '+', top, left, bottom, right) &&                           isSafe(board, row, col + 1, '-', top, left, bottom, right))                     {                               board[row][col] = '+';                          board[row][col + 1] = '-';                              if (solveMagnetPuzzle(board, row, col + 2,                                              top, left, bottom, right, str))                                         return true;                            // if it doesn't lead to a solution, backtrack                          board[row][col] = 'X';                          board[row][col + 1] = 'X';                      }                       // put ('-', '+') pair and recur                        if (isSafe(board, row, col, '-', top, left, bottom, right) &&                           isSafe(board, row, col + 1, '+', top, left, bottom, right))                     {                               board[row][col] = '-';                          board[row][col + 1] = '+';                              if (solveMagnetPuzzle(board, row, col + 2,                                              top, left, bottom, right, str))                                         return true;                            // if it doesn't lead to a solution, backtrack                          board[row][col] = 'X';                          board[row][col + 1] = 'X';                      }               }               // if vertical slot contains T and B            if (str[row][col] == 'T' && str[row + 1][col] == 'B')           {                       // put ('+', '-') pair and recur                        if (isSafe(board, row, col, '+', top, left, bottom, right) &&                           isSafe(board, row + 1, col, '-', top, left, bottom, right))                     {                               board[row][col] = '+';                          board[row + 1][col] = '-';                              if (solveMagnetPuzzle(board, row, col + 1,                                              top, left, bottom, right, str))                                         return true;                            // if it doesn't lead to a solution, backtrack                          board[row][col] = 'X';                          board[row + 1][col] = 'X';                      }                       // put ('-', '+') pair and recur                        if (isSafe(board, row, col, '-', top, left, bottom, right) &&                           isSafe(board, row + 1, col, '+', top, left, bottom, right))                     {                               board[row][col] = '-';                          board[row + 1][col] = '+';                              if (solveMagnetPuzzle(board, row, col + 1,                                              top, left, bottom, right, str))                                         return true;                            // if it doesn't lead to a solution, backtrack                          board[row][col] = 'X';                          board[row + 1][col] = 'X';                      }               }               // ignore current cell and recur                if (solveMagnetPuzzle(board, row, col + 1,                              top, left, bottom, right, str))                         return true;            // if no solution is possible, return false             return false;   }       public static void solveMagnetPuzzle(int top[], int left[], int bottom[],                                                       int right[], char str[][])      {               // to store result              char board[][] = new char[M][N];                // initalize all cells by 'X'           for (int i = 0; i < M; i++)                  Arrays.fill(board[i], 'X');             // start from (0, 0) cell               if (!solveMagnetPuzzle(board, 0, 0, top, left, bottom, right, str))             {                       System.out.println("Solution does not exist");                  return;                 }               // print result if given configuration is solvable              printSolution(board);   }       public static void main(String[] args)  {               // indicates the count of + or - along the top (+), bottom (-),                 // left (+) and right (-) edges respectively.           // value of -1 indicates any number of + or - signs             final int top[] = { 1, -1, -1, 2, 1, -1 };              final int bottom[] = { 2, -1, -1, 2, -1, 3 };           final int left[] = { 2, 3, -1, -1, -1 };                final int right[] = { -1, -1, -1, 1, -1 };              // rules matrix                 char str[][] =          {                       { 'L', 'R', 'L', 'R', 'T', 'T' },                       { 'L', 'R', 'L', 'R', 'B', 'B' },                       { 'T', 'T', 'T', 'T', 'L', 'R' },                       { 'B', 'B', 'B', 'B', 'T', 'T' },                       { 'L', 'R', 'L', 'R', 'B', 'B' }                };              solveMagnetPuzzle(top, left, bottom, right, str);       } }

4) Find shortest path in maze:

import java.util.ArrayDeque; import java.util.Queue; // queue node used in BFS class Node {         // (x, y) represents matrix cell coordinates    // dist represent its minimum distance from the source  int x, y, dist;         Node(int x, int y, int dist) {          this.x = x;             this.y = y;             this.dist = dist;       } }; class Util {       // M x N matrix         private static final int M = 10;        private static final int N = 10;        // Below arrays details all 4 possible movements from a cell    private static final int row[] = { -1, 0, 0, 1 };       private static final int col[] = { 0, -1, 1, 0 };       // Function to check if it is possible to go to position (row, col)     // from current position. The function returns false if (row, col)      // is not a valid position or has value 0 or it is already visited      private static boolean isValid(int mat[][], boolean visited[][],                                                                                                        int row, int col)       {               return (row >= 0) && (row < M) && (col >= 0) && (col < N)                                    && mat[row][col] == 1 && !visited[row][col];   }       // Find Shortest Possible Route in a matrix mat from source     // cell (i, j) to destination cell (x, y)       private static void BFS(int mat[][], int i, int j, int x, int y)        {               // construct a matrix to keep track of visited cells            boolean[][] visited = new boolean[M][N];                // create an empty queue                Queue<Node> q = new ArrayDeque<>();                 // mark source cell as visited and enqueue the source node              visited[i][j] = true;           q.add(new Node(i, j, 0));               // stores length of longest path from source to destination             int min_dist = Integer.MAX_VALUE;               // run till queue is not empty          while (!q.isEmpty())            {                       // pop front node from queue and process it                     Node node = q.poll();                   // (i, j) represents current cell and dist stores its                   // minimum distance from the source                     i = node.x;                     j = node.y;                     int dist = node.dist;                   // if destination is found, update min_dist and stop                    if (i == x && j == y)                   {                               min_dist = dist;                                break;                  }                       // check for all 4 possible movements from current cell                         // and enqueue each valid movement                      for (int k = 0; k < 4; k++)                  {                               // check if it is possible to go to position                            // (i + row[k], j + col[k]) from current position                               if (isValid(mat, visited, i + row[k], j + col[k]))                              {                                       // mark next cell as visited and enqueue it                                     visited[i + row[k]][j + col[k]] = true;                                         q.add(new Node(i + row[k], j + col[k], dist + 1));                              }                       }               }               if (min_dist != Integer.MAX_VALUE) {                    System.out.print("The shortest path from source to destination "                                                        + "has length " + min_dist);            }               else {                  System.out.print("Destination can't be reached from source");           }       }       // Shortest path in a Maze      public static void main(String[] args)  {               // input maze           int[][] mat =           {                       { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },                       { 0, 1, 1, 1, 1, 1, 0, 1, 0, 1 },                       { 0, 0, 1, 0, 1, 1, 1, 0, 0, 1 },                       { 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 },                       { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 },                       { 1, 0, 1, 1, 1, 0, 0, 1, 1, 0 },                       { 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 },                       { 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 },                       { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 },                       { 0, 0, 1, 0, 0, 1, 1, 0, 0, 1 },               };              // Find shortest path from source (0, 0) to             // destination (7, 5)           BFS(mat, 0, 0, 7, 5);   } }

5) Find Longest possible route in a matrix:

class Main {   // M x N matrix         private static final int M = 10;        private static final int N = 10;        // check if it is possible to go to position (x, y) from        // current position. The function returns false if the cell     // has value 0 or it is already visited.        private static boolean isSafe(int mat[][], int visited[][], int x, int y)       {               if (mat[x][y] == 0 || visited[x][y] != 0)                       return false;           return true;    }       // if not a valid position, return false        private static boolean isValid(int x, int y)    {               if (x < M && y < N && x >= 0 && y >= 0)                     return true;            return false;   }       // Find Longest Possible Route in a Matrix mat from source      // cell (0, 0) to destination cell (x, y)       // 'max_dist' stores length of longest path from source to      // destination found so far and 'dist' maintains length of path from    // source cell to the current cell (i, j)       public static int findLongestPath(int mat[][], int visited[][], int i,                                                          int j, int x, int y, int max_dist, int dist)    {               // if destination not possible from current cell                if (mat[i][j] == 0) {                   return 0;               }               // if destination is found, update max_dist             if (i == x && j == y)           {                       return Integer.max(dist, max_dist);             }               // set (i, j) cell as visited           visited[i][j] = 1;              // go to bottom cell            if (isValid(i + 1, j) && isSafe(mat, visited, i + 1, j)) {                      max_dist = findLongestPath(mat, visited, i + 1, j, x, y,                                                                                max_dist, dist + 1);            }               // go to right cell             if (isValid(i, j + 1) && isSafe(mat, visited, i, j + 1)) {                      max_dist = findLongestPath(mat, visited, i, j + 1, x, y,                                                                                max_dist, dist + 1);            }               // go to top cell               if (isValid(i - 1, j) && isSafe(mat, visited, i - 1, j)) {                      max_dist = findLongestPath(mat, visited, i - 1, j, x, y,                                                                                max_dist, dist + 1);            }               // go to left cell              if (isValid(i, j - 1) && isSafe(mat, visited, i, j - 1)) {                      max_dist = findLongestPath(mat, visited, i, j - 1, x, y,                                                                                max_dist, dist + 1);            }               // Backtrack - Remove (i, j) from visited matrix                visited[i][j] = 0;              return max_dist;        }       public static void main(String[] args)  {               // input matrix                 int mat[][] =           {                               { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 },                               { 1, 0, 1, 0, 1, 1, 1, 0, 1, 1 },                               { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },                               { 0, 0, 0, 0, 1, 0, 0, 1, 0, 0 },                               { 1, 0, 0, 0, 1, 1, 1, 1, 1, 1 },                               { 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 },                               { 1, 0, 0, 0, 1, 0, 0, 1, 0, 1 },                               { 1, 0, 1, 1, 1, 1, 0, 0, 1, 1 },                               { 1, 1, 0, 0, 1, 0, 0, 0, 0, 1 },                               { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 }                };              // construct a matrix to keep track of visited cells            int[][] visited= new int[N][N];                 // (0,0) are the source cell coordinates and (5, 7) are the             // destination cell coordinates                 int max_dist = findLongestPath(mat, visited, 0, 0, 5, 7, 0, 0);                 System.out.println("Maximum length path is " + max_dist);       } }

6) Find path from source to destination in a matrix that satisfies given constraints:

import java.util.ArrayList; import java.util.List; // Object of Node class stores cell coordinates of the matrix class Node {        int first, second;      public Node(int first, int second) {            this.first = first;             this.second = second;   }       @Override       public boolean equals(Object ob) {              Node node = (Node) ob;          return (first == node.first && second == node.second);  }       @Override       public int hashCode() {                 return 31 * first + second;     } } class Tour {        // N x N matrix         private static final int N = 10;        // Below arrays details all 4 possible movements from a cell    private static final int row[] = { -1, 0, 0, 1 };       private static final int col[] = { 0, -1, 1, 0 };       // Function to check if it is possible to go to position pt     // from current position. The function returns false if pt is   // not a valid position or it is already visited        private static boolean isValid(List<Node> path, Node pt)  {               return pt.first >= 0 && pt.first < N &&                           pt.second >= 0 && pt.second < N &&                                !path.contains(pt);     }       // Function to print the complete path from source to destination       private static void printPath(List<Node> path)    {               for (Node cell: path) {                         System.out.print("(" + cell.first + ", " + cell.second + ") ");                 }       }       // Find route in a matrix mat from source cell (0, 0) to        // destination cell (N-1, N-1)  public static boolean findPath(int mat[][], List<Node> path, Node curr)   {               // include current vertex in the path           path.add(curr);                 // if destination is found, return true                 if (curr.first == N - 1 && curr.second == N - 1)                        return true;            // value of current cell                int n = mat[curr.first][curr.second];           // check all 4 possible movements from current cell             // and recur for each valid movement            for (int i = 0; i < 4; i++)          {                       // get next position using value of current cell                        int x = curr.first + row[i] * n;                        int y = curr.second + col[i] * n;                       Node next = new Node(x, y);                     // check if it is possible to go to position (x, y)                     // from current position                        if (isValid(path, next) && findPath(mat, path, next))                           return true;            }               // Backtrack - exclude current vertex in the path               path.remove(path.size() - 1);           return false;   }       public static void main(String[] args)  {               int mat[][] =           {                       { 7, 1, 3, 5, 3, 6, 1, 1, 7, 5 },                       { 2, 3, 6, 1, 1, 6, 6, 6, 1, 2 },                       { 6, 1, 7, 2, 1, 4, 7, 6, 6, 2 },                       { 6, 6, 7, 1, 3, 3, 5, 1, 3, 4 },                       { 5, 5, 6, 1, 5, 4, 6, 1, 7, 4 },                       { 3, 5, 5, 2, 7, 5, 3, 4, 3, 6 },                       { 4, 1, 4, 3, 6, 4, 5, 3, 2, 6 },                       { 4, 4, 1, 7, 4, 3, 3, 1, 4, 2 },                       { 4, 4, 5, 1, 5, 2, 3, 5, 3, 5 },                       { 3, 6, 3, 5, 2, 2, 6, 4, 2, 1 }                };              List<Node> path = new ArrayList<>();                Node source = new Node(0, 0);           // Find route in a matrix mat from source cell (0, 0) to                // destination cell (N-1, N-1)          if (findPath(mat, path, source))                        printPath(path);        } }

7) Find total number of unique paths in a maze from source to destination:

import java.util.Arrays; class Combinations {   private static final int N = 4;         // Check if cell (x, y) is valid or not         private static boolean isValidCell(int x, int y)        {               if (x < 0 || y < 0 || x >= N || y >= N)                     return false;           return true;    }       private static int countPaths(int maze[][], int x, int y,                                                                boolean visited[][], int count)        {               // if destination (bottom-rightmost cell) is found,             // increment the path count             if (x == N - 1 && y == N - 1)           {                       count++;                        return count;           }               // mark current cell as visited                 visited[x][y] = true;           // if current cell is a valid and open cell             if (isValidCell(x, y) && maze[x][y] == 1)               {                       // go down (x, y) --> (x + 1, y)                     if (x + 1 < N && !visited[x + 1][y])                                 count = countPaths(maze, x + 1, y, visited, count);                     // go up (x, y) --> (x - 1, y)                       if (x - 1 >= 0 && !visited[x - 1][y])                                count = countPaths(maze, x - 1, y, visited, count);                     // go right (x, y) --> (x, y + 1)                    if (y + 1 < N && !visited[x][y + 1])                                 count = countPaths(maze, x, y + 1, visited, count);                     // go left (x, y) --> (x, y - 1)                     if (y - 1 >= 0 && !visited[x][y - 1])                                count = countPaths(maze, x, y - 1, visited, count);             }               // backtrack from current cell and remove it from current path          visited[x][y] = false;          return count;   }       public static void main(String[] args)  {               int maze[][] =          {                       { 1, 1, 1, 1 },                         { 1, 1, 0, 1 },                         { 0, 1, 0, 1 },                         { 1, 1, 1, 1 }          };              // stores number of unique paths from source to destination             int count = 0;          // 2D matrix to keep track of cells involved in current path            boolean[][] visited = new boolean[N][N];                // start from source cell (0, 0)                count = countPaths(maze, 0, 0, visited, count);                 System.out.println("Total number of unique paths are " + count);        } }

8) Print all Hamiltonian path present in a graph:

import java.util.ArrayList; import java.util.Arrays; import java.util.List; // data structure to store graph edges class Edge {  int source, dest;       public Edge(int source, int dest) {             this.source = source;           this.dest = dest;       } }; // class to represent a graph object class Graph {         // An array of Lists to represent adjacency list        List<List<Integer>> adjList = null;         // Constructor  Graph(List<Edge> edges, int N)    {               adjList = new ArrayList<>(N);             for (int i = 0; i < N; i++) {                        adjList.add(i, new ArrayList<>());                }               // add edges to the undirected graph            for (int i = 0; i < edges.size(); i++)               {                       int src = edges.get(i).source;                  int dest = edges.get(i).dest;                   adjList.get(src).add(dest);                     adjList.get(dest).add(src);             }       } } class HamiltonianPaths {    public static void printAllHamiltonianPaths(Graph g, int v,                                             boolean[] visited, List<Integer> path, int N)     {               // if all the vertices are visited, then                // hamiltonian path exists              if (path.size() == N)           {                       // print hamiltonian path                       for (int i : path)                              System.out.print(i + " ");                      System.out.println();                   return;                 }               // Check if every edge starting from vertex v leads             // to a solution or not                 for (int w : g.adjList.get(v))          {                       // process only unvisited vertices as hamiltonian                       // path visits each vertex exactly once                         if (!visited[w])                        {                               visited[w] = true;                              path.add(w);                            // check if adding vertex w to the path leads                           // to solution or not                           printAllHamiltonianPaths(g, w, visited, path, N);                               // Backtrack                            visited[w] = false;                             path.remove(path.size()-1);                     }               }       }       public static void main(String[] args)  {               // List of graph edges as per above diagram             List<Edge> edges = Arrays.asList(                                 new Edge(0, 1), new Edge(0, 2), new Edge(0, 3),                                 new Edge(1, 2), new Edge(1, 3), new Edge(2, 3)          );              // Set number of vertices in the graph          final int N = 4;                // create a graph from edges            Graph g = new Graph(edges, N);          // starting node                int start = 0;          // add starting node to the path                List<Integer> path = new ArrayList<>();             path.add(start);                // mark start node as visited           boolean[] visited = new boolean[N];             visited[start] = true;          printAllHamiltonianPaths(g, start, visited, path, N);   } }

9) Print all k-colourable configurations of the graph(vertex colouring of graph):

import java.util.ArrayList; import java.util.Arrays; import java.util.List; // data structure to store graph edges class Edge {  int source, dest;       public Edge(int source, int dest) {             this.source = source;           this.dest = dest;       } }; // class to represent a graph object class Graph {         // An array of Lists to represent adjacency list        List<List<Integer>> adjList = null;         // Constructor  Graph(List<Edge> edges, int N)    {               adjList = new ArrayList<>(N);             for (int i = 0; i < N; i++) {                        adjList.add(i, new ArrayList<>());                }               // add edges to the undirected graph            for (int i = 0; i < edges.size(); i++)               {                       int src = edges.get(i).source;                  int dest = edges.get(i).dest;                   adjList.get(src).add(dest);                     adjList.get(dest).add(src);             }       } } class KColorable {  // string array to store colors (10-colorable graph)    private static String COLORS[] = {"", "BLUE", "GREEN", "RED", "YELLOW",                                         "ORANGE", "PINK", "BLACK", "BROWN", "WHITE", "PURPLE"};         // Function to check if it is safe to assign color c to vertex v        private static boolean isSafe(Graph graph, int[] color, int v, int c)   {               // check color of every adjacent vertex of v            for (int u : graph.adjList.get(v))                      if (color[u] == c)                              return false;           return true;    }       public static void kColorable(Graph g, int[] color, int k, int v, int N)        {               // if all colors are assigned, print the solution               if (v == N)             {                       for (v = 0; v < N; v++)                              System.out.printf("%-8s" , COLORS[color[v]]);                   System.out.println();                   return;                 }               // try all possible combinations of available colors            for (int c = 1; c <= k; c++)                 {                       // if it is safe to assign color c to vertex v                  if (isSafe(g, color, v, c))                     {                               // assign color c to vertex v                           color[v] = c;                           // recur for next vertex                                kColorable(g, color, k, v + 1, N);                              // backtrack                            color[v] = 0;                   }               }       }       public static void main(String[] args)  {               // List of graph edges as per above diagram             List<Edge> edges = Arrays.asList(                                 new Edge(0, 1), new Edge(0, 4),                                 new Edge(0, 5), new Edge(4, 5),                                 new Edge(1, 4), new Edge(1, 3),                                 new Edge(2, 3), new Edge(2, 4)          );              // Set number of vertices in the graph          final int N = 6;                // create a graph from edges            Graph g = new Graph(edges, N);          int k = 3;              int[] color = new int[N];               // print all k-colorable configurations of the graph            kColorable(g, color, k, 0, N);  } }

10) Find all permutations of agiven string:

// Java program to print all permutations of a // given string. public class Permutation { public static void main(String[] args) { String str = "ABC"; int n = str.length(); Permutation permutation = new Permutation(); permutation.permute(str, 0, n-1); } /** * permutation function * @param str string to calculate permutation for * @param l starting index * @param r end index */ private void permute(String str, int l, int r) { if (l == r) System.out.println(str); else { for (int i = l; i <= r; i++) { str = swap(str,l,i); permute(str, l+1, r); str = swap(str,l,i); } } } /** * Swap Characters at position * @param a string value * @param i position 1 * @param j position 2 * @return swapped string */ public String swap(String a, int i, int j) { char temp; char[] charArray = a.toCharArray(); temp = charArray[i] ; charArray[i] = charArray[j]; charArray[j] = temp; return String.valueOf(charArray); } } 

11) All combinations of elements satisfying given constraints:

import java.util.Arrays; class Combinations {  // Find all combinations that satisfies given constraints       public static void findAllCombinations(int[] arr, int elem, int n)      {               // if all elements are filled, print the solution               if (elem > n)                {                       for (int i : arr)                               System.out.print(i + " ");                      System.out.println();                   return;                 }               // try all possible combinations for element elem               for (int i = 0; i < 2*n; i++)                {                       // if position i and (i+elem+1) are not occupied in the vector                  if (arr[i] == -1 && (i + elem + 1) < 2*n &&                                  arr[i + elem + 1] == -1)                        {                               // place elem at position i and (i+elem+1)                              arr[i] = elem;                          arr[i + elem + 1] = elem;                               // recur for next element                               findAllCombinations(arr, elem + 1, n);                          // backtrack (remove elem from position i and (i+elem+1) )                              arr[i] = -1;                            arr[i + elem + 1] = -1;                         }               }       }       public static void main(String[] args)  {               // given number                 int n = 7;              // create a vector of double the size of given number with              // all its elements initialized by -1           int[] arr = new int[2*n];               Arrays.fill(arr, -1);           // start from element 1                 int elem = 1;           findAllCombinations(arr, elem, n);      } }

12) Find all binary strings that can be formed from given wildcard pattern:

class Combinations { // Find all binary strings that can be formed from given // wildcard pattern private static void printAllCombinations(char pattern[], int i) { if (i == pattern.length) { System.out.println(pattern); return; } // if the current character is '?' if (pattern[i] == '?') { for (char ch = '0'; ch <= '1'; ch++) { // replace '?' with 0 and 1 pattern[i] = ch; // recur for the remaining pattern printAllCombinations(pattern, i + 1); // backtrack as array is passed by reference to the function pattern[i] = '?'; } return; } // if the current character is 0 or 1, ignore it and // recur for the remaining pattern printAllCombinations(pattern, i + 1); } public static void main(String[] args) { char[] pattern = "1?11?00?1?".toCharArray(); printAllCombinations(pattern, 0); } }

Therefore all the programs in java are given as above.