Backtracking Algorithm

  • N-Queen problem:

    
    #include iostream.h
    #include math.h
    //plz insert the tags of header libraries by your own
    class backtracking
    {
    protected:
    	int *ans;
    	int m;
    	int l;
    public:
           backtracking(int n,int o);
    	void backtrack(int k);
    	virtual int condition(int k,int i);
    	virtual void out();
    };
    backtracking::backtracking(int n,int o)
    {
    	m=n;
    	ans=new int[n];
    	l=o;
    }
    void backtracking::backtrack(int k)
    {
    	int j;
    	while(k>0)
    	{
    		for(j=ans[k]+1;j<l;j++)
    		{
    			if(condition(k,j))
    			{
    				ans[k]=j;
    				if(k==l)
    					out();
    				else
    				{
    					k++;
    					j=ans[k];
    				}
    			}
    		}
    		ans[k]=-1;
    		k--;
    	}
    }
    class NQueen:public backtracking
    {
    public:
    	NQueen(int n,int l):backtracking(n,l){}
    	int condition(int k,int i);
    	void out();
    };
    int NQueen::condition(int k,int i)
    {
    	if(i==0&&k==0)return 0;
    	for(int j=0;j<k;j++)
    	{
    		if(i==ans[j]||(abs(i-ans[j])==(k-j)))
    			return 0;
    	}
    	return 1;
    }
    void NQueen::out()
    {
    	for(int i=0;i<m;i++)
    		cout<<ans[i]<<"\t";
    	cout<<"\n";
    }
    void main()
    {
    	backtracking *pointer;
    	NQueen ob(4,4);
    	pointer=&ob;
    	ob.backtrack(0);                    }
    
  • 8-Queen problems
    #include iostream.h
    #include math.h
    #include conio.h
    //plz insert the tags of header libraries by your own
    int ans[8],count;
    int Length;
    int place(int k,int i)
    {
    	if(i==0&&k==0)return 0;
    	for(int j=0;j=0)
    	{
    		for(j=ans[k]+1;j<Length;j++)
    		{
    			if(place(k,j))
    			{
    				ans[k]=j;
    				if(k==Length-1)
    				{
    					for(int l=0;l<Length;l++)
    						cout<<ans[l]<<"\t";
    					cout<<"\n";
    					count++;
    				}
    				else
    				{
    					k=(k+1);
    					j=ans[k];
    				}
    			}
    		}
    		ans[k]=-1;
    		k--;
    	}
    }
    void main()
    {
    	clrscr();
    	count=0;
    	Length=6;
    	for(int i=0;i<Length;i++)ans[i]=-1;
    	backtrack(0);
    	getch();
    	cout<<count;
    	getch();
    }
    
  • N-queen recursive:
    #include iostream.h
    #include math.h
    //plz insert the tags of header libraries by your own
    int place(int k,int i);
    void Nqueen(int k,int n);
    int x[8];
    int count;
    void main()
    {
    	count=0;
    	Nqueen(0,8);
    /*	for(int i=0;i<8;i++)
    		cout<<x[i]<<"\t";*/
    	cout<<"\n\nNumber of solution is :"<<count<<"\n";
    }
    int place(int k,int i)
    {
    	for(int j=0;j<k;j++)
    	{
    		if(x[j]==i||abs(x[j]-i)==k-j)
    			return 0;
    	}
    	return 1;
    }
    void Nqueen(int k,int n)
    {
    	for(int i=0;i<n;i++)
    		if(place(k,i))
    		{
    			x[k]=i;
    			if(k==n-1)
    			{
    				for(int j=0;j<n;j++)
    					cout<<x[j]+1<<"\t";
    				cout<<"\n";
    				count++;
    			}
    			else Nqueen(k+1,n);
    		}
    }
    
    
    
  • 3 thoughts on “Backtracking Algorithm

    Leave a Reply

    Please log in using one of these methods to post your comment:

    WordPress.com Logo

    You are commenting using your WordPress.com account. Log Out /  Change )

    Google photo

    You are commenting using your Google account. Log Out /  Change )

    Twitter picture

    You are commenting using your Twitter account. Log Out /  Change )

    Facebook photo

    You are commenting using your Facebook account. Log Out /  Change )

    Connecting to %s