2008
05-30

#include<stdio.h>
#include<math.h>
#include<malloc.h>
#define Gragh 1
int Place (int row,int *pos,int line)       //*pos是什么意思


          //to judge whether the queen can be placed here
  {            
    int count=0;
    while(count<line)
       {
          if(*(pos+count)==row||abs(*(pos+count)-row)==abs(count-line))
          return 0;
          count++;
     }
           return 1;          //can be placed here;
      }
void Display(int *pos,int n)
{
           int i,j;
           printf(“\n”);
          for(i=0;i<n;i++)           //output the gragh
                {
              for(j=0;j<n;j++)
              if(*(pos+i)!=j)printf(“* “);
              else printf(“Q “);
              printf(“\n”);
        }


             /* for(i=0;i<n;i++)
             printf(“%d “,*(pos+i));                 //output the row number*/
}
int nQueens(int n)
        {
          int *pos=(int *)malloc(n*sizeof(int));
          int line=0,row,i, count=0;
          for(i=0;i<n;i++)
          pos[i]=-1;
          while(line>=0)             //the condition of the backtracking
               {
               row=pos[line]+1;       //shift to next row if backtracking
               while(row<n&&!Place(row,pos,line))
               row++;            //if can’t be placed this row,move to next
               if(row<n)              //if find a place to put the queen
                 {
                  pos[line]=row;
                  if(line==n-1)           //if all queens have been in place
                    {
                      Display(pos,n);
                      count++;              //the number of the answer
                       }
               else
               line++;   //if there still some queens to be placed move to the next line
             }
         else
             pos[line--]=-1;
                              //if can’t find a place to place the queen ,backtrack
             }
           return count;
             }
    int main()
    {
            int n;
           printf(“please input the number of queens\n”);
            scanf(“%d”,&n);
             printf(“\nthe answer is: %d\n”,nQueens(n));


            return 0;
  }


在网上找到一个八皇后的代码,可是有些看不懂,希望有人能帮我看看,把主要思路讲解一下,谢谢了,主要思路,多谢!!!!


留下一个回复