[已解决]关于八皇后的问题

HUC等风

#include"stdio.h"
int sum=0;
int notDanger(int row,int j,int (*chess)[8])
{   int i,k=0,m;
   //判断列方向
        for(i=0;i<8;i++)
        {  if(*(*(chess+i)+j)!=0)
               {k=1;break;}
        }
        //判断左上方
        for(i=row,m=j;i>=0&&m>=0;i--,m--)
        {
        if(*(*(chess+i)+m)!=0)       
                         {k=1;break;}
        }
        //判断右下方
        for(i=row,m=j;i<8&&m<8;i++,m++)
        {
        if(*(*(chess+i)+m)!=0)       
                         {k=1;break;}
        }
    //判断右上方
   for(i=row,m=j;i>=0&&m<8;i--,m++)
        {
        if(*(*(chess+i)+m)!=0)       
                         {k=1;break;}
        }
   //判断左下方
  for(i=row,m=j;i<8&&m>=0;i++,m--)
        {
        if(*(*(chess+i)+m)!=0)       
                         {k=1;break;}
        }
  return k;

}

//参数 row  表示起始行
//参数 n 表示列数
//参数 (*chess)[8] 表示指向棋盘每一行的指针
void EightQueen(int row,int n,int (*chess)[8])
{ int chess2[8][8];
  int i,j;
            for(i=0;i<8;i++)
                for(j=0;j<8;j++)
                    chess2[i][j]=chess[i][j];
  if(8==row)
  {/*  for(i=0;i<8;i++){
        for(j=0;j<8;j++)
                        printf("%d  ",*(*(chess2+i)+j));
                    printf("\n");
                       }*/
  sum=sum+1;;
    printf("\n");
  }
  else
  {   
          //如果没有危险就继续往下
          for(j=0;j<n;j++)
          { if(notDanger(row,j,chess2))//判断这个位置是否有危险
            { for(i=0;i<8;i++)
                {
                      *(*(chess2+i)+j)=0;
                  }
              *(*(chess2+row)+j)=1;
                  EightQueen(row+1,n,chess2);
            }
          }  
  }
}
void main()
{  int  chess[8][8],i,j;
    for(i=0;i<8;i++)
       for(j=0;j<8;j++)
          chess[i][j]=0;
    EightQueen(0,8,chess);
printf("%d\n",sum);

}

最佳答案

月排行榜 / 总排行榜

claws0n

2018-10-1 19:14:47

#include <stdio.h>


int count = 0;

int notDanger(int row, int j, int (*chess)[8])
{
        int i, k, flag1 = 0, flag2 = 0, flag3 = 0, flag4 = 0, flag5 = 0;
        // check column
        for(i = 0; i < 8; i++)
        {
                if( *(*(chess+i)+j) != 0)
                {
                        flag1 = 1;
                        break;
                }
        }
        
        // check diagonal left-up
        for(i = row, k = j; i >= 0 && k >= 0; i--, k--)
        {
                if( *(*(chess+i)+k) != 0 )
                {
                        flag2 = 1;
                        break;
                }
        }
        
        // check diagonal right-down
        for(i = row, k = j; i < 8 && k < 8; i++, k++)
        {
                if( *(*(chess+i)+k) != 0 )
                {
                        flag3 = 1;
                        break;
                }
        }
        
        // check diagonal right-up
        for(i = row, k = j; i >= 0 && k < 8; i--, k++)
        {
                if( *(*(chess+i)+k) != 0 )
                {
                        flag4 = 1;
                        break;
                }
        }
        
        // check diagonal left-down
        for(i = row, k = j; i < 8 && k >= 0; i++, k--)
        {
                if( *(*(chess+i)+k) != 0 )
                {
                        flag5 = 1;
                        break;
                }
        }
        
        if( flag1 || flag2 || flag3 || flag4 || flag5 )
        {
                return 0;
        }
        else
        {
                return 1;
        }
}
        

