DEV Community: Nikhilesh2601

Backtracking in JAVA

Nikhilesh2601 — Thu, 25 Nov 2021 13:37:36 +0000

Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time (by time, here, is referred to the time elapsed till reaching any level of the search tree)

There are three types of problems in backtracking –

1)Decision Problem – In this, we search for a feasible solution.
2)Optimization Problem – In this, we search for the best solution.
3)Enumeration Problem – In this, we find all feasible solutions.
4)How to determine if a problem can be solved using Backtracking?

Generally, every constraint satisfaction problem which has clear and well-defined constraints on any objective solution, that incrementally builds candidate to the solution and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution, can be solved by Backtracking. However, most of the problems that are discussed, can be solved using other known algorithms like Dynamic Programming or Greedy Algorithms in logarithmic, linear, linear-logarithmic time complexity in order of input size, and therefore, outshine the backtracking algorithm in every respect (since backtracking algorithms are generally exponential in both time and space). However, a few problems still remain, that only have backtracking algorithms to solve them until now.

Consider a situation that you have three boxes in front of you and only one of them has a gold coin in it but you do not know which one. So, in order to get the coin, you will have to open all of the boxes one by one. You will first check the first box, if it does not contain the coin, you will have to close it and check the second box and so on until you find the coin. This is what backtracking is, that is solving all sub-problems one by one in order to reach the best possible solution.

Consider the below example to understand the Backtracking approach more formally,

Given an instance of any computational problem P and data D corresponding to the instance, all the constraints that need to be satisfied in order to solve the problem are represented by C . A backtracking algorithm will then work as follows:

The Algorithm begins to build up a solution, starting with an empty solution set S . S = {}

Add to S the first move that is still left (All possible moves are added to S one by one). This now creates a new sub-tree s in the search tree of the algorithm.
Check if S+s satisfies each of the constraints in C .
If Yes, then the sub-tree s is “eligible” to add more “children”.
Else, the entire sub-tree s is useless, so recurs back to step 1 using argument S .
In the event of “eligibility” of the newly formed sub-tree s , recurs back to step 1, using argument S+s .
If the check for S+s returns that it is a solution for the entire data D . Output and terminate the program.
If not, then return that no solution is possible with the current s and hence discard it.

Difference between Recursion and Backtracking:
In recursion, the function calls itself until it reaches a base case. In backtracking, we use recursion to explore all the possibilities until we get the best result for the problem.

Pseudo Code for Backtracking :

Recursive backtracking solution.

void findSolutions(n, other params) :
if (found a solution) :
solutionsFound = solutionsFound + 1;
displaySolution();
if (solutionsFound >= solutionTarget) :
System.exit(0);
return

for (val = first to last) :
    if (isValid(val, n)) :
        applyValue(val, n);
        findSolutions(n+1, other params);
        removeValue(val, n);

Finding whether a solution exists or not

boolean findSolutions(n, other params) :
if (found a solution) :
displaySolution();
return true;

for (val = first to last) :
    if (isValid(val, n)) :
        applyValue(val, n);
        if (findSolutions(n+1, other params))
            return true;
        removeValue(val, n);
    return false;

Let us try to solve a standard Backtracking problem, 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. For example, following is a solution for 4 Queen problem.

The expected output is a binary matrix which has 1s for the blocks where queens are placed. For example, following is the output matrix for the above 4 queen solution.

{ 0, 1, 0, 0}
{ 0, 0, 0, 1}
{ 1, 0, 0, 0}
{ 0, 0, 1, 0}

Backtracking Algorithm: The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes then we backtrack and return false.

1) Start in the leftmost column
2) If all queens are placed
return true
3) 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 the 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 and go to step (a) to try other rows.
4) If all rows have been tried and nothing worked, return false to trigger
backtracking.

**Examples for backtracking:

Program-1:

import java.util.Scanner;
public class pro1 {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the values of m and n:");
int m = scanner.nextInt();
int n = scanner.nextInt();
int result = grid(1,1, m, n);
System.out.println("Result: "+ result);
}
public static int grid(int x, int y, int m, int n){
if(x == m && y == n){
return 1;
}
else if(x <= m && y <= n){
return grid(x+1, y, m, n) + grid(x, y+1, m, n);
}
else{
return 0;
}
}
}

Program-2:

import java.util.Scanner;
import java.lang.Math;
public class pro2 {
private static double MAX = Math.pow(10, 9) + 7;
public static int countOrders(int n) {
int sumTillNow = 1;
double productTillNow = 1;
for (int i = 2; i <= n; i++) {
for (int j = 2*i - 2; j <= 2*i - 1; j++) {
sumTillNow += j;
}
productTillNow *= sumTillNow;
productTillNow = productTillNow % MAX;
}
return (int)productTillNow;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the values of n:");
int n = scanner.nextInt();
System.out.println("Result : "+ countOrders(n));
}
}

