赞
踩
在一个N*N的棋盘上放置N个皇后,每行一个并使其不能互相攻击(同一行、同一列、同一斜线上的皇后都会自动攻击),问一共有多少种放法?
import java.util.ArrayList; import java.util.List; // n 皇后问题 public class queen { public static List<List<Integer>> ResList=new ArrayList<>(); //结果列表 public static int num=8; //皇后个数 public static void main(String[] args) { List<Integer> list=new ArrayList<>(); //已选好的路径 backtrack(0,list); //从第一行开始放起 for(List<Integer> l:ResList) System.out.println(l); System.out.println("一共有"+ResList.size()+"种答案"); } private static void backtrack(int n, List<Integer> list) { // n表示当前行数 if(list.size()==num){ ResList.add(new ArrayList<>(list)); return ; } for(int i=0;i<num;i++){ //每行从第一列开始试探放皇后 if(!judge(i,n,list)) continue; list.add(i); backtrack(n+1,list); //放置下一行 list.remove(list.size()-1); //返回寻找新的路线 } } private static boolean judge(int i, int n, List<Integer> list) { // i表示当前第n行的列坐标 for(int j=0;j<n;j++){ //判断是否和前面的蜘蛛在同一列,或者同一斜线上 if(list.get(j)==i || Math.abs(n-j)==Math.abs(i-list.get(j))) return false; } return true; } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。