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 example, following is a solution for 4 Queen problem.
-
Start in the leftmost column
-
If all queens are placed return true
-
Try all rows in the current column. Do following for every tried row. a) If the queen can be placed safely in this row then mark this [row, column] as part of the solution and recursively check if placing
queen here leads to a solution. b) If placing queen in [row, column] leads to a solution then return true. c) If placing queen doesn't lead to a solution then unmark this [row, column] (Backtrack) and go to step (a) to try other rows. -
If all rows have been tried and nothing worked, return false to trigger backtracking.
My OUTPUT
- This code is exponential in nature, and it's time complexity will turn out to be O(n!).
- The maximum number of recursive calls can be equal to the number of rows. Hence the recursion stack call will take atmax O(n) space.
- However, we are not using any extra data structure, hence the solution is said to have O(1) auxiliary space.
A Hamiltonian cycle also called a Hamiltonian circuit, is a graph cycle (i.e., closed-loop) through a graph that visits each node exactly once.
- Using the backtracking method, we can easily find all the Hamiltonian Cycles present in the given graph.
- The idea is to use the Depth-First Search algorithm to traverse the graph until all the vertices have been visited.
- We traverse the graph starting from a vertex (arbitrary vertex chosen as starting vertex) and
- At any point during the traversal we get stuck (i.e., all the neighbor vertices have been visited), we backtrack to find other paths (i.e., to visit another unvisited vertex).
- If we successfully reach back to the starting vertex after visiting all the nodes, it means the graph has a Hamiltonian cycle otherwise not.
- We mark each vertex as visited so that we don’t traverse them more than once.
My OUTPUT
- Time complexity is O(2nn2).
- The space complexity it takes O(n) space.
-
Given a number n which represents the size of a chess board, and a row and a column, as a starting point for a knight piece, you are required to generate the all moves of a knight starting in (row, col) such that knight visits all cells of the board exactly once.
-
A knight should move according to the rules in chess. Please explore the next moves in the clockwise direction to get the same result as ours.
-
One of the possible valid configuration for N = 8 is shown below:
- If invalid move (row < 0, row >= n, col < 0, col >= n or chess[row][col] > 0), then return without printing.
- If the base case is hit (got till the last move = n2), then fill the cell with move no, print the configuration, mark the cell empty back - again (=0), and backtrack/return.
- Before Recurring, mark the cell with the current move number.
- Recur for all possible 8 moves with modified values of row and col, and a unit increment of the move number.
- After returning from all 8 calls, mark the cell as empty again (=0) and return.
- For each cell, we have 8 decisions to choose from for each of the n2 cell, the time complexity will be O(8(n^2)).
- The maximum number of recursive calls/depth of the recursion tree can be equal to the number of cells. Hence the recursion stack call will take atmax O(n2) space.
- However, we are not using any extra data structure, hence the solution is said to have O(1) auxiliary space.
- We learned how to use backtracking in this problem.
- Less Memory consuming.
- Backtracking is not the best solution for the Knight’s tour problem.
- Time Consuming.
- Given an array of n numbers and a number "tar" as the input.
- Calculate and print all subsets of the given elements, the contents of which sum to "tar".
- Say, if given an array 10,20,30,40,50 and the target is 60. Then all the valid subsets are [10,20,30],[10,50] and [20,40].
- Pass the arguments as parameters to the given function "PrintTarget SumSubsets" : given input array, the index we are at i.e. 0 , initial empty subset, sum of that subset and the target .
- BASE CASE: check whether the index is equal to array of length because it would tell whether all the elements have been used up or not.
- Check condition for arr.ize() and not arr.size()-1 even though the indices start with 0 because when the recursive function is called on the last element it increases the index by 1 for the index arr.length-1 and hence the value stored in "idx" is equal to the arr.size().
- Call a recursive function for the YES part of the element. Here, that element gets added to the subset string and arithmetically added.
- Call a recursive function for the NO part of that element. Here, that element does not get added to either the subset string.
- O(2n)
- This time complexity is exponential because for each state, 2 recursion calls are made.
-O(1)
-As no extra space is required, therefore space complexity is constant. However, if we include the space used in the recursive stack then the space complexity is O(n).
- We learned how to use backtracking in this problem.
- Less Memory consuming.
- Backtracking is not the best solution for Subset Sum Problem.
- Time Consuming.