Friday, July 26, 2019

what is backtracking and n- queen problem

What is backtracking?

Backtracking is a general algorithm for discovering all answers for some computational issue, quite a requirement fulfillment the issue, that steadily assembles contender to the arrangement and forsakes an up-and-comer when it verifies that the applicant can't in any way, shape or form be finished to a substantial arrangement.

n-Queens problem-

1. N queen problem is based on chess games. Take a chessboard and imagine a n x n chessboard. The problem is to place on this board all the n queens.
2. The problem is based on arranging the queens on a chessboard in such a way that two queens can attack each other.
3. The n-Queen problem states as consider a n x n chessboard on which we have to place n queens so that no two queens attack each other by being a similar line or in a similar segment or on a similar corner to corner.
4. The 2 queens problem is not solvable because 2 queens can be placed on 2x2 chessboard but 4 queens problem is solvable. That no two queens can attack each other.

The sum of a subset-

The sum of the subset problem is to find a subset of the element 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 expected that the information set is one of a kind.
Now we are given a set of n positive numbers wi, 1<=i<=n, and a positive number m. The sum of subsets problem is to find all possible subsets of the
given set of wi's, whose sum is m. For example, if n=4,(w1, w2, w3, w4)=(12, 14, 26, 8), and m=34, then the required subsets are {12, 14, 8} and {26, 8}.

Graph coloring problem

This is a classical combinatorial problem. A graph G with n nodes and a positive integer m are given. The graph coloring problem is using m colors only, to color all the nodes of G in such a way that no two
adjacent nodes have the same color. This problem is called the-coloring decision problem. The integer m is called the chromatic number of the graph.

No comments:

Post a Comment