Box Stacking Problem

Problem:- You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.
Link to read


public class BoxStack {

    public static void main (String[] args) {
        //code
       //Let's suppose the example
        int [][] matrix={ {1,2,4},
                          {3,2,5}
                        };


        BoxStack  g=new BoxStack ();            
       
       //Generate all surfaces of the cuboid.
        int [][] finalMatrix=g.generateAllSurfaces( matrix);
     
        //Sort the cuboid based on surfaces, assumed the first two data is Width and depth, and third one
        //is height.

        g.sortMatrix(finalMatrix);
     
       //Now use augmented LIS to find the max sub sequence    
        g.findTheStackBox(finalMatrix);
 
    }
 
 
    public void findTheStackBox(int [][] matrix){
        int [] max = new int[matrix.length];   // to hold the max subsequences
        int [] result = new int[matrix.length]; //to hold the sequence
     
        for(int i=0;i<matrix.length;i++){
            max[i]=matrix[i][2];
            result[i]=i;
        }
 
        // writing LIS  
        for(int i=1,length=matrix.length;i<length;i++){
         
        for(int j=0;j<i;j++){
                //check for the surface validity
                if(matrix[i][0]< matrix[j][0] && matrix[i][1]< matrix[j][1]  ){
                max[i]=matrix[i][2]+max[j];
                    result[i]=j;
                }
            }
        }
   
        int index=0;
        int maxData=0;
        for(int i=0;i<max.length;i++){
            if(max[i]>maxData){
                maxData=max[i];
                index=i;
            }
         
         
        }
     
        System.out.println("Maximum Height of the stack is = "+maxData);
     
        //Now print the stack of the considered height top to bottom
     
        while(index!=result[index]){
         
            System.out.println(matrix[index][0]+" "+matrix[index][1]+" "+matrix[index][2]);
         
            index=result[index];
         
        }
        System.out.println(matrix[index][0]+" "+matrix[index][1]+" "+matrix[index][2]);
     
    }
 
    public void sortMatrix(int [][] matrix){
        for(int i=1,length=matrix.length;i<length;i++){
            int a=matrix[i][0];
            int b=matrix[i][1];
            int c=matrix[i][2];
            int pivot=a*b;
            int j=i-1;
 
            while(j>=0 && (matrix[j][0]*matrix[j][1])<=pivot){
                matrix[j+1][0]=matrix[j][0];
                matrix[j+1][1]=matrix[j][1];
                matrix[j+1][2]=matrix[j][2];
                j--;
            }
            matrix[j+1][0]=a;
            matrix[j+1][1]=b;
            matrix[j+1][2]=c;
        }
    }
 
 
    public int [][] generateAllSurfaces(int [][] matrix){
        int [][] temp = new int [3*matrix.length][3];
        int m=0;
     
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<3;j++){
                int a=matrix[i][j];
                int b=matrix[i][(j+1)%3];
                int c=matrix[i][(j+2)%3];
             
                if(b>c){
                    temp[m][0]=b;
                    temp[m][1]=c;
                }else{
                    temp[m][0]=c;
                    temp[m][1]=b;
                }
                temp[m][2]=a;
                m++;
            }
        }
     
     return temp;
    }
}

page contents

Soduku Solver An easy approach.

I can bet a coffee, you must have played this game for more about this game See here...
         How can we solve this puzzle through programming that's also seems a good task to do.This questions generally used to ask in interviews.This problem deal with the bactracking.

 

Approach:-An Empty position can be checked against a value (1 to 9) - Row-wise, Column-wise or In a small (3 by 3) matrix. if it satisfies go ahead and see the next position if not so, go back and change the previous value..... do this back and forth until all the cell gets filled.

see my code :- Easy to read
Important Note:- Things to check out before placing any value on empty(zeroth valued) position
1) Check the whole Row( of length 9) whether any similar value already exists or not if not go ahead and check other conditions.
2)Check the whole Column(of length 9) whether any similar value already exists or not if not go ahead and check next conditions.
3)Only Row and Column wise lookup against value is not enough, There are 9 small matrices of size 3 by 3 (which is named as sMatrixChecker in code), we have to check whether a similar value exists in small matrix against the value to be placed related to position of the value to be placed.
 Example:- See the middle 3 by 3 matrix which has values 6,0,7,9,4,0,2,0,5 (0 for empty) to fill any 0 valued position we have to check whether that value already exists in this matrix too or not.