// n is col
// row pointer
void EightQueen(int row, int n, int (*chess)[8])
{
        int chess2[8][8], i, j;  // temp chessboard
        
        for(i = 0; i < 8; i++)
        {
                for(j = 0; j < 8; j++)
                {
                        chess2[i][j] = chess[i][j];
                }
        }
        
        // Core recursion
        if(row == 8)
        {
                printf("%d-th solution\n", count+1);
                for(i = 0; i < 8; i++)
                {
                        for(j = 0; j < 8; j++)
                        {
                                printf("%d ", *(*(chess2+i)+j));
                        }
                        printf("\n");
                }
                printf("\n");
                count++;
        }
        else
        {
                // Is this a valid position?
                // If yes, continue...
                for(j = 0; j < n; j++)
                {
                        if( notDanger(row, j, chess) ) // valid position?
                        {
                                for(i = 0; i < 8; i++)
                                {
                                        *(*(chess2+row)+i) = 0;
                                }
                                *(*(chess2+row)+j) = 1;
                                
                                EightQueen(row+1, n, chess2);
                        }
                }
        }
        
}


int main(void)
{
        int chess[8][8], i, j;
        
        for(i = 0; i < 8; i++)
        {
                for(j = 0; j < 8; j++)
                {
                        chess[i][j] = 0;
                }
        }
        
        EightQueen(0, 8, chess);
        
        printf("There are %d number of solutions in total\n\n", count);
        
        return 0;
}

注释自己换一下吧~

跳转到最佳答案楼层

HUC等风

编译没问题，但执行有问题

claws0n

#include <stdio.h>


int count = 0;

int notDanger(int row, int j, int (*chess)[8])
{
        int i, k, flag1 = 0, flag2 = 0, flag3 = 0, flag4 = 0, flag5 = 0;
        // check column
        for(i = 0; i < 8; i++)
        {
                if( *(*(chess+i)+j) != 0)
                {
                        flag1 = 1;
                        break;
                }
        }
        
        // check diagonal left-up
        for(i = row, k = j; i >= 0 && k >= 0; i--, k--)
        {
                if( *(*(chess+i)+k) != 0 )
                {
                        flag2 = 1;
                        break;
                }
        }
        
        // check diagonal right-down
        for(i = row, k = j; i < 8 && k < 8; i++, k++)
        {
                if( *(*(chess+i)+k) != 0 )
                {
                        flag3 = 1;
                        break;
                }
        }
        
        // check diagonal right-up
        for(i = row, k = j; i >= 0 && k < 8; i--, k++)
        {
                if( *(*(chess+i)+k) != 0 )
                {
                        flag4 = 1;
                        break;
                }
        }
        
        // check diagonal left-down
        for(i = row, k = j; i < 8 && k >= 0; i++, k--)
        {
                if( *(*(chess+i)+k) != 0 )
                {
                        flag5 = 1;
                        break;
                }
        }
        
        if( flag1 || flag2 || flag3 || flag4 || flag5 )
        {
                return 0;
        }
        else
        {
                return 1;
        }
}
        

// n is col
// row pointer
void EightQueen(int row, int n, int (*chess)[8])
{
        int chess2[8][8], i, j;  // temp chessboard
        
        for(i = 0; i < 8; i++)
        {
                for(j = 0; j < 8; j++)
                {
                        chess2[i][j] = chess[i][j];
                }
        }
        
        // Core recursion
        if(row == 8)
        {
                printf("%d-th solution\n", count+1);
                for(i = 0; i < 8; i++)
                {
                        for(j = 0; j < 8; j++)
                        {
                                printf("%d ", *(*(chess2+i)+j));
                        }
                        printf("\n");
                }
                printf("\n");
                count++;
        }
        else
        {
                // Is this a valid position?
                // If yes, continue...
                for(j = 0; j < n; j++)
                {
                        if( notDanger(row, j, chess) ) // valid position?
                        {
                                for(i = 0; i < 8; i++)
                                {
                                        *(*(chess2+row)+i) = 0;
                                }
                                *(*(chess2+row)+j) = 1;
                                
                                EightQueen(row+1, n, chess2);
                        }
                }
        }
        
}


int main(void)
{
        int chess[8][8], i, j;
        
        for(i = 0; i < 8; i++)
        {
                for(j = 0; j < 8; j++)
                {
                        chess[i][j] = 0;
                }
        }
        
        EightQueen(0, 8, chess);
        
        printf("There are %d number of solutions in total\n\n", count);
        
        return 0;
}

注释自己换一下吧~

HUC等风

感谢楼上