n皇后问题，帮忙找个错误。

主题：n皇后问题，帮忙找个错误。

雅雅哈哈 [专家分：0] 发布于 2008-04-10 20:11:00

好 20:04:14
//5huanghou
#include<iostream.h>
void main()
{
    const int m=5,n=5;
    int A[m][n];
    for(int i=0;i<m;i++)
    {
        {
            A[0][i]=1;
            for(int j=0;j<m;j++)
            {
                if(j!=i)
                A[0][j]=0;
            }
        }
        for(int o=0;o<m;o++)
        {
            {
               A[1][o]=1;
               for(int p=0;p<m;p++)
               {
                  if(o!=p)
                  A[1][p]=0;
               }
            }
            for(int a=0;a<m;a++)
            {
                {
                    A[2][a]=1;
                    for(int b=0;b<m;b++)
                    {
                        if(a!=b)
                        A[2][b]=0;
                    }
                }
                for(int c=0;c<m;c++)
                {
                    {
                        A[3][c]=1;
                        for(int d=0;d<m;d++)
                        {
                            if(c!=d)
                            A[3][d]=0;
                        }
                    }
                    for(int e=0;e<m;e++)
                    {
                        {
                             A[4][e]=1;
                             for(int f=0;f<m;f++)
                             {
                                 if(e!=f)
                                 A[4][f]=0;
                             }
                            if((i!=o&&o!=a&&a!=c&&c!=e)//判断是否在同一列上
                                &&(i!=o+1&&o!=a+1&&a!=c+1&&c!=e+1)//判断是否在同一斜线上
                                    )
                            for(int k=0;k<m;k++)
                            for(int l=0;l<m;l++)
                            {
                               cout<<"  "<<A[k][l];
                               if(l==4)
                               cout<<endl;
                            }
                            cout<<endl;
                        }
                    }
                }
            }
        }
    }
}

本帖地址： http://bbs.pfan.cn/post/272617.html

回复列表（共2个回复）

沙发

boxertony [专家分：23030] 发布于 2008-04-11 14:43:00

你的棋盘状态判断是错误的，如果能改正就能得到正确结果。改正方法最简单的就是把每一行，每一列，每一斜行或列分别加起来，如果不为1说明就是不允许的状态。

另外给几个建议：
1. 每一层循环里的第一个for循环可以取消
           {
               A[1][o]=1;
               for(int p=0;p<m;p++)
               {
                  if(o!=p)
                  A[1][p]=0;
               }
            }
这个for循环可以用
    if(o!=0)
        A[1][o-1]=0;
    else
        A[1][m-1]=0;
代替

2. 5皇后问题用5重循环来做，作为C语言练习是可以的，但是希望能够想出更好的算法来，否则10皇后问题就麻烦了，呵呵。你可以试试用递归来做

板凳

zhqyzhqychn [专家分：20] 发布于 2008-04-11 23:13:00

贴上我写的，o(∩_∩)o...回溯法
#include<stdio.h>
#include<math.h>
#include<malloc.h>
int Place (int row,int *pos,int line)//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;
}

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：n皇后问题，帮忙找个错误。

回复列表（共2个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：n皇后问题，帮忙找个错误。

回复列表 （共2个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共2个回复）