Sudoku Generator program.....


#include<stdio.h>
#include<stdlib.h>



int place(int X[][9],int row,int num)
//returns 1 if "num" can be placed in position "row","X[row,num]". Else return 0
//X[row,num] gives the column number of "num" in "row"
{
int i;
if(num<1||num>9||row<0||row>8)return 0;
num=num-1;   //num is used as column index of solution array X.

for(i=0;i<row;i++)            // check positions of same number upto row-1
if( X[i][num]==X[row][num] || (i/3==row/3)&&(X[i][num]/3==X[row][num]/3) )
return 0;

for(i=0;i<num;i++)        // check if some other placed in same position
if(X[row][i]==X[row][num])
return 0;
return 1;

}

void print_sudoku(int X[][9])
{
int i,j;
int temp[9][9];

for(i=0;i<9;i++)
for(j=0;j<9;j++)
temp[i][X[i][j]]=j+1;

for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
printf("%d  ",temp[i][j]);
printf("\n");
}

}

void sudoku(int X[][9])
{
int row,number;
long int n=0;
row=0;
number=0;   //numbers 0 to 9-1 since it is used as column index of solution array

X[0][0]=-1;

while(number>=0)
{
X[row][number]=X[row][number]+1;

while(X[row][number]<9 && place(X,row,number+1)==0)
X[row][number]=X[row][number]+1;

if(X[row][number]<9)
{
if(row==8)
{
if(number==8){n++; printf("Sudoku no.%ld\n",n);print_sudoku(X); getchar();}
else { row=0; number++; X[row][number]=-1;}
}
else
{
row++;
X[row][number]=-1;
}

}
else if(row==0){number--; row=8;}
else row--;

}


}


main()
{
int X[9][9];
sudoku(X);
}



Sudoku Solver program......


#include<stdio.h>
#include<stdlib.h>



int place(int X[][9],int row,int num,int table[][9])
//returns 1 if "num" can be placed in position "row","X[row,num]". Else return 0
//X[row,num] gives the column number of "num" in "row"
{
int i;
if(num<1||num>9||row<0||row>8)return 0;
num=num-1;   //num is used as column index of solution array X.

for(i=0;i<9 && i!=num;i++)
if(table[row][i]==X[row][num])return 0;

for(i=0;i<row;i++)            // check positions of same number upto row-1
if( X[i][num]==X[row][num] || (i/3==row/3)&&(X[i][num]/3==X[row][num]/3) )
return 0;
for(i=row+1;i<9;i++)
if( table[i][num]!=-1 &&(table[i][num]==X[row][num] || (i/3==row/3)&&(table[i][num]/3==X[row][num]/3)))
return 0;

for(i=0;i<num;i++)        // check if some other placed in same position
if(X[row][i]==X[row][num])
return 0;
for(i=num+1;i<9;i++)    
if(table[row][i]!=-1&&table[row][i]==X[row][num])
return 0;


return 1;

}

void read_table(int problem[][9],int table[][9])
{
int i,j;
printf("Enter the sudoku\nput 0 for blanks\n");

//initialise solution array
for(i=0;i<9;i++)
for(j=0;j<9;j++)
table[i][j]=-1;


for(i=0;i<9;i++)
for(j=0;j<9;j++)
{
scanf("%d",&problem[i][j]);
if(problem[i][j]!=0)table[i][problem[i][j]-1]=j;
}


}

void print_sudoku(int X[][9])
{
int i,j;
int temp[9][9];

for(i=0;i<9;i++)
for(j=0;j<9;j++)
temp[i][X[i][j]]=j+1;

for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
printf("%d  ",temp[i][j]);
printf("\n");
}

}

void sudoku(int X[][9],int table[][9],int problem[][9])
{
int row,number;
long int n=0;
row=0;
number=0;   //numbers 0 to 9-1 since it is used as column index of solution array

X[0][0]=-1;

while(number>=0)
{
if(table[row][number]!=-1)X[row][number]=table[row][number];
else
{
X[row][number]=X[row][number]+1;
while(X[row][number]<9 && place(X,row,number+1,table)==0)
X[row][number]=X[row][number]+1;
}
if(X[row][number]<9)
{
if(row==8)
{
if(number==8){n++; printf("Sudoku no.%ld\n",n);print_sudoku(X); }
else { row=0; number++; X[row][number]=-1;}
}
else
{
row++;
X[row][number]=-1;
}

}
else if(row==0)
{
number--;
row=8;
while(table[row][number]!=-1)
{
if(row==0){number--; row=8;}
row--;
}
}
else
{
row--;
while(table[row][number]!=-1)
{
if(row==0){number--; row=8;}
row--;
}
}

}


}


