Click here to Skip to main content
15,887,683 members
Please Sign up or sign in to vote.
1.00/5 (4 votes)
See more:
I found this working c code on the internet.But was not able to understand the backtracking part in it.

How does the code backtracks once it encounters a dead end.

What I have tried:

C++
 #include<stdio.h>
 #include<conio.h>
 #include<math.h>
  int board[10],count=1;
  void queen(int,int);
  int place(int,int);
  void print (int);
  void main()
  {
    int n;
    clrscr();
    printf("\n enter the number of queen");
    scanf("%d",&n);
    queen(1,n);
    getch();
  }
  void queen(int row,int n)
  {
   int column;
    for(column=0;column<=n;column++)
    {
      if(place(row,column))
      {
      board[row]=column;
      if(row==n)
      print(n);
      else
      queen(row+1,n);
      }
    }
   }
   int place(int row,int column)
   {
     int i;
     for(i=0;i<=row-1;i++)
     {
     if(board[i]==column)
     return 0;
     if(abs(board[i]-column)==abs(i-row))
     return 0;
     }
     return 1;
   }
    void print(int n)
  { int i,j;
    printf("\n\n soluntion %d \n\n",count++);
    for(i=1;i<=n;i++)
    printf("\t%d",i);
    for(i=1;i<=n;i++)
   {
     printf("\n %d",i);
     for(j=1;j<=n;j++)
     { if(board[i]==j)
       printf("\tQ");
       else
       printf("\t-");
     }
   }
}
Posted
Updated 23-Feb-16 4:26am
v2
Comments
nv3 23-Feb-16 9:28am    
How do you write a C program ...? That's simple to answer: Use a text editor or even better, use an IDE (integrated development environment) like Visual Studio. Think about the algorithm, write the code, and finally test it in a debugger. That's how everybody does it :-)
[no name] 23-Feb-16 9:36am    
wow! thanks genius
nv3 23-Feb-16 10:06am    
Instead of doing your homework you hunt for some code in the internet and don't even want to invest the time to understand it. You will probably not get very far in this way. Good luck!

When you want to understand what is doing a piece of code, the debugger is the tool of choice.
The debugger allow to run the code line by line and you can inspect all variables between 2 lines.

Mastering the debugger is a must have skill.

For the N queens problem, try to think how you would do with a sheet of paper and a pen. Paid attention at what you do when you can't place a queen on next row.

advice: find some tutorials and documentation about backtracking.
You can also try to find the path in a maze and see what you do when you hit a dead end.
 
Share this answer
 
nv3 is right, to fully understand it you should debug it.

It is recursion: it means that a function is calling itsself. The key is, that this functions needs some abort logic to work properly.

Get the Visual Studio Community Editionand try your luck.
 
Share this answer
 
Comments
[no name] 23-Feb-16 9:47am    
I came here only after i tried it enough.The thing is i am not able to get where does the backtracking thing start once there is no valid box to place a queen in a particular row.
F-ES Sitecore 23-Feb-16 10:00am    
Ask your class tutor, we're not here to do your work for you. Just remember that the code you're looking to hand in has also been found by all the other people in your class that don't want to do their own work.
[no name] 23-Feb-16 10:08am    
If you all dont have the time or the knowledge or the inclination to give a suitable answer to the problem i posted,then please stop wasting your time to comment on this thread.
F-ES Sitecore 23-Feb-16 10:10am    
If you don't have the knowledge to do your own homework then advise your tutor of this so that you can get remedial training rather than trying to cheat.
[no name] 23-Feb-16 10:14am    
[insulting comment removed]

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900