Backtracking Algorithms : Explaining Cindy's Puzzle with a C++ Program

Classic text books in Algorithm Analysis like Cormen, Leiserson and Rivest, Sedgewick and Flajolet, etc. often neglect or give least preference to the algorithm development technique called backtracking. Even those textbooks discussing backtracking only discuss few selected problems. A classic problem discussed along with backtracking is the eight queens puzzle. Often this problem is unappreciated by persons not well versed in the game of Chess. Here I am trying to explain backtracking using a very simple game often called ‘Cindy’s puzzle’.

The game Cindy’s puzzle involves n Red marbles, n Green marbles and a playing board which consists simply of a line of 2n+1 spaces to put the marbles in. Start with the Red marbles all at one end (say, the left), the Green marbles all at the other end, and a free space in between. For n=2, the initial arrangement on the board is shown below.

To denote this position we use the notation |R|R| _ |G|G| is used.

The aim of the puzzle is to reverse the positions of the marbles as shown below.

So the solution for the puzzle can be denoted as |G|G| _ |R|R|.

The movements of the marbles are restricted by the following rules.

The Red marbles can only move to the right, and the Green marbles can only move to the left (no backing up). At each move, a marble can either

• Move one space ahead, if that space is clear, or
• Jump ahead over exactly one marble of the opposite color, if the space just beyond that marble is clear.

I am trying to develop a backtracking algorithm to solve this puzzle. The algorithm will be able to produce one particular solution to this puzzle. For example for n=2, the solution steps are given below.

           |R|R| _ |G|G|

        |R|R|G| _ |G|

        |R| _ |G|R|G|

        | _ |R|G|R|G|

        |G|R| _ |R|G|

        |G|R|G|R| _ |

        |G|R|G| _ |R|

        |G| _ |G|R|R|

        |G|G| _ |R|R|

Of course this is an ideal solution where no backtracking is used but in the proposed backtracking algorithm, if non winnable situation arises backtracking is applied to go back to a previous state and continue the search for a solution. 

 Click here to download the C++ Program.

Operator Overloading in C++ : PART 2 ([ ] Operator)

  Array subscript operator [ ] used for array indexing can also be overloaded in C++. In this post I have added a program in which the array subscript operator [ ] is overloaded. The program illustrates an overloaded array subscript operator.

The program also offers a solution to the C++ puzzle question given below.

Floating Point Number in Array Subscript

Write a C++ program in which the following statement compiles without an error.

cout << a[0.123];

The difficulty in solving this puzzle arises from the fact that array subscript should be an integer.  

If you pass a float value to a normal array subscript you will get the following error "Invalid type for array subscript". 

One possible solution is to overload the array subscript operator.

Click here to download the C++ program solving the puzzle.

There might be some other solutions to this puzzle. If you know any other solution please share them here. 

   

Operator Overloading in C++ : PART 1 (++ Operator)

 I am now teaching under graduate students C++ programming. I thought I will share the programs I have prepared so that it benefits everyone.

Overloading ++ Operator

In this post I have added sample programs overloading the ++ Operator. In C++ we have preincrement and postincrement operators. For example ++a is preincrement whereas a++ is postincrement. So in order to handle these two situations there should be two versions of the operator++( ) function. The two versions are shown below. 

    void operator++(int y);  // for postincrement

   // The call a++; will invoke this version

   // The call a++; is same as the call a.operator++();
   

   void operator++( );        // for preincrement

   // The call ++a; will invoke this version

   // The call ++a; is same as the call a.operator++(0);

Click here to download the C++ program. 

Overloading ++ Operator with Friend Function

In C++ we can overload the ++ operator by using friend function.  Here also we need two versions to manage the preincrement and postincrement versions of the ++ operator. The two versions are given below.

   void operator++(A, int);  // for postincrement

   // The name of the Class is A

   // The call a++; will invoke this version

   // The call a++; is same as the call operator++(a);
   

   void operator++(A);        // for preincrement
   //The name of the class is A 

   // The call ++a; will invoke this version

   // The call ++a; is same as the call operator++(a,0);

Click here to download the C++ program. 

In C and C++ typedef is a Storage Class Specifier

  Consider the program given below.

#include<stdio.h>
int main()
{
   typedef static int i;
   i a = 0;
   printf("%d", a);
   return 0;
}

The program when compiled as C or C++ will give you the following error "multiple storage classes in declaration specifiers". The error tells us that typedef in C and C++ is treated as a storage class specifier and this leads to the error since it is not allowed to use two storage class specifiers with a variable.

The C Reference Manual says "The typedef specifier does not reserve storage and is called a storage class specifier only for syntactic convenience".

Yet Another Difference Between C and C++: Initializing Constant Variables

  Constant variable initialization is yet another minute difference between C and C++. Consider the program given below.