main()
{
int solution[9][9];
int problem[9][9],table[9][9];
read_table(problem,table);
sudoku(solution,table,problem);
}

Approach #1 for generate the sequence

 #include<stdio.h>
#include<math.h>
main()
{
int n;
long long int num,i,x,j;
long int cnt=0;
printf("\n enter the number of bits :");
scanf("%d",&n);
num=pow(2,n);
printf("\n %lld",num);
for (i=0;i<num;i++)
{
    for (j=0;j<num;j++)
    {
    x=j;
    cnt=0;

    while (x)
        {
        if (x&1)
        cnt++;
        x=x>>1;
        }
    if (cnt==i)
        printf("\n %lld : %ld",j,cnt);
    }
}   
return 1;
}

Generate this Sequence.

Your objective is to print all unsigned integers less than N, where N is the largest unsigned integer that can be represented by the number of bits specified by the user. The order in which the numbers should appear is decided by the following rules.

1. 0 appear first, since its binary representation have zero ones.
2. 1,2,4,8,.... appear next in the increasing order. Note that their binary representation have exactly one one. 
3. 3,5,6,9,.... appear next in the increasing order. Note that their binary representation have exactly two one. 
4. And so on.

One obvious approach is first store all the possible numbers in an array and then sort them based on the number of ones in their binary representation. But this is not what we need since we may need around 16GB of memory to store the numbers if inputs as small as 32. Another approach is to scan this 2^32 numbers 32 times, which may not be a big deal for our processors but still this in not the efficient way of doing it. we can either use some arithmetic relation between numbers of this sequence to find next number if any number in the sequence is given, or we can use bit-wise operators to develop an algorithm to find the next number for any given number.

Answer to Implement hash search in C

Here we use shift- folding as the hashing function and chaining for overflow handling.


#include <stdio.h>
#include <string.h>
#include <malloc.h>

#define MAXLEN 80
#define HASHSIZE 23             // some prime val.
#define SHIFTBY 3               // each group size in hashing.

typedef struct node node;
typedef char *type;

struct node {
   int val;
   char *key;
   node *next;
};
node *h[HASHSIZE];


int hGetIndex(char *key) {
   /*
    * returns index into hashtable applying hash function.
    * uses shift-folding followed by mod function for hashing.
    */
   int i, n, finaln=0;
   char *keyptr;
   for(keyptr=key; *keyptr; finaln+=n)
       for(i=0, n=0; i<SHIFTBY && *keyptr; ++i, ++keyptr)
              n = n*10 + *keyptr;
   finaln %= HASHSIZE;

   return finaln;
}

void hInsert( char *key, int val) {
    /*
     * insert s in hashtable h.
     * use shift-folding followed by mod function for hashing.
     * does NOT check for duplicate insertion.
     */
   node *ptr = (node *)malloc(sizeof(node));
   int index = hGetIndex(key);

   ptr->key = strdup(key);
   ptr->val = val;
   ptr->next = h[index];

   h[index] = ptr;
   printf("h[%d] = %s.\n", index, key);
}

int hGetVal( char *key) {
   /*
    * returns val corresponding to key if present in h else −1.
    */
   node *ptr;
    ptr=h[hGetIndex(key)];
   while (1)
   {
   if (ptr==NULL || strcmp(ptr->key, key)==0)
       break;
    ptr=ptr->next;
    }
   if(ptr)
       return ptr->val;
   return -1;
}

void printHash() {
    /*
     * print the hashtable rowwise.
     */
   int i;
   node *ptr;

   for(i=0; i<HASHSIZE; ++i) {
       printf("%d: ", i);
       for(ptr=h[i]; ptr; ptr=ptr->next)
              printf("%s=%d ", ptr->key, ptr->val);
       printf("\n");
   }
}

