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.

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

I have faced this question in Amazon online test.....
You are given an unweighted, undirected graph. Write a program to check if it's a tree topology.

Input

The first line of the input file contains two integers N and M --- number of nodes and number of edges in the graph (0 < N <= 10000, 0 <= M <= 20000). 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).

Output

Print YES if the given graph is a tree, otherwise print NO.

Example

Input:
3 2
1 2
2 3


Output:
YES

Solution:-Things to consider:- 

a) Whether there is cycle or not.

b) Whether there is any connected component exist or not.

General solution Hints:-

Create an Adjacency List/Matrix and maintain an Vector to check out the back edges of the graph if it found return 0, it means it is creating a cycle so it can't be tree. Second thing to consider is whether there is component or not if there is component exist in this case too it can't be tree.

Best Solutions:- Surprisingly solution is very easy if you think hard.

a)First condition can be checked by vertices==edges+1 to be tree.

2)Connected component can be checked by using sets. All edges should be in a single set to be a tree

#include<iostream>
#include<cstdlib>
using namespace std;
void Makeset(int Set[],int N)
{
    for(int i=0;i<=N;i++)
 Set[i]=-1;
}
int Find(int Set[],int size)
{
 if(Set[size]<0)
 return size;
 return Find(Set,Set[size]);
}
bool Union(int Set[],int N)
{
 int u,v,c;
 for(int i=0;i<N;i++)
 { 
  cin>>u>>v;
  --u,--v; //Because values ranges from 1 to n and we have array 0 to n-1 ;)
  u=Find(Set,u);
  v=Find(Set,v);
  if(u==v)
  return false; // if making cycle 
  else if(Set[u]>Set[v])
  {
   c=Set[u];
   Set[u]=v;
   Set[v]+=c; 
  }
  else if(Set[u]<Set[v])
  {
   c=Set[v];
   Set[v]=u;
   Set[u]+=c;
  }
  else
  {
   c=Set[v];
   Set[v]=u;
   Set[u]+=c;
  }
 }
return true;
}
int main()
{   int *Set=NULL;
 int N,M;
 bool f=false;
 cin>>M>>N;
 if(M==N+1)
 {
 Set=new int[M];
  Makeset(Set,N);
 f=Union(Set,N);
 }
if(f)
cout<<"YES";
else
cout<<"NO";
return 0;
}

My solution using Adjacency list goes like this... Don't forget to check out my Adjacency Matrix solution below 

#include<iostream>
using namespace std;
struct Adlist
{
    int data;
    Adlist *next;
};

struct Graph
{
    int V;
    int E;
    Adlist *list;
};

void Create_Graph(Graph *G)
{
  int u,v;
  Adlist *ptr=NULL;
  for(int i=0;i<G->E;i++)
  {   Adlist *node=new Adlist;
      cin>>u>>v;
      u=u-1;
      v=v-1;
      node->data=v;
      node->next=NULL;
   
      if(G->list[u].next==NULL)
      G->list[u].next=node;
      else
      {ptr=G->list[u].next;
      while(ptr->next)
      ptr=ptr->next;
      ptr->next=node;
      }
   
      Adlist *node1=new Adlist;
      node1->data=u;
      node1->next=NULL;
      if(G->list[v].next==NULL)
      G->list[v].next=node1;
      else
      {
          ptr=G->list[v].next;
          while(ptr->next)
          ptr=ptr->next;
          ptr->next=node1;
      }
 
  }
}

void DFS(Graph *G,int u,char *Visited)
{
    if(Visited[u]==49)
    return;
    Visited[u]=49;
 
    for(int v=0;v<G->V;v++)
    {
        DFS(G,v,Visited);
    }
 
}

