N皇后问题
package cn.gao.algorithm2.service;/* * 经典的八皇后问题（恒生电子笔试B卷最后一题,当初哥用8个for循环，真汗颜，无脸面江东父老。。。） * 八皇后问题是一个古老而著名的问题，是递归中回溯算法的典型例题。在8X8格的国际象棋上摆放八个皇后， * 使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一正反斜线上，问有多少种摆法。 * 这里将八皇后推广位N皇后问题NightQueueTest类实现此功能 * * 解决思想： * 构建规则函数，判断在某列col中,行为row的元素是否"碰撞"过原来的元素，即与之前的0-col-1咧的每个元素都不会在同一行，同一列，同一正反斜线上相遇 * 构建通路函数：判断某列col中，能不能走通，即判断到第8列且第8列是符合前面规则的. * */public class NightQueueTest {/*判断规则函数，判断某个列是否'碰撞'过之前的数据*/public int queenList[];/*记录皇后数组，下标表示列，值表示列所对应的行*/public int count;/*统计路径方案种数*/public int n;/*皇后问题规模*/ public NightQueueTest(int n) {/*初始一个N规模的皇后问题*/super();this.queenList = new int[n];this.count = 0;this.n=n;}public boolean check(int col,int row)/*判断之前列的点与当前点不在同一行，同一正反斜线上*/ { for(int i=0;i<col;i++) { if(queenList[i]==row||(queenList[i]+i==row+col)||(queenList[i]-i==row-col)) { return false; } } return true; } public void findCorrectPath(int col)/*判断第col列是否能够走通，即当前第col列到第8列都能够走通*/ { if(col==this.n)/*前面0-7个都已经遍历完毕，所以如果到了col=8，说明前面7个都正确，表示整个路径分布成功了*/ { count++; System.out.println("第"+count+"种方案:"); for(int i=0;i<queenList.length;i++)/*打印已有方案*/ { System.out.println("第"+i+"列"+"第"+queenList[i]+"行："+"第"+(i+1)+"个皇后"); } System.out.println("\n\n"); return ; } else{ int row=0; while(row<this.n) { if(check(col,row))/*当前第col列选取的第row行是符合规则的*/ { //System.out.println("aaaa:"+count+": "+col+row); queenList[col]=row;/*有点进栈的味道*/ findCorrectPath(col+1); queenList[col]=0;/*有点出栈的味道*/ } row++; } } }public static void main(String[] args) {NightQueueTest gao=new NightQueueTest(8);gao.findCorrectPath(0);}}?