int main() {
    char s[MAXLEN];
    int i = 0;
    for (i=0;i<HASHSIZE;i++)
        h[i]=NULL;
    i=0;
    printf("Enter the string to be hashed: ");
    gets(s);

    while(*s) {
       hInsert( s, i++);
       printf("Enter the string to be hashed(enter to end): ");
       gets(s);
    }
    printHash();
    printf("Enter the string to be searched: ");
    gets(s);

    while(*s) {
        i=hGetVal(s);
        if (i!=-1)
               printf("%s was inserted at number %d.\n", s,i);
    else
        printf("%s was not inserted in the hashtable",s);
       
       printf("\nEnter the string to be searched(enter to end): ");
       gets(s);
    }

    return 0;
}

Implement a hash search in C

Write a program that takes strings as inputs and stores them in a hash table.

Then it should then ask the user for strings to be searched in the hash table.

Answer to nth fibonacci number

We have the recursion formula for fibonacci series as
               f(n)=f(n-1)+f(n-2)

We can derive a formula for the function as
 f(n) - f(n-1) - f(n-2) = 0
which is transformed into a recurrence relation problem as..
x^2 - x - 1=0
The solution is  x= (1 + 5)/2 and x=(1- 5)/2.
therefore the homogenius solution is
        .

1 + √5

n

+A2

1 – √5

n

f(n) =

A1

2

2

 Since the initial condition is
     f(0)=0
     f(1)=1
Therefore A1 + A2 =0
               A1*((1 + 5)/2) + A2*((1 - 5)/2) = 1
solving the above two equations ,
A1=(1/5) and A2=(-1/5).

ie. the formula for f(n)=

1

1 + √5

n

–

1 – √5

n

√5

2

2

This formula is called
I present a simple python program to implement this..

import math
a=math.sqrt(5)
p=(1+a)/2
q=(1-a)/2
n=raw_input("enter the number n  : ")
n=int(n)
print int((p**n-q**n)/a)

Find nth fibonacci number without traversing from the start

Write a program to find the nth fibonacci number without traversing from the start index.
ie.. the program should have a time complexity of the order of 1 [O(1)].

Answer to "Find the determinant"

Program :
#include <stdio.h>
#include <math.h>
#include<stdlib.h>
#define EPSILON 1e-10

typedef enum {FALSE, TRUE} bool;
int N;
void print( double **a) {
    /*
     * print the matrix.
     */
    int i, j;

    for( i=0; i<N; ++i ) {
       for( j=0; j<N; ++j )
              printf( "%8.4g ", a[i][j] );
       printf( "\n" );
    }
    printf( "\n" );
}

void divRow( double **a, int row, double divisor ) {
    /*
     * divides row of a by divisor.
     */
    int j;
    for( j=0; j<N; ++j )
    a[row][j] /= divisor;
}

void subRow( double **a, int row1, int row2 ) {
    /*
     * row1 -= row2.
     */
    int j;
    for( j=0; j<N; ++j )
       a[row1][j] -= a[row2][j];
}

bool anyZero( double **a ) {
    /*
     * returns TRUE if any diagonal entry of a is zero (less than EPSILON).
     */
    int i;
    for( i=0; i<N; ++i )
       if( fabs(a[i][i]) <= EPSILON )
             return TRUE;
    return FALSE;
}