#include<stdio.h>
int main()
{
  int x = 111;
  static int y = x;
  if(x == y)
     printf("Equal");
  else
     printf("Not Equal");
  return 0;
}

If you save the program as a C++ program, it compiles fine and shows the output as "Equal". But the same program when compiled as C will give you the following error "initializer element is not constant|". What is the reason? This is another minor difference between C and C++. In C a constant variable can only be initialized with a constant value and not by using another variable. But C++ do not have this restriction. You can initialize a constant variable with any other variable.

Click here to download the C++ program.

Yet Another Difference Between C and C++: Case Labels

 There are many major differences between C and C++. Such differences are matters for Text Books and Manuals. Here I am pointing out yet another minor difference between C and C++. This time the difference arises from the way case labels are treated in C and C++. 

 C++ will allow const int variables as case labels, whereas C will give you an error. Consider the program given below.

#include<stdio.h>

int main()
{
    int i=1;
    const int j=1;
    switch(i)
    {
        case j:
            printf("\nHello\n\n");
            break;
        case 2:
            printf("\nHi\n\n");
            break;
        default:
            printf("\nWelcome\n\n");
    }
    return 0;
}

The program will give the error 'case label does not reduce to an integer constant' when compiled as a C program. But when compiled as a C++ program the program executes without any errors and gives 'Hello' as output. 

C/C++ Puzzles: PART - 36

  The following program will give you syntax error.


#include<stdio.h>

int main()
{
    int a=10,b=5,c;
    c=a>b?a:;
    printf("\n%d\n\n",c);
    return 0;
}

Whereas the program given below will work without any syntax errors. Predict the output of the program.


#include<stdio.h>

int main()
{
    int a=10,b=5,c;
    c=a>b?:b;
    printf("\n%d\n\n",c);
    return 0;
}

C/C++ Puzzles: PART - 35

   C Program Tricked to Believe X equals X+2

  The puzzle has been discussed previously, but only one solution was provided. But now I have added a few more solutions to this puzzle. The challenge is to get a true value for the following conditional statement. 

x==x+2  

You are free to use any feature of the C preprocessor or Compiler. If you can't get a solution then check the programs shown below.

Solution 1

#define x 2|0
#include<stdio.h>

int main()
{
    if(x == x+2)
    {
        printf("\n Hello");
    }
    else
    {
        printf("\n Hi");
    }
}

Solution 2

#include<stdio.h>

int main()

{

    float x=1.0/0;

    if(x==x+2)

    {

        printf("\nHello");

    }

    else

    {

        printf("\nHi");

    }

}

Solution 3

#include<stdio.h>

int main()

{

    float x = 1e100;

    if(x==x+2)

    {

        printf("\nHello");

    }

    else

    {

        printf("\nHi");

    }

}

Solution 4

#include<stdio.h>

struct {}*x=0;

int main()

{

    if(x==x+2)

    {

        printf("\nHello");

    }

    else

    {

        printf("\nHi");

    }

}

Solution 5

#include<stdio.h>

int (*x)[0x20000000];

int main()

{

    if(x==x+2)

    {

        printf("\nHello");

    }

    else

    {

        printf("\nHi");

    }

}

Solution 6

#include<stdio.h>

int main()

{

/////////////////////////////////////

// we initialize tr = 1            //

int tr = 1;

int x = 111;

////////////////////////////////////

// Can You change the value of tr??/

tr = (x == x + 2);

/////////////////////////////////////

// The value of tr is not changed  //

    if(tr==1)

    {

        printf("\nHello");

    }

    else

    {

        printf("\nHi");

    }

}

Click here to download the C program solutions. 

Click here to download the C++ program solutions.

Power Method to Find the Largest Eigenvalue

   Power method is used to find the numerically largest eigenvalue. The method sometimes converge very slowly. In this post I am providing the C and C++ programs to implement power method.

Figure Below Shows a Sample Output

Click here to download the C program.

Click here to download the C++ program. 

Fitting a Parabola Using Method of Moments : C/C++ Program

   In this post I have shared the C and C++ programs to fit a Parabola using the method of moments.

Figure Below Shows a Sample Output

Click here to download the C Program.

Click here to download the C++ Program.

Straight Line Fitting By Using the Method of Least Squares : C/C++ Program

   In this post I have shared the C and C++ Programs to perform straight line fitting by using the method of least squares. 

Figure Below Shows a Sample Output

Click here to download the C Program.

Click here to download the C++ Program.

Straight Line Fitting Using the Method of Group Averages : C/C++ Program

   In this post I have shared the C and C++ programs to perform straight line fitting by using the method of Group Averages.

Figure Below Shows a Sample Output

Click here to download the C Program.

Click here to download the C++ Program.

Gauss Seidel Method: C/C++ Program

   With this post I have provided the C and C++ programs implementing the Gauss Seidel Method.

Figure Below Shows a Sample Output

