1- N Queen Problem

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no
two queens attack each other. Queen can attack horizontally, vertically and diagonaly.For
example, following are two solutions for 4 Queen Problem

https://www.geeksforgeeks.org/printing-solutions-n-queen-problem/?ref=lbp
2-K Battle Ship
You are given NxM matrix. You have K battle ships. You are also given 3 parameters for each of
the battle ship - rowAttack, columnAttack and diagonalAttack. Each telling how many cells in a
row/column/diagonal(on each direction) the ship can attack. Your task is find whether the ships
can be placed in the board such that no one attacks each other.

To shed more light on the attacks, say if the ship is placed at (5,5) and if it's column attack range
is 3, then it can attack any ship from (5,2) to (5,8).

Link https://stackoverflow.com/questions/23726791/variation-of-n-queens

3- A* Search Algorithm
To approximate the shortest path in real-life situations, like- in maps, games where there can
be many hindrances.
We can consider a 2D Grid having several obstacles and we start from a source cell (coloured
red below) to reach towards a goal cell (coloured green below)

What is A* Search Algorithm?

A* Search algorithm is one of the best and popular technique used in path-finding and graph
traversals.

Informally speaking, A* Search algorithms, unlike other traversal techniques, it has “brains”.
 What it means is that it is really a smart algorithm which separates it from the other
conventional algorithms. This fact is cleared in detail in below sections.
And it is also worth mentioning that many games and web-based maps use this algorithm to
find the shortest path very efficiently (approximation).

https://www.geeksforgeeks.org/a-search-algorithm/

4- Hidato Puzzle
The rules are:

 You are given a grid with some numbers placed in it. The other squares in the grid will be blank.
 The grid is not necessarily rectangular.
 The grid may have holes in it.
 The grid is always connected.
 The number “1” is always present, as is another number that is equal to the number of squares
in the grid. Other numbers are present so as to force the solution to be unique.
 It may be assumed that the difference between numbers present on the grid is not greater than
lucky 13.
 The aim is to place a natural number in each blank square so that in the sequence of numbered
squares from “1” upwards, each square is in the wp:Moore neighborhood of the squares
immediately before and after it in the sequence (except for the first and last squares, of course,
which only have one-sided constraints).
 Thus, if the grid was overlaid on a chessboard, a king would be able to make legal moves along
the path from first to last square in numerical order.
 A square may only contain one number.
 In a proper Hidato puzzle, the solution is unique.

Solution

https://rosettacode.org/wiki/Solve_a_Hidato_puzzle
5- Knight Tour Problem
the knight is placed on the first block of an empty board and, moving according to the rules of
chess, must visit each square exactly once.
Path followed by Knight to cover all the cells
Following is chessboard with 8 x 8 cells. Numbers in cells indicate move number of Knight.

https://www.geeksforgeeks.org/the-knights-tour-problem-backtracking-1/

6- Numberix Puzzle
Numbrix puzzles are similar to Hidato. The most important difference is that it is only possible
to move 1 node left, right, up, or down (sometimes referred to as the Von Neumann
neighborhood). Published puzzles also tend not to have holes in the grid and may not always
indicate the end node. Two examples follow:

0 0 0 0 0 0 0 0 0
0 0 46 45 0 55 74 0 0
0 38 0 0 43 0 0 78 0
0 35 0 0 0 0 0 71 0
0 0 33 0 0 0 59 0 0
0 17 0 0 0 0 0 67 0
0 18 0 0 11 0 0 64 0
0 0 24 21 0 1 2 0 0
0 0 0 0 0 0 0 0 0
Solution

49 50 51 52 53 54 75 76 81
48 47 46 45 44 55 74 77 80
37 38 39 40 43 56 73 78 79
36 35 34 41 42 57 72 71 70
31 32 33 14 13 58 59 68 69
30 17 16 15 12 61 60 67 66
29 18 19 20 11 62 63 64 65
28 25 24 21 10 1 2 3 4
27 26 23 22 9 8 7 6 5

7- Magnet Puzzle
The puzzle game Magnets involves placing a set of domino-shaped magnets (or electrets or
other polarized objects) in a subset of slots on a M X N board so as to satisfy a set of
constraints. For example, the puzzle on the left has the solution shown on the right