double makeUpper( double **a ) {
    /*
     * makes a an upper-triangular matrix.
     * returns 0 if any of the diagonal entries are 0; 1 otherwise.
     */
    int i, j;
    double factor = 1.0;
    double temp;

    for( i=1; i<N; ++i )    // dont worry about row 0.
       for( j=0; j<i; ++j ) {
              temp = a[i][j];
              if( fabs(temp) > EPSILON ) {
                     printf( "factor=%g dividing row %d by %g...\n", factor, i+1, temp );
                     divRow( a, i, temp );
                     print(a);
                     factor *= temp;
              }
              temp = a[j][j];
              if( fabs(temp) > EPSILON && fabs(temp-1.0) > EPSILON ) {
                     printf( "factor=%g dividing row %d by %g...\n", factor, j+1, temp );
                     divRow( a, j, temp );
                     print(a);
                     factor *= temp;
                }
                if( fabs(a[i][j]) > EPSILON ) {
                     printf( "factor=%g row[%d] -= row[%d]...\n", factor, i+1, j+1 );
                       subRow( a, i, j );
                       print(a);
                }
                if( anyZero(a) == TRUE )
                       return 0;
            }
        a[N-1][N-1] *= factor;        // all but(?) last element of row N-1 are zero.

        return 1;
   }

   double multDia( double **a ) {
       /*
        * returns multiplication of diagonal elements.
        */
       int i;
       double factor = 1;

       for( i=0; i<N; ++i )
           factor *= a[i][i];
       return factor;
   }

   int main() {
    int i,j;  
       double **a;
       double factor;
       printf("\n enter the dimension of the matrix : ");
       scanf(" %d",&N);
       a=(double **)malloc (N*sizeof (double *));
       for (i=0;i<N;i++)
           a[i]=(double  *)malloc (N *sizeof(double));
      for (i=0;i<N;i++)
          {
          printf("\n enter row %d : ",i+1);
          for (j=0;j<N;j++)
              scanf(" %lf",&a[i][j]);
    }
   print(a);
   factor = makeUpper(a);
   print(a);
   printf( "determinant = %g.\n", factor*multDia(a) );
}
Explanation:

   1.

      The usual way of finding the value of an N × N determinant is to take the first element of the first row and multiply it by the value of the determinant formed by removing that row and that column. This procedure is followed recursively at every step until only a single element remains whose value itself is the value of the 1 × 1 determinant. The sign of the element being multiplied may change depending on its row and column. In general, if the element has row i and column j, then its sign is determined by the formula (−1)^(i+j).
   2.

      There is another way to solve the problem. We note that if we perform row or column transformations on the determinant, its value does not change. We take advantage of this fact to transform the matrix corresponding to the determinant into an upper or lower triangular matrix and then find its determinant value. It becomes clear that the determinant value of an upper or lower triangular matrix is the product of the diagonal elements. Thus the job of finding a determinant value is basically a matter of making a matrix upper or lower triangular.
   3.

      To make a matrix upper triangular (makeUpper()), we perform row transformations on the matrix. Another important observation is that multiplication of a determinant D by a value v is a new determinant in which any of the rows of D are multiplied by v. Multiplication of a row by v means multiplying each element in the row by v. Thus we maintain a variable factor that keeps track of the multiplier as the rows of the determinant are multiplied or divided by various factors in the process of upper-triangulation. We assume all elements of the determinant to be floating-point numbers.
   4.

      In the process of upper-triangulation, if any of the diagonal elements become 0 (anyZero()), that means the value of the determinant is 0 (remember that the value of the determinant is the multiplication of diagonal elements (multDia()).
   5.

      Since here we assume that the elements are floating-point numbers, the calculations might not be exact. To account for this approximation, we maintain an error term EPSILON which is set to a sufficiently low value (tending to 0). Any value in the range +EPSILON…0…–EPSILON is considered to be 0.
   6.

      The algorithm for making a matrix upper triangular is as follows:

      factor = 1.
      for i=1 to N-1 do
      for j=0 to i-1 do
         divide row i by D[i][j]       // divRow().
         factor *= D[i][j].
         divide row j by D[j][j]       // divRow().
         factor *= D[j][j].
         subtract elements of row j from corresponding elements of row i
      // subRow().
         check for any of the diagonal elements of D to be 0.
      // anyZero().
           determinant = factor*product of diagonal elements.

   7.

      Example:
    Let the determinant be

             | 8 0 1 |
             | 2 1 3 |
             | 5 3 9 |.
       factor = 1.

Snapshots of the algorithm when run on this determinant are shown here.

I       J        STEP               FACTOR       DETERMINANT

1     0     divide row 1 by 2      2             |8       0       1 |
                                                            |1      0.5   1.5 |
                                                            |5      3        9 |

1     0   divide row 0 by 8       16            | 1      0    0.125 |
                                                            | 1    0.5     1.5  |
                                                            | 5      3         9 |

1     0    row 1 −= row 0|       16            | 1      0    0.125 |
                                                            | 0     0.5  1.375 |
                                                            | 5      3          9 |

2     0   divide row 2 by 5       80            | 1      0    0.125 |
                                                            | 0    0.5   1.375 |
                                                            | 1    0.6      1.8 |

2     0    row 2 −= row 0        80            | 1      0   0.125 |
                                                            | 0    0.5  1.375 |
                                                            | 0    0.6  1.675 |

2     1   divide row 2 by 0.6    48             | 1     0   0.125 |
                                                            | 0    0.5  1.375 |
                                                            | 0      1   2.792 |

2    1    divide row 1 by 0.5    24             | 1     0    0.125 |
                                                            | 0      1     2.75 |
                                                            | 0      1   2.792 |

2    1    row 2 −= row 1         24            | 1      0    0.125 |
                                                            | 0      1     2.75  |
                                                            | 0      0   0.0417|

Thus, the determinant = 24*(1*1*0.0417) = 1.

Points to Remember:

   1.

      The first way to solve the problem recursively was natural but clumsy, as it requires removal of a row and a column. So, when designing an algorithm, we should try different approaches and then select the most appropriate one.
   2.

      Note how we reduced the problem of finding a determinant value to making a matrix upper triangular. These reductions not only simplify a problem but can also help in reusing the code and analysis.
   3.

      An error term such as EPSILON should be used in floating point computations.

Find the determinant

Write a program to find the determinant of an N*N matrix.

Answer to "All Graphs are not Trees"

A graph is said to be a tree when it has no cyclic path in it .

So the program focuses to find out whether the given graph is acyclic

by using a two dimensional array of size m*n.

Each row contains the max limit of array,start node and the adjacent nodes from

the previous node.Last index is a flag which is used in case of undirected graph

as here.

In undirected graph when 1-2 is the edge , there is an edge also from 2-1.

Eg :-we prove that the graph 

given by the input :

3 3

1 2

1 3

2 3

is cyclic  as shown in the diagram.

 If for any row , the first and the last element are same,

then the graph is cyclic,that is not a tree.Here in the second row ,node 2 comes 

in front and rear.

The program is described as follows..

#include<stdio.h>

#include<stdlib.h>

 

void print( int **a,int n, int m)

{

  int i,j;

 

  for(i=0;i<n;i++)

    {

      for(j=0;j<a[i][0];j++)printf("%d ",a[i][j]);

      printf("\n");

    }

  printf("\n");

 

}

 

int main()

{

  int n,m,i,j,k,r,c,**a,flag=0,temp,*pos;

 

  scanf("%d%d",&n,&m);

  pos=(int *)malloc(n*sizeof(int));

  a=(int **)malloc(n*sizeof(int *));

  for(i=0;i<n;i++)a[i]=(int *)malloc((m+2)*sizeof(int));

 

  for(i=0;i<n;i++){ a[i][1]=i+1; a[i][0]=2;}

 

 

  for(i=0;i<m;i++)

    {

  scanf("%d%d",&r,&c);

  for(k=0;k<n;k++)pos[k]=0;

 if(r==c){ flag=1; break;}

  if(r!=c)

    {

 for(j=0;j<n;j++)

    {

 

      if(a[j][a[j][0]-1]==r){ a[j][a[j][0]]=c; a[j][0]++; pos[j]=1;  }  

   }

 for(j=0;j<n;j++)

    {

     if(pos[j]==0&&a[j][a[j][0]-1]==c){ a[j][a[j][0]]=r; a[j][0]++; }     

    }  

print(a,n,m);

    }

    }

  if(flag==1){printf("NOT A TREE\n"); return 0; }

for(i=0;i<n;i++)

  {

if(a[i][0]>2&&a[i][1]==a[i][a[i][0]-1]){printf("YES\n"); return 0;}

  }

printf("TREE\n");

 

}

All Graphs are not Trees.

You are given an unweighted, undirected graph. Write a program to check if it's a tree topology.

The first line of the input file contains two integers N and M --- number of nodes and number of edges in the graph . Next M lines contain M edges of that graph --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u,v <= N).

Example 1

Input:
3 2
1 2
2 3


Output:
TREE

Example 2
Input:
3 3
1 2
1 3
2 3

Output:
NOT A TREE