经典算法八皇后问题有多少种解法？你想知道吗...

迷南。 2023-03-14 10:44 13阅读 0赞

## 运行结果 ##

![运行结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70]

## 说明 ##

*  在本题中，棋盘是由8行8列，共64个格子构成
 *  运行结果中的 \[7, 3, 0, 2, 5, 1, 6, 4\] 的意思是：
    
     *  第1行第8(7+1)列放第1个皇后
     *  第2行第4(3+1)列放第2个皇后
     *  第3行第1(0+1)列放第3个皇后
     *  其它依此类推…
 *  示意图如下：

## 源代码 ##

import java.util.Arrays;
    
    // 八皇后问题求解
    
    public class Queue8 { 
    	// 皇后的个数
    	int max = 8;
    	// 摆放方案的个数
    	static int count = 0;
    	// 保存每个皇后的位置，因为每行只放一个皇后，所以只用了一个一维数组保存列号即可
    	int[] arr = new int[max];
    	
    	public static void main(String[] args) { 
    		
    		Queue8 queue8 = new Queue8();
    		queue8.layout(0);
    		System.out.println("八皇后问题共有"+count+"个解法");
    	}
    	
    	// 放置皇后
    	private void layout(int n) { 
    		if(n == max) { 
    			// 这时说明已经摆放完了
    			System.out.println(Arrays.toString(arr));
    			count++;
    			return;
    		}
    		
    		// 对每个皇后，都依次去尝试摆放在每一列
    		for(int i = 0; i < max; i++) { 
    			arr[n] = i;
    			// 判断这个皇后摆放位置是否冲突
    			if(judge(n)) { 
    				// 如果当前位置不冲突，继续递归，摆放下一个皇后
    				layout(n+1);
    			}
    			// 如果发生冲突，进入下一轮循环，尝试摆放在下一列
    		}
    	}
    	
    	// 判断第n个皇后是否和前面的冲突
    	private boolean judge(int n) { 
    		for(int i = 0; i < n; i++) { 
    			// 判断是否在同一列，或一条对角线上
    			if(arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[i] - arr[n])) { 
    				return false;
    			}
    		}
    		return true;
    	}
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70]: /images/20230312/85d167fd446b4e5ea9c0df59db81ad29.png