Print all Hamiltonian paths present in a graph
Given an undirected graph, print all Hamiltonian paths present in it. The Hamiltonian path in an undirected or directed graph is a path that visits each vertex exactly once.
Tag: Hard
Travelling Salesman Problem using Branch and Bound
Given a set of cities and the distance between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.
Magnet Puzzle
We are given a set of bipolar magnets, each domino-shaped. The objective is to place magnets on an M × N board, which satisfies a set of conditions where both M and N are not odd.
Print all possible Knight’s tours on a chessboard
Given a chessboard, print all sequences of moves of a knight on a chessboard such that the knight visits every square only once.
Print all possible solutions to N–Queens problem
The N–queens puzzle is the problem of placing N chess queens on an N × N chessboard so that no two queens threaten each other. Thus, the solution requires that no two queens share the same row, column, or diagonal.
Calculate the size of the largest plus of 1’s in a binary matrix
Given a square matrix of 0’s and 1’s, calculate the size of the largest plus formed by 1’s.
Merge `M` sorted lists each containing `N` elements
Given m sorted lists, each containing n elements, print them efficiently in sorted order.
Find the smallest range with at least one element from each of the given lists
Given M sorted lists of variable length, efficiently compute the smallest range, including at least one element from each list.
3–partition problem extended | Printing all partitions
Given an array of positive integers, which can be partitioned into three disjoint subsets having the same sum, print the partitions.
Shortest Superstring Problem
Given a list of strings where no string is a substring of another, find the shortest string that contains each string in the list as a substring.
Kruskal’s Algorithm for finding Minimum Spanning Tree
Given an undirected, connected and weighted graph, construct a minimum spanning tree out of it using Kruskal’s Algorithm.
Chess Knight Problem | Find the shortest path from source to destination
Given a chessboard, find the shortest distance (minimum number of steps) taken by a knight to reach a given destination from a given source.