Each slot contains either a blank entry (indicated by ‘x’s), or a “magnet” with a positive and
negative end. The numbers along the left and top sides show the numbers of ‘+’ squares in
particular rows or columns. Those along the right and bottom show the number of ‘-’ signs in
particular rows or columns. Rows and columns without a number at one or both ends are
unconstrained as to the number of ‘+’ or ‘-’ signs, depending on which number is not present. In
addition to fulfilling these numerical constraints, a puzzle solution must also satisfy the
constraint that no two orthogonally touching squares may have the same sign (diagonally
joined squares are not constrained).
You are given top[], bottom[], left[], right[] arrays indicates the count of + or – along the top(+),
bottom(-), left(+) and right(-) edges respectively. Values of -1 indicate any number of + and –
signs. Also given matrix rules[][] contain any one T, B, L or R characters. For a vertical slot in the
board, T indicates its top end and B indicates the bottom end. For a horizontal slot in the board,
L indicates left end and R indicates the right end.
input : M = 5, N = 6
top[] = { 1, -1, -1, 2, 1, -1 }
bottom[] = { 2, -1, -1, 2, -1, 3 }
left[] = { 2, 3, -1, -1, -1 }
right[] = { -1, -1, -1, 1, -1 }
rules[][] = { { 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 }};
Output : + - + - X -
-+-+X+
XX+-+-
XX-+X+
-+XXX-

Input : M = 4, N = 3
top[] = { 2, -1, -1 }
bottom[] = { -1, -1, 2 }
left[] = { -1, -1, 2, -1 }
right[] = { 0, -1, -1, -1 }
rules[][] = { { T, T, T },
{ B, B, B },
{ T, L, R },
 { B, L, R } };
Output : + X +
–X–
+–+
–+–

8- Rat In a Maze
A Maze is given as N*N binary matrix of blocks where source block is the upper left most block
i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1]. A rat starts
from source and has to reach the destination. The rat can move only in two directions: forward
and down.
In the maze matrix, 0 means the block is a dead end and 1 means the block can be used in the
path from source to destination. Note that this is a simple version of the typical Maze problem.
For example, a more complex version can be that the rat can move in 4 directions and a more
complex version can be with a limited number of moves.

Solution
9- Print all shortest route in a grid
Given a matrix of N*M order. Find the shortest distance from a source cell to a destination cell,
traversing through limited cells only. Also you can move only up, down, left and right. If found
output the distance else -1. s represents ‘source’ d represents ‘destination’ * represents cell
you can travel 0 represents cell you can not travel This problem is meant for single source and
destination.
https://www.techiedelight.com/print-triplets-array-sum-less-equal-given-number/

10- Print longest route in a grid

https://www.techiedelight.com/find-longest-possible-route-matrix/

11- Find total number of unique path in maze from source to destination
https://www.techiedelight.com/find-total-number-unique-paths-maze-source-destination/
12- Subset Sum Problem
Subset sum problem is to find subset of elements that are selected from a given set whose sum
adds up to a given number K. We are considering the set contains non-negative values. It is
assumed that the input set is unique (no duplicates are presented)
https://www.geeksforgeeks.org/subset-sum-backtracking-4/

13- Coin Change Problem

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S
= { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins
doesn’t matter.
For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So
output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3},
{2,2,6}, {2,3,5} and {5,5}. So the output should be 5.
https://www.geeksforgeeks.org/coin-change-dp-7/

14- Cutting a Rod

Given a rod of length n inches and an array of prices that contains prices of all pieces of size
smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the
pieces. For example, if length of the rod is 8 and the values of different pieces are given as
following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)

length | 1 2 3 4 5 6 7 8
--------------------------------------------
price | 1 5 8 9 10 17 17 20
And if the prices are as following, then the maximum obtainable value is 24 (by cutting in eight
pieces of length 1)
length | 1 2 3 4 5 6 7 8
--------------------------------------------
price | 3 5 8 9 10 17 17 20
https://www.geeksforgeeks.org/cutting-a-rod-dp-13/
.

15- Print all triplets in an array with sum is less than or equal to given number
https://www.techiedelight.com/print-triplets-array-sum-less-equal-given-number/

16- K Partition Probem

https://www.techiedelight.com/k-partition-problem-print-all-subsets/

17- find ways to calculate a target from array use addition and substraction
operator
https://www.techiedelight.com/find-ways-calculate-target-elements-array/

18- Sudoku Problem

Given a partially filled 9×9 2D array ‘grid[9][9]’, the goal is to assign digits (from 1 to 9) to the
empty cells so that every row, column, and subgrid of size 3×3 contains exactly one instance of
the digits from 1 to 9.
https://www.geeksforgeeks.org/sudoku-backtracking-7/

19- longest common subsequence

Given two sequences, print the longest subsequence present in both of them.
Examples:
LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

https://www.geeksforgeeks.org/printing-longest-common-subsequence/

20- longest palindromic subsequence

