Tag

Backtracking

Browsing

Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that is a cycle. Hamiltonian Path problem is actually looking for a longest simple path in a graph. This is a classic NP-complete problem. Write a program to find the Hamiltonian Cycle. source Code package com.dsacode.Algorithm.backtracking; import java.util.Arrays; public class HamiltonianCycle { private int V, pathCount; private int[] path; private int[][] graph; public HamiltonianCycle(int V){ this.V=V; } public void findHamiltonianCycle(int[][] g) { graph = g; path = new int[graph.length]; Arrays.fill(path, -1); try { path[0] = 0;…

Find the non-empty subset whose sum is zero from given set of the integers. For example, given the set {-7, -3, -2, 5, 8}, the answer is yes because the subset {-3, -2, 5} sums to zero. This problem is an example of NP-complete. Write a program to give the total of values equal to sum S. source Code package com.dsacode.Algorithm.backtracking; public class SubsetSum { public static boolean subSetSumRecur(int [] mySet, int n, int goal){ if (goal ==0){ return true;} if ((goal < 0)|( n >= mySet.length)) return false; if (subSetSumRecur(mySet,n+1,goal – mySet[n])){ System.out.print(mySet[n]+” “); return true;} if (subSetSumRecur(mySet,n+1,goal)) return…

A Maze is given matrix and Rat start from upper left and should reach to lower right. The Rat starts from source to destination and moves only forward and down direction. Given a maze, 4 x 4 matrix. A rat has to find a path from source to destination. Rat start from left top corner and go to right bottom destination. There are few cells which are dead end which means rat cannot enter into those cells. Write a program to rat start from source to destination? source Code package com.dsacode.Algorithm.backtracking; import java.util.Arrays; public class RatinMaze { public int[][] solution;…

The eight queen’s puzzle is the problem of placing eight chess queens on an 8 x 8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. Backtracking eliminates or avoids the partial candidate solutions as soon as it finds that that path cannot lead to a solution. We are given 4 x 4 chessboard and we need to place 4 queens in non-attacking places on this board. source Code package com.dsacode.Algorithm.backtracking; public class NQueens { int[] x; public NQueens(int N) { x = new int[N];…

Write a program to print all the possible combination of given string. source Code package com.dsacode.Algorithm.recursive; public class AllPossiblecombinations { private StringBuilder output = new StringBuilder(); private final String inputstring; public AllPossiblecombinations( final String str ){ inputstring = str; System.out.println(“The input string is : ” + inputstring); } public void combine() { combine( 0 ); } private void combine(int start ){ for( int i = start; i < inputstring.length(); ++i ){ output.append( inputstring.charAt(i) ); System.out.println( output ); if ( i < inputstring.length() ) combine( i + 1); output.setLength( output.length() – 1 ); } } public static void main (String args[])…

Graph and tree nodes can be traversed using the backtracking technique. Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. DFS takes less memory compare than Breadth-first search and not necessary to store all of the child pointers at each level. DFS technique used in web-crawling, Finding connected components, Topological sorting, Finding the bridges of a graph, Finding strongly connected components, Solving puzzles with only one solution, such as mazes, maze generation may use a randomized depth-first search, Finding connectivity in graphs. source Code package com.dsacode.Algorithm.backtracking; import java.util.Stack; class Vertex{ public char label; public…