八皇后问题(递归回溯法)--Java实现

一时失言乱红尘 2022-02-17 18:14 305阅读 0赞

一.题目

经典的八皇后问题是要将八个皇后放在棋盘上,任何两个皇后不能相互攻击(即没有两个皇后是在同一行,同一列或者同意对角线上).编写程序列出所有的解决方案和解决方案的总数.

二.代码及思想

package work22;
    
    
    public class Test {
    	
    	public static int[][] array = new int[8][8];	//初始化棋盘
    	
    	public static int map;		//八皇后可能解的个数
    
    	public static void main(String[] args) {
    		// TODO 自动生成的方法存根
    		
    		System.out.println("八皇后问题 : ");
    		
    		search(0);
    		
    		//System.out.println();
    		
    		System.out.println("八皇后一共有" + map + "个解");
    
    	}
    	
    	
    	public static void search(int i){
    		
    		if(i > 7){
    			
    			map++;
    			
    			print();
    			
    			return;		//return后会接着指向array[i][j]=0,然后继续for循环,寻找下一个合适的解
    			
    			
    		}
    		
    		for(int j = 0; j < 8; j++){
    			
    			if(check(i, j)){
    				
    				array[i][j] = 1;
    				
    				search(i+1);
    				
    				array[i][j] = 0;		//清零,以免回溯的时候出现脏数据,当这一行都没有合适结点时被调用
    				
    			}
    			
    			
    		}
    		
    		
    		
    	}
    	
    	
    	public static boolean check(int i, int j){		//检查该结点是否符合条件
    		
    		for(int k = 0; k < i; k++){		//检查与该结点在一列上的元素是否有不为1的结点,且只检查在改结点上方的行,因为下方的行全为0,无需检查
    			
    			if(array[k][j] == 1){
    				
    				return false;
    			}
    			
    		}
    		
    		
    		for(int m = i-1, n = j-1; m>=0&& n>=0; m--, n--){		//检查左对角线上的元素
    			
    			if(array[m][n] == 1){
    				
    				return false;
    				
    			}
    			
    		}
    		
    		
    		for(int m = i-1, n = j+1; m>=0&& n<=7; m--, n++){		//检查右对角线上的元素
    			
    			if(array[m][n] == 1){
    				
    				return false;
    				
    			}
    			
    		}
    		
    		
    		return true;
    		
    		
    		
    	}
    	
    	
    	public static void print(){		//打印符合条件结点的位置
    		
    		for(int i = 0; i < 8; i++){
    			
    			for(int j = 0; j < 8; j++){
    				
    				
    				if(array[i][j] == 1){
    					
    					System.out.print("[" + i + " ," + j + "]   ");
    					
    					
    				}
    				
    				
    			}
    			
    		}
    		
    		
    		System.out.println();
    		
    		
    	}
    
    }

核心代码是search方法,该方法有一个参数i表示当前判断到第几行,if(i > 7)这个判断表示已经找到了一种情况(即行数已经超过7),然后调用print方法打印该种情况,并通过return语句返回到上一次递归中的array\[i\]\[j\] = 0,将这种情况下的最后一个值清为0,并在此基础上接着for循环寻找改行下一个可能的值,若没有,则接着向上回溯.

解决八皇后问题使用的是递归回溯算法.