每日一算法:八皇后问题

可以设置3个数组，分别记录8列及各条对角线上有没有皇后。思路就是从第一行开始，找一个可用格，对该格占用的列及对角线作标志，然后试下一行。如果一行中没有合适的位置，就回溯一行，再试下一个格子，不行再回溯，直到回溯到第一行为止。
大概的算法如下

1 当前行n=1
2 对于第n个皇后，在第n行从左到右找一个列及两条对角线都没有被占用的空格，如果找到这样的空格转3，否则n=n-1，转4退回一行
3 皇后放在该格，设置对应列及对角线的占用标志，如果n=8，输出一个结果并转4，否则n=n+1，转2
4 如果n=0，就结束。否则将当前行(第n行)的皇后占用的列及对角线标志清除，在当前格右边继续找一个可用格。找到的话转3，否则n=n-1，转4再退回一行

  

   

    

     

    
    

     

      #include <stdio.h> 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #define N 8 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int column[N+1]; // 同栏是否有皇后，1表示有 
     
    
   

    

     

    
    

     

      int rup[2*N+1]; // 右上至左下是否有皇后 
     
    
   

    

     

    
    

     

      int lup[2*N+1]; // 左上至右下是否有皇后 
     
    
   

    

     

    
    

     

      int queen[N+1] = {0}; 
     
    
   

    

     

    
    

     

      int num; // 解答编号 
     
    
   

    

     

    
    

     

      void backtrack(int); // 回溯求解 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(void)
     
    
   

    

     

    
    

     

       { 
     
    
   

    

     

    
    

     
	int i; 
     
    
   

    

     

    
    

     

      	num = 0; 
     
    
   

    

     

    
    

     
	for(i = 1; i <= N; i++) 
     
    
   

    

     

    
    

     

      		column[i] = 1; 
     
    
   

    

     

    
    

     
	for(i = 1; i <= 2*N; i++) 
     
    
   

    

     

    
    

     

      		rup[i] = lup[i] = 1; 
     
    
   

    

     

    
    

     

      	backtrack(1); 
     
    
   

    

     

    
    

     
	return 0; 
     
    
   

    

     

    
    

     

      } 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void showAnswer() 
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int x, y;
     
    
   

    

     

    
    

     
	printf("\n解答 %d\n", ++num);
     
    
   

    

     

    
    

     
	for(y = 1; y <= N; y++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		for(x = 1; x <= N; x++)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			if(queen[y] == x)
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     
 printf(" Q");
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			else
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     
 printf(" .");
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		printf("\n");
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void backtrack(int i) 
     
    
   

    

     

    
    

     

      { 
     
    
   

    

     

    
    

     
	int j;
     
    
   

    

     

    
    

     
	if(i > N) 
     
    
   

    

     

    
    

     

      	{ 
     
    
   

    

     

    
    

     

      		showAnswer();
     
    
   

    

     

    
    

     

      	} 
     
    
   

    

     

    
    

     
	else 
     
    
   

    

     

    
    

     

      	{ 
     
    
   

    

     

    
    

     
		for(j = 1; j <= N; j++) 
     
    
   

    

     

    
    

     

      		{ 
     
    
   

    

     

    
    

     
			if(column[j] == 1 && rup[i+j] == 1 && lup[i-j+N] == 1) 
     
    
   

    

     

    
    

     

      			{ 
     
    
   

    

     

    
    

     

       queen[i] = j; 
     
    
   

    

     

    
    

     
 // 设定为占用
     
    
   

    

     

    
    

     

       column[j] = rup[i+j] = lup[i-j+N] = 0; 
     
    
   

    

     

    
    

     

       backtrack(i+1); 
     
    
   

    

     

    
    

     

       column[j] = rup[i+j] = lup[i-j+N] = 1; 
     
    
   

    

     

    
    

     

      			} 
     
    
   

    

     

    
    

     

      		} 
     
    
   

    

     

    
    

     

      	} 
     
    
   

    

     

    
    

     

      } 
     
    
  
 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/15503441