int main(void)
{ int k=1;
    Graph *G=new Graph;
    if(!G)return 0;
    cin>>G->V>>G->E;
    G->list=new Adlist[G->V];
    if(!G->list)return 0;
   char *Visited=new char[G->V];
   for(int v=0;v<G->V;v++)
    {
        G->list[v].data=0;
        G->list[v].next=NULL;
        Visited[v]=48;
    }
Create_Graph(G);
DFS(G,0,Visited);
for(int i=0;i<G->V;i++)
if(Visited[i]!=49)
{
    k=0;break;
}
if(G->V==G->E+1&&k)
cout<<"YES";
else
cout<<"NO";
}

//By using Adjacency Matrix


#include<iostream>
#include<cstdlib>
using namespace std;

struct Graph
{
int V;
int E;
int **Matrix;
};

Graph *Create(Graph *G)
{
int u,v;
G->Matrix=new int*[G->V];
for(int i=0;i<G->V;i++)
G->Matrix[i]=new int[G->V];
for(int i=0;i<G->E;i++)
{
    cin>>u>>v;
    G->Matrix[u-1][v-1]=1;
    G->Matrix[v-1][u-1]=1;
}
return G;
}

int DFS(Graph *G,int u,int *Visited)
{
    if(Visited[u]!=-1)
    return 0;
    Visited[u]=1;
for(int v=0;v<G->V;v++)
{
    if(G->Matrix[u][v])
       DFS(G,v,Visited);
}
return 1;  
}

int main(void)
{   int *Visited=NULL;
    Graph *G=new Graph;
    cin>>G->V>>G->E;
    G->Matrix=NULL;
    G=Create(G);
    Visited=new int[G->V];
    for(int i=0;i<G->V;i++)
    Visited[i]=-1;
  int k=DFS(G,0,Visited);
  if(k==0)
  cout<<"NO";
  else
  {
      for(int v=0;v<G->V;v++)
      {
          if(Visited[v]==-1)
          {cout<<"NO"; return 0;}
      }
  cout<<"YES";
  }
}

Open Addressing concept of hashing to avoid collision.

Hashing implementation using Open Addressing

Open Addressing is way to not to use chaining to resolve collision, it will try to find a place inside the hash table for the element.This can be done the possible three ways

1.Linear Probing.. Try to search next empty slot to fill by the elements.

like h(k)=h(k)+i mod m(size of the table)

2.Quadratic Probing..Try to search quadratically.like h(k)=h(k)+c*i+c*i^2 mod m (size of the table).

