如何在单个全局数组的帮助下使用回溯编写n皇后问题的c代码？ [英] How do i write a c code for n queen problem using backtracking with the help of a single global array?

问题描述

我在互联网上找到了这个工作的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输入后面的数字）; 
 scanf（ ％d，& n）; 
 queen（ 1 ，n）; 
 getch（）; 
} 
  void  queen（ int 行， int  n）
 {
  int 列; 
  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 列）
 {
  int  i; 
  for （i =  0 ; i< = row-  1 ; i ++）
 {
  if （board [i] == column）
  return   0 ; 
  if （abs（board [i] -column）== abs（i-row））
 返回  0 ; 
} 
 返回  1 ; 
} 
  void  print（ int  n）
 { int  i，j; 
 printf（  \ n \ n soluntion％d \ n \ n，计数++）; 
  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  - ）; 
} 
} 
} 

解决方案

当你想了解在做什么的时候代码，调试器是首选的工具。

调试器允许逐行运行代码，你可以检查2行之间的所有变量。



掌握调试器是必备技能。



对于N皇后问题，试着想一想用一张纸和一支钢笔怎么做。当你不能在下一行放置女王时，要注意你做什么。



建议：找一些关于回溯的教程和文档。

你也可以尝试在迷宫中找到路径并查看你遇到死路时的行为。

nv3是对的，要完全理解你应该调试它。



它是递归：它意味着一个函数正在调用它自己。关键是，这个功能需要一些中止逻辑才能正常工作。



获取 Visual Studio Community Edition 并试试运气。

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:

 #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-");
     }
   }
}

解决方案

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.

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.

这篇关于如何在单个全局数组的帮助下使用回溯编写n皇后问题的c代码？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！