Rat in the maze

Given a NxN matrix with 0s and 1s. A block with value 0 is a dead end, we cannot use this block to move ahead. While a block with value 1 can be used to travel ahead in the matrix. Now, consider mat[0][0] as the starting point for the rat. We […]

Multiset Partitioning Problem

In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that number of elements in the original set always equals to the sum of number of elements in each partition. Equivalently, a family of sets P is a partition of X if and only if […]

N Queen Problem Analysis

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For a larger N, this problem couldn’t be solved in polynomial time. So, it is an NP-Complete problem. However, this problem could be solved by backtracking in non-polynomial time for a […]

Backtracking

Backtracking is a general algorithm for finding solutions to some computational problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.