/*By Atiqur Rahman for atiqwhiz.blogspot.in*/

    #include <iostream>
    #define N 9
    using namespace std;
    
    class Soduku
    {
    int arr[N][N];
    
    public:
    Soduku()
    { cout<<"Enter the initial position Rowise(1 to 9) if no +ve Integer put 0 there\n";
    for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
    cin>>arr[i][j];
    }
    void putSoduku()
    {
    for(int i=0;i<N;i++)
    {
    for(int j=0;j<N;j++)
    cout<<arr[i][j]<<" ";
    cout<<endl;
    }
    
    }
    bool sMatrixChecker(int value ,int row,int column);
    
    bool rowChecker(int value,int row,int column);
    
    bool columnChecker(int value,int row,int column);
    
    bool Solver(int ,int);
    };
    
    bool Soduku::sMatrixChecker(int value,int row,int column) //To check the small matrix of 3 by 3.
    {
    for(int i=row/3*3;i<row/3*3+3;i++)
    for(int j=column/3*3;j<column/3*3+3;j++)
    {
    if(arr[i][j]==value)
    return false;
    }
    return true;
    }
    //To solve row stability against value
    bool Soduku::rowChecker(int value,int row,int column)
    {
    for(int i=0;i<9;i++)
    {
    if(arr[row][i]==value)
    return false;
    }
    
    return true;
    }
    //To solve column stability against value.
    bool Soduku::columnChecker(int value,int row,int column)
    {
    for(int i=0;i<9;i++)
    {
    if(arr[i][column]==value)
    return false;
    }
    return true;
    }
    
                            //To solove the problem
bool Soduku::Solver(int n,int m)
{ int t,p;
     if(n==N)
     return true;
  for(int i=n;i<N;i++)
  {
    
    for(int j=m;j<N;j++)
    { int value=1;
       if(!arr[i][j])
       {
          while(value<10)
            {
               if(sMatrixChecker(value,i,j)&&rowChecker(value,i,j)&&columnChecker(value,i,j))
               {
                 arr[i][j]=value;    
                     t=i;p=j;
                    if((j+1)%N==0)
                    { t++;p=(j+1)%N;}
                    if(Solver(t,p))
                     return true;
               }
               else
               {
                arr[i][j]=0;
                value++;
               }
            }
          return false;   
       }
    
    }
   m=0;   
 
  }
}
   
    int main()
    {
    Soduku s;s.putSoduku();cout<<endl<<endl;
    s.Solver(0,0);
    cout<<"Solved Soduku\n";
    s.putSoduku();
    return 0;
    }

 Input (Empty cell is equal to zero).:- 3 0 6 5 0 8 4 0 0 5 2 0 0 0 0 0 0 0 0 8 7 0 0 0 0 3 1 0 0 3 0 1 0 0 8 0 9 0 0 8 6 0 0 0 5 0 5 0 0 9 0 6 0 0 1 3 0 0 0 0 2 5 0 0 0 0 0 0 0 0 7 4 0 0 5 2 0 6 3 0 0

output:-

Solved Soduku
3 1 6 5 7 8 4 9 2 
5 2 9 1 3 4 7 6 8 
4 8 7 6 2 9 5 3 1 
2 6 3 4 1 5 9 8 7 
9 7 4 8 6 3 1 2 5 
8 5 1 7 9 2 6 4 3 
1 3 8 9 4 7 2 5 6 
6 9 2 3 5 1 8 7 4 
7 4 5 2 8 6 3 1 9 

Knight's tour on N*N Square

Knight Tour Problem:- A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed, otherwise it is open. The exact number of open tours on an 8x8 chessboard is still unknown.For more details...
                             

Great seems you understood the problem, again complex looking problem yes it is at first sight but not actually let's try to give a hit.

Naive Approach:-Let's start from any position (let's 0,0) on square..try to make any possible L(knight move), continue untill you filled all the places of square or either you don't have option to go ahead... Now this is the point to Backtrack from last positions of the knight hence doing back and forth you can achieve your destination...(yes it is time consuming).