Given a sequence, print a longest palindromic subsequence of it.
Examples :
Input : BBABCBCAB
Output : BABCBAB
The above output is the longest
palindromic subsequence of given
sequence. "BBBBB" and "BBCBB" are
also palindromic subsequences of
the given sequence, but not the
longest ones.

Input : GEEKSFORGEEKS
Output : Output can be either EEKEE
or EESEE or EEGEE, ..

21- longest increasing subsequence

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest
subsequenceof a given sequence such that all elements of the subsequence are sorted in
increasing order.
For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50,
60, 80}.

https://www.geeksforgeeks.org/construction-of-longest-increasing-subsequence-using-
dynamic-programming/

22- Text Segmentation

Given a valid sentence without any spaces between the words and a dictionary of valid English
words, find all possible ways to break the sentence in individual dictionary words.
Example
Consider the following dictionary
{ i, like, sam, sung, samsung, mobile, ice,
cream, icecream, man, go, mango}

Input: "ilikesamsungmobile"
Output: i like sam sung mobile
i like samsung mobile

Input: "ilikeicecreamandmango"
Output: i like ice cream and man go
i like ice cream and mango
i like icecream and man go
i like icecream and mango

https://www.geeksforgeeks.org/word-break-problem-using-backtracking/?ref=lbp

23- Edit Distance

Given two strings str1 and str2 and below operations that can performed on str1. Find
minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.
1. Insert
2. Remove
3. Replace
All of the above operations are of equal cost.

Examples:
Input: str1 = "geek", str2 = "gesek"
Output: 1
We can convert str1 into str2 by inserting a 's'.
24- Edit Distance
Given two strings str1 and str2 and below operations that can performed on str1. Find
minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.
1-Insert
2-Remove
All of the above operations are of equal cost.

Examples:
Input: str1 = "geek", str2 = "gesek"
Output: 1
We can convert str1 into str2 by inserting a 's'.

25- Optimal BST

Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts,
where freq[i] is the number of searches to keys[i]. Construct a binary search tree of all keys such
that the total cost of all the searches is as small as possible.
Let us first define the cost of a BST. The cost of a BST node is level of that node multiplied by its
frequency. Level of root is 1.
Examples:
Input: keys[] = {10, 12}, freq[] = {34, 50}
There can be following two possible BSTs
10 12
\ /
12 10
I II
Frequency of searches of 10 and 12 are 34 and 50 respectively.
The cost of tree I is 34*1 + 50*2 = 134
The cost of tree II is 50*1 + 34*2 = 118
https://www.geeksforgeeks.org/optimal-binary-search-tree-dp-24/

https://www.techiedelight.com/find-optimal-cost-to-construct-binary-search-tree/
26- Graph Coloring
Given an undirected graph and a number m, determine if the graph can be coloured with at
most m colours such that no two adjacent vertices of the graph are colored with the same
color. Here coloring of a graph means the assignment of colors to all vertices.
Input-Output format:
Input:
1. A 2D array graph[V][V] where V is the number of vertices in graph and graph[V][V] is
adjacency matrix representation of the graph. A value graph[i][j] is 1 if there is a direct
edge from i to j, otherwise graph[i][j] is 0.
2. An integer m which is the maximum number of colors that can be used.
Output:
An array color[V] that should have numbers from 1 to m. color[i] should represent the color
assigned to the ith vertex. The code should also return false if the graph cannot be colored with
m colors.
Example:
Input:
graph = {0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0}
Output:
Solution Exists:
Following are the assigned colors
1 2 3 2
Explanation: By coloring the vertices
with following colors, adjacent
vertices does not have same colors

https://www.geeksforgeeks.org/m-coloring-problem-backtracking-5/

27- find all topological ordering in DAG

https://www.techiedelight.com/find-all-possible-topological-orderings-of-dag/

28- find all path between two vertices in graph

https://www.techiedelight.com/find-path-between-vertices-directed-graph/
29- hamiltonian cycle
https://www.techiedelight.com/print-all-hamiltonian-path-present-in-a-graph/

30- find minimum number possible by doing atmost k swaps

https://www.techiedelight.com/find-minimum-number-possible-k-swaps/

31- generate list of possible words from given matrix

https://www.techiedelight.com/generate-list-of-possible-words-from-a-character-matrix/

32- All combinaation of elements satihfying given constraints

https://www.techiedelight.com/find-combinations-of-elements-satisfies-given-constraints/

33- find all binary string from a given wildcard pattern

https://www.techiedelight.com/find-binary-strings-can-formed-given-wildcard-pattern/

34- find all possibe permutaton of given string

https://www.techiedelight.com/find-permutations-given-string/