每日一算法:八皇后问题

Love The Way You Lie 2022-09-18 07:53 135阅读 0赞

可以设置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; 
    			} 
    		} 
    	} 
    }