Let's see the code here...
/*Developed By Atiqur Rahman for atiqwhiz.blogspot.in*/
#include <iostream>
#include <iomanip>
using namespace std;
#define R 8
#define C 8
class KnightTour
{
    int arr[R][C];
    int count;
    public:
     KnightTour():count(0)
     {  
         for(int n=0;n<R;n++)
          for(int m=0;m<C;m++)
          {
             arr[n][m]=0;
          }
       
     }
     bool Knight(int i,int j)
     {  
         count++;
        //cout<<"Count "<<count<<" i "<<i<<" j "<<j<<endl;
        if(count==R*C)
        {arr[i][j]=count;return true;}
       
        if(i+2<R&&j+1<C&&!arr[i+2][j+1])      //1
        {
            arr[i][j]=count;
            if(Knight(i+2,j+1))
             return true;
        }
       
        if(i+1<R&&j+2<C&&!arr[i+1][j+2])  //2
        {
            arr[i][j]=count;
           if(Knight(i+1,j+2))  
            return true;  
        }
       
        if(i-1>=0&&j+2<C&&!arr[i-1][j+2])  //3
        {
            arr[i][j]=count;
            if(Knight(i-1,j+2))
             return true;
        }
       
        if(i-2>=0&&j+1<C&&!arr[i-2][j+1])    //4
        {
            arr[i][j]=count;
            if(Knight(i-2,j+1))
             return true;
        }
         if(i-2>=0&&j-1>=0&&!arr[i-2][j-1])  //5
        {
            arr[i][j]=count;
            if(Knight(i-2,j-1))
             return true;
        }
   
         if(i-1>=0&&j-2>=0&&!arr[i-1][j-2])  //6
        {
            arr[i][j]=count;
            if(Knight(i-1,j-2))
             return true;
        }
       
         if(i+1<R&&j-2>=0&&!arr[i+1][j-2])   //7
        {
            arr[i][j]=count;
            if(Knight(i+1,j-2))
             return true;
        }
       
         if(i+2<R&&j-1>=0&&!arr[i+2][j-1])    //8
        {
            arr[i][j]=count;
            if(Knight(i+2,j-1))
             return true;
        }
         count--;
         arr[i][j]=0;
        return false;
     }
void put()
{
   
    cout<<"Resultant Matrix\n";
    for(int i=0;i<R;i++)
    {
        for(int j=0;j<C;j++)
        {
         cout<<setw(3)<<arr[i][j];  
        }
    cout<<endl;
    }

}

};

int main()
{
KnightTour k;
bool b=k.Knight(0,0);
k.put();  
if(b)
{
    cout<<"\nTour is Possible";
}
else
 cout<<"Tour is not possible";

}

//Happy coding....
//If you find any bug let us know.....Happy to help you......Must read this link for better understanding See this

The N-Queens problem, A simple approach

Welcome back Guys...Got time to write my next topic...Hope everyone is doing great!!! ;) ;)

Let's Start with the problem :-
The N-queens problem consists in placing N non-attacking queens on an N-by-N chess board. A queen can attack another queen vertically, horizontally, or diagonally. E.g. placing a queen on a central square of the board blocks the row and column where it is placed, as well as the two diagonals (rising and falling) at whose intersection the queen was placed.

"This is typically looking a very complex questions for budding coders but I bet it is not so, Let's tackle it as below, It has 92 distinct and 12 unique (after removing rotations and reflections) solutions...and it's my own work, not to mention ;) ;) ) ".

Idea:- The algorithm to solve this problem uses backtracking.Let we have N*N square where we have to place N queens,you must be thinking to create an square of size N*N... oh No Not at all!!!. Create an array (single dimensional), and try to put every possible column  number to put so we have to check every time is there any Queen crossing this position if not go for next rows otherwise get back to previous row and try is there any other possible solution for this row...repeat until you don't get your solution hence back and forth.

To check attacking queens we can try this way: let assume r1 and c1 are already placed queens positions respectively , r2  and c2 are to be placed queens, they will attack each other
if  r1==r2 OR c1==c2 OR absolute(r1-r2)==absolute(c1-c2)

Here the complete Running code:
/*Author Atiqur Rahman on blog atiqwhiz.blogspot.in*/
#include <iostream>

#define N 8
using namespace std;
bool nQueens(int solve[],int n)
{
 int j,r1,r2,c1,c2;
  if(n==N)
  return true;
  for(int i=0;i<N;i++)
  {
      r2=n;
      c2=i;
      for(j=0;j<n;j++)
      {   r1=j;
          c1=solve[j];
        if(r1==r2||c1==c2||abs(r1-r2)==abs(c1-c2))
         break;
      }
    if(j==n)
    {
        solve[n]=i;
        if(nQueens(solve,n+1))
         return true;
    }
  }

return false;
}

int main()
{
   int solve[N];
   if(nQueens(solve,0))
   {   cout<<"Row     Column\n";
       for(int j=0;j<N;j++)
       {
           cout<<j<<"          "<<solve[j]<<endl;
       }
   }
   else
   {
       cout<<"\n\nNo such combination is possible";
   }
 
   return 0;
}

//Happy Coding...
//Let me know if anything is not working....will be happy to respond.

Based on String Processing

1. KMP Algorithm ... A simple and efficient string matching algorithm Click here to see the code

2. Ternary Search Tree...For String Storing and Matching and Traversing.... An Efficient Approach  Click here to see the code

3. Tries-String Storing and matching Program Using C language click here to see the code

Based on Bitwise

1. Given a number having only one ’1′ and all other ’0′s in its binary representation, find position of the only set bit.

2.Find the position of the most significant set bit in a 64-bit signed long int.

3. Count the number of bits that are set to 1, in a 64-bit signed integer.

4. RangeOperation on A(m, n) = m & (m+1) & ... & (n-1) & n.

5. Bit Flooding outward and backward of a set Bit.