Program-3:

import java.util.Scanner;
public class pro3 {
private static int mod = 1000000007;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Enter n and k:");
int n = scanner.nextInt();
int k = scanner.nextInt();
System.out.println("Result: " + rearrangeSticks(n, k));
}
public static int rearrangeSticks(int n, int k) {
int[][] dp=new int[n+1][k+1];
return helper(n,k,dp);
}
public static int helper(int n, int k, int[][] dp){
int result=0;
if(n==k){
return 1;
}
if(k==0){
return 0;
}
if(dp[n][k]==0){
dp[n][k]=(int)((1L * helper(n - 1, k - 1,dp) + 1L * helper(n - 1, k,dp) * (n - 1)) % mod);
}
return dp[n][k];
}
}

Note:
For more examples, just visit leetcode and practice..!

Structures and Unions in C

Nikhilesh2601 — Sun, 09 May 2021 13:48:38 +0000

Structures in c:

Arrays allow to define type of variables that can hold several data items of the same kind. Similarly structure is another user defined data type available in C that allows to combine data items of different kinds.

Structures are used to represent a record. Suppose you want to keep track of your books in a library. You might want to track the following attributes about each book

Title
Author
Subject
Book ID
Defining a Structure
To define a structure, you must use the struct statement. The struct statement defines a new data type, with more than one member. The format of the struct statement is as follows

struct [structure tag] {

member definition;
member definition;
...
member definition;
} [one or more structure variables];

The structure tag is optional and each member definition is a normal variable definition, such as int i; or float f; or any other valid variable definition. At the end of the structure's definition, before the final semicolon, you can specify one or more structure variables but it is optional. Here is the way you would declare the Book structure −

struct Books {
char title[50];
char author[50];
char subject[100];
int book_id;
} book;

Accessing Structure Members:
To access any member of a structure, we use the member access operator (.). The member access operator is coded as a period between the structure variable name and the structure member that we wish to access. You would use the keyword struct to define variables of structure type. The following example shows how to use a structure in a program

include

struct Books {
char title[50];
char author[50];
char subject[100];
int book_id;
};

int main( ) {

struct Books Book1; /* Declare Book1 of type Book /
struct Books Book2; / Declare Book2 of type Book */

/* book 1 specification */
strcpy( Book1.title, "C Programming");
strcpy( Book1.author, "Nuha Ali");
strcpy( Book1.subject, "C Programming Tutorial");
Book1.book_id = 6495407;

/* book 2 specification */
strcpy( Book2.title, "Telecom Billing");
strcpy( Book2.author, "Zara Ali");
strcpy( Book2.subject, "Telecom Billing Tutorial");
Book2.book_id = 6495700;

/* print Book1 info */
printf( "Book 1 title : %s\n", Book1.title);
printf( "Book 1 author : %s\n", Book1.author);
printf( "Book 1 subject : %s\n", Book1.subject);
printf( "Book 1 book_id : %d\n", Book1.book_id);

/* print Book2 info */
printf( "Book 2 title : %s\n", Book2.title);
printf( "Book 2 author : %s\n", Book2.author);
printf( "Book 2 subject : %s\n", Book2.subject);
printf( "Book 2 book_id : %d\n", Book2.book_id);

return 0;
}

When the above code is compiled and executed, it produces the following result

Book 1 title : C Programming
Book 1 author : Nuha Ali
Book 1 subject : C Programming Tutorial
Book 1 book_id : 6495407
Book 2 title : Telecom Billing
Book 2 author : Zara Ali
Book 2 subject : Telecom Billing Tutorial
Book 2 book_id : 6495700
Structures as Function Arguments
You can pass a structure as a function argument in the same way as you pass any other variable or pointer.

include

struct Books {
char title[50];
char author[50];
char subject[100];
int book_id;
};

/* function declaration */
void printBook( struct Books book );

int main( ) {

struct Books Book1; /* Declare Book1 of type Book /
struct Books Book2; / Declare Book2 of type Book */

/* book 1 specification */
strcpy( Book1.title, "C Programming");
strcpy( Book1.author, "Nuha Ali");
strcpy( Book1.subject, "C Programming Tutorial");
Book1.book_id = 6495407;

/* book 2 specification */
strcpy( Book2.title, "Telecom Billing");
strcpy( Book2.author, "Zara Ali");
strcpy( Book2.subject, "Telecom Billing Tutorial");
Book2.book_id = 6495700;

/* print Book1 info */
printBook( Book1 );

/* Print Book2 info */
printBook( Book2 );

return 0;
}

void printBook( struct Books book ) {

printf( "Book title : %s\n", book.title);
printf( "Book author : %s\n", book.author);
printf( "Book subject : %s\n", book.subject);
printf( "Book book_id : %d\n", book.book_id);
}

When the above code is compiled and executed, it produces the following result

Book title : C Programming
Book author : Nuha Ali
Book subject : C Programming Tutorial
Book book_id : 6495407
Book title : Telecom Billing
Book author : Zara Ali
Book subject : Telecom Billing Tutorial
Book book_id : 6495700
Pointers to Structures
You can define pointers to structures in the same way as you define pointer to any other variable −

struct Books *struct_pointer;
Now, you can store the address of a structure variable in the above defined pointer variable. To find the address of a structure variable, place the '&'; operator before the structure's name as follows −

struct_pointer = &Book1;
To access the members of a structure using a pointer to that structure, you must use the → operator as follows −

struct_pointer->title;
Let us re-write the above example using structure pointer.

include

struct Books {
char title[50];
char author[50];
char subject[100];
int book_id;
};

/* function declaration */
void printBook( struct Books *book );
int main( ) {

struct Books Book1; /* Declare Book1 of type Book /
struct Books Book2; / Declare Book2 of type Book */

/* book 1 specification */
strcpy( Book1.title, "C Programming");
strcpy( Book1.author, "Nuha Ali");
strcpy( Book1.subject, "C Programming Tutorial");
Book1.book_id = 6495407;

/* book 2 specification */
strcpy( Book2.title, "Telecom Billing");
strcpy( Book2.author, "Zara Ali");
strcpy( Book2.subject, "Telecom Billing Tutorial");
Book2.book_id = 6495700;

/* print Book1 info by passing address of Book1 */
printBook( &Book1 );

/* print Book2 info by passing address of Book2 */
printBook( &Book2 );

return 0;
}

void printBook( struct Books *book ) {

printf( "Book title : %s\n", book->title);
printf( "Book author : %s\n", book->author);
printf( "Book subject : %s\n", book->subject);
printf( "Book book_id : %d\n", book->book_id);
}

When the above code is compiled and executed, it produces the following result

Unions in c:

A union is a special data type available in C that allows to store different data types in the same memory location. You can define a union with many members, but only one member can contain a value at any given time. Unions provide an efficient way of using the same memory location for multiple-purpose.

Defining a Union:
To define a union, you must use the union statement in the same way as you did while defining a structure. The union statement defines a new data type with more than one member for your program. The format of the union statement is as follows

union [union tag] {
member definition;
member definition;
...
member definition;
} [one or more union variables];

The union tag is optional and each member definition is a normal variable definition, such as int i; or float f; or any other valid variable definition. At the end of the union's definition, before the final semicolon, you can specify one or more union variables but it is optional. Here is the way you would define a union type named Data having three members i, f, and str −

union Data {
int i;
float f;
char str[20];
} data;

Now, a variable of Data type can store an integer, a floating-point number, or a string of characters. It means a single variable, i.e., same memory location, can be used to store multiple types of data. You can use any built-in or user defined data types inside a union based on your requirement.

The memory occupied by a union will be large enough to hold the largest member of the union. For example, in the above example, Data type will occupy 20 bytes of memory space because this is the maximum space which can be occupied by a character string. The following example displays the total memory size occupied by the above union

include

union Data {
int i;
float f;
char str[20];
};

int main( ) {

union Data data;

printf( "Memory size occupied by data : %d\n", sizeof(data));

return 0;
}

When the above code is compiled and executed, it produces the following result −

Memory size occupied by data : 20
Accessing Union Members
To access any member of a union, we use the member access operator (.). The member access operator is coded as a period between the union variable name and the union member that we wish to access. You would use the keyword union to define variables of union type. The following example shows how to use unions in a program

include

union Data {
int i;
float f;
char str[20];
};

int main( ) {

union Data data;

data.i = 10;
data.f = 220.5;
strcpy( data.str, "C Programming");

printf( "data.i : %d\n", data.i);
printf( "data.f : %f\n", data.f);
printf( "data.str : %s\n", data.str);

return 0;
}

When the above code is compiled and executed, it produces the following result

data.i : 1917853763
data.f : 4122360580327794860452759994368.000000
data.str : C Programming
Here, we can see that the values of i and f members of union got corrupted because the final value assigned to the variable has occupied the memory location and this is the reason that the value of str member is getting printed very well.

Now let's look into the same example once again where we will use one variable at a time which is the main purpose of having unions

include

union Data {
int i;
float f;
char str[20];
};

int main( ) {

union Data data;

data.i = 10;
printf( "data.i : %d\n", data.i);

data.f = 220.5;
printf( "data.f : %f\n", data.f);

strcpy( data.str, "C Programming");
printf( "data.str : %s\n", data.str);

return 0;
}
When the above code is compiled and executed, it produces the following result −

data.i : 10
data.f : 220.500000
data.str : C Programming