[数据结构与算法]洛谷——八皇后问题

题目链接：八皇后问题

java代码：

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static int n, count = 0;
//	b用来表示每一行的棋子放在哪一列，如b[1] = 4表示第一行的棋子存放在第4列
	public static int b[] = new int[14];
	
	public static Scanner in = new Scanner(System.in);
	
    public static void main(String[] args) {
       
    	n = in.nextInt();
//    	函数的参数只需要一个行数
    	f(1);
    	System.out.println(count);
    }
    
    public static void f(int line) {
//    	如果line>n了，表示一种摆放位置的解形成，之后根据目前解的数量以及题目要求，选择性输出结果
    	if(line>n) {
    		count++;
    		if(count>3) return;
    		else {
    			for(int i=1;i<=n;++i) {
    				System.out.print(b[i]);
    				if(i!=n) System.out.print(" ");
    			}
    			System.out.println();
    			return;
    		}
    	}
    	
//    	到了这里就说明棋子还没有摆完（进了前面的if语句就return了）
//    	对第line行的每一列进行遍历
    	for(int i=1;i<=n;++i) {
//    		判断棋子能否放在第line行的第i列
    		if(isPut(line,i)==true) {
//    			更新b数组
    			b[line] = i;
    			f(line+1);
    			b[line] = 0;
    		}
    	}
    }
    
    public static boolean isPut(int line, int col) {
//    	判断规则：通过b数组，根据前面几行存放的数据来判断是否会造成冲突
//    	如line=4, 遍历前面三行中每行的棋子摆放的位置，来判断是否会造成列冲突、两个对角线冲突
    	for(int i=1;i<=line-1;++i) {
    		if(col==b[i]||(line-i)==(col-b[i])||(line-i)==(b[i]-col)) 
    			return false;
    	}
    	return true;
    }
      
}