Click here to download the C Program.

Click here to download the C++ Program.

Gauss Jacobi Method: C/C++ Program

   With this post I have provided the C and C++ programs implementing the Gauss Jacobi Method.

Figure Below Shows a Sample Output

Click here to download the C Program.

 

Click here to download the C++ Program.  

C/C++ Puzzles: PART - 34

  Consider the two C code fragments given below.

Code 1:

int i;
i=0;
while(i < 10)
{
     // Single Line of Code Here
     printf("\n%d",i);
     i++;
}

Code 2:

int i;
for(i=0; i < 10; i++)
{
     // Single Line of Code Here
     printf("\n%d",i);
}

The Output will be same for both the codes. The Output is shown below.

The Challenge is to obtain different outputs for the two codes by adding the same single line of code in place of the comment. You should not make any changes in the code other than replacing the comment with the same single line of code. There might be different ways to solve the puzzle.

C/C++ Program to Print Pascal's Triangle

  Pascal's Triangle is a triangular array of the binomial coefficients. The C/C++ program given in this post prints the Pascal's Triangle.

Figure Below Shows the Output
 

Click here to download the C Program. 

Click here to download the C++ Program.

Overloading Increment/Decrement Operators Using Friend Functions

  Friend functions can be used to overload Prefix and Postfix forms of Increment/Decremnt operators in C++. Sample output and code are shown below. 

Figure Below Shows a Sample Output

#include<iostream>

using namespace std;

class over_load
{
    int n1,n2;
    public:
    void set(int x, int y)
    {
        n1=x;
        n2=y;
    }
    void show()
    {
        cout<<"\nNumber 1 is "<<n1<<"\n";
        cout<<"\nNumber 2 is "<<n2<<"\n";
    }
    friend over_load operator++(over_load &ob)
    {
        ob.n1++;
        ob.n2++;
        cout<<"\nPost Incremnt Operator Overloaded\n";
    }
    friend over_load operator++(over_load &ob, int x)
    {
        ++ob.n1;
        ++ob.n2;
        cout<<"\nPre Increment Operator Overloaded\n";
    }
};

int main()
{
  over_load ob1;
  ob1.set(100,200);
  cout<<"\nObejct ob1 Initially:\n";
  ob1.show();
  ob1++;
  ob1.show();
  ++ob1;
  ob1.show();
  return 0;
}

Click here to download the C++ Program.

Overloading Prefix and Postfix Increment/Decrement Operators in C++

  In C++ operators can be overloaded. Problems can arise when we have to overload Increment/Decrement Operators of C++. We need to distinguish between Prefix and Postfix forms of Increment/Decrement Operators. The program given below shows the prototype for Prefix and Postfix forms of Increment/Decrement Operators.

#include<iostream>

using namespace std;

class over_load
{
    int n1,n2;
    public:
    void set(int x, int y)
    {
        n1=x;
        n2=y;
    }
    void show()
    {
        cout<<"\nNumber 1 is "<<n1<<"\n";
        cout<<"\nNumber 2 is "<<n2<<"\n";
    }
    over_load operator++()
    {
        n1++;
        n2++;
        cout<<"\nPost Incremnt Operator Overloaded\n";
        return *this;
    }
    over_load operator++(int x)
    {
        ++n1;
        ++n2;
        cout<<"\nPre Increment Operator Overloaded\n";
        return *this;
    }
};

int main()
{
  over_load ob1;
  ob1.set(100,200);
  cout<<"\nObejct ob1 Initially:\n";
  ob1.show();
  ob1++;
  ob1.show();
  ++ob1;
  ob1.show();
  return 0;
}

Figure Below Shows a Sample Output

Click here to download the C++ Program.  

C/C++ Program to Print Triangular, Pentagonal, and Heptagonal Numbers

  The C/C++ Program provided with this post prints the Triangular, Pentagonal, and Heptagonal Numbers.

• To learn about Triangular Numbers check this Wikipedia Article. 
• To learn about Pentagonal Numbers check this Wikipedia Article. 
• To learn about Heptagonal Numbers check this Wikipedia Article.    

Figure Below Shows a Sample Output

Click here to download the C Program. 

Click here to download the C++ Program. 

C/C++ Puzzles: PART - 33

C Program Showing Errors When Compiled as C++ Program 

  Write a C Program without any errors, but the same when compiled as a C++ Program should show errors? This was a question I had to answer recently. There are many different answers I suppose. The program given below is the one which comes to my mind first. 

#include<stdio.h>

void func();

int main()
{
  int x;
  x=333;
  func(x);
  return 0;
}

void func(int x)
{
    printf("\nValue is %d\n",x);
}

The program gives an error when compiled as a C++ program because in C a function with an empty parameter list can have any number of parameters including zero parameters where as in C++ it means the function can't receive any parameter.

Click here to download the C Program.