3.Double hashing... Uses double hashing like h(k)=h(k)+i*H(k)mod m(size of table)

   In the below program i have used all the above method, you can active by removing double slash(//) and run it...while you do activate one deactivate others two.

//Hashing by using concepts of Open addressing....a various way implementation

#include <iostream>
#define Max 10
using namespace std;
int j=0;
//Linear Probing.... Remember it does suffer from primary clustering
void LinearProbing(unsigned long N,int Table[],int i)
{
if(Table[(N+i)%Max])
{
LinearProbing(N,Table,++i);
}
else
Table[(N+i)%Max]=N;
}
 
//Quadratic Probing .... Remember it does suffer from secondary clustering
void QuadraticProbing(unsigned long N,int Table[],int i)
{
 
if(j==Max)
{
cout<<"No empty place there...Sorry!!!\n";
return;
}
j++;
int p=0;
p=i+i*i;
if(Table[(N+p)%Max])
QuadraticProbing(N,Table,++i);
else
Table[(N+p)%Max]=N;
}
//Double Hashing.... It can have uniform hashing uses two hash functions
void DoubleHashing(unsigned long N,int Table[],int i)
{
unsigned int key=701%Max;
if(j==Max)
{
    cout<<"No empty slot exist... Sorry !!!\n";
    return;
}
j++;
if(Table[(N+i*key)%Max])
DoubleHashing(N,Table,++i);
else
Table[(N+i*key)%Max]=N;
}
//Insertion of data goes here.....Uses Open addressing approaches to get the slot
void Insert(unsigned long N,int Table[])
{
if(Table[N%Max])
{
//LinearProbing(N,Table,1);
//QuadraticProbing(N,Table,1);
DoubleHashing(N,Table,1);
j=0;
}
else
Table[N%Max]=N;
}    
//Searching through linear probe
int LinearProbSearch(unsigned long N,int Table[],int i)
{
if(j==Max)   
{
return 0;    
}
j++;
if(Table[(N+i)%Max]==N)
return 1;
else
return LinearProbSearch(N,Table,++i);
}
//Search through quadratic probe
int QuadraticProbSearch(unsigned long N,int Table[],int i)
{
unsigned long p=i+i*i;    
if(j==Max)
{
cout<<"Not Found\n";
return 0;
}
j++;
if(Table[(N+p)%Max]==N)
return 1;
else
return QuadraticProbSearch(N,Table,++i);
}
//Searchthrough double hashing
int DoubleHashingSearch(unsigned long int N,int Table[],int i)
{
unsigned long int  k=701%Max;
if(j==Max)
return 0;
j++;
if(Table[(N+i*k)%Max]==N)
return 1;
else
return DoubleHashingSearch(N,Table,++i);
}
 
int Search(unsigned long N,int Table[])
{
if(Table[N%Max]==N)
return 1;
else
{
//return LinearProbSearch(N,Table,1);
//return QuadraticProbSearch(N,Table,1);
return DoubleHashingSearch(N,Table,1);
}
return 0;
}
 
int main()
{
int Table[Max]={0};
unsigned long N;
int i=0;
while(i<10)
{  cin>>N;
 Insert(N,Table);
i++;
}
i=0;
while(i<Max)
cout<<Table[i++]<<endl;
i=0;
cout<<"Enter the integer to be searched\n";
while(i<2)
{
j=0;    
cin>>N;    
Search(N,Table)?cout<<N<<" Exist\n":cout<<N<<" Do not Exist\n";
i++;
} 
return 0;
}

Hashing Program using Division Method and collision resolution by Chaining

It's  Hashing Implementation for long integers, i have used Division method to fix the slot's and chaining to resolve the collision.
Division Method:-
  To efficiently implement(for uniform hashing) division method in a program, there is some fix rule
Note- choose no. of slots (m) , a prime not too close to an exact power of 2, is often a good choice for m.
 i.e h(k)=k mod 701. where as k is key and m=701 ( a prime not close to a power of any 2.).

// Hasihng implementation
#include<stdio.h>
#include<stdlib.h>
#define Max 15
struct Hash
{
long     int data;
struct Hash *next;
};
 
void LookUp(long int N,struct Hash arr[])
{
if(arr[N%Max].data>0)
{       
struct Hash *ptr;
ptr=&arr[N%Max];
while(ptr->next!=NULL)
ptr=ptr->next;
struct Hash *temp;
temp=(struct Hash*)malloc(sizeof(struct Hash));
temp->data=N;
temp->next=NULL;
ptr->next=temp;
}
else
  arr[N%Max].data=N;
}
 
 
// Function for searching the data goes here
int Search(long int N,struct Hash arr[])
{
struct Hash *ptr;
ptr=&arr[N%Max];
while(ptr!=NULL&&ptr->data!=N)
ptr=ptr->next;
if(ptr!=NULL&&ptr->data==N)
return 1;
return 0;
}
//Main goes here
int main(void)
{  
struct Hash arr[Max];
int i=0;long int N;
while(i<Max)
{
arr[i].data=0;
arr[i++].next=NULL;
}
i=0;
while(i++<10)
{
 scanf("%d",&N);;
LookUp(N,arr);
}
 
printf("Table is like this ... Inside\n");
i=0;
struct Hash *temp;
while(i<Max)
{
printf("\n%d ",arr[i].data);
temp=&arr[i];
while(temp->next!=NULL)  
{
temp=temp->next;
printf("%d ",temp->data);
 
}
i++;
}
 
printf("\nEnter the integer to be searched\n"); 
i=0;
while(i++<4)
{
scanf("%ld",&N);
Search(N,arr)?printf("%d Exist\n",N):printf("%d Do not exist\n",N);
}
return 0;
}