今天上算法课,要求写数组的全排列,要用递归和回溯法来写,结果发现都很尴尬,听得懂算法写不出来, 然后上百度查数组的全排列,分别查了递归跟全排列,发现有些文章,好像分不清递归和回溯法,回溯法以前写过的到现在又忘了, 所以打算动手写一写,写了一个晚上发现,数组和八皇后这两个问题,递归和回溯法有点难分离,都有各自的有点. 然后特别是八皇后问题,我打算先看别人的递归法,看了几遍自己动手dubug一段时间就可以了,然后去看别人的回溯法, 发现回溯法好像更加花时间,就不打算写回溯法了.
package java_chapter4_7; public class Queens { private static final int N=8; private static int num=0;//统计可行解的个数 public static void main(String[] args) { int[][] chess=new int[N][N]; putQueenAtRow(chess,0); } private static void putQueenAtRow(int[][] chess,int row) { /* * 如果row=8>7 * 即刚刚好突破了递归的极限了 * 可以输出之前的排序了 */ if(row==N) { num++; System.out.println("输出第"+num+"个可行解棋盘"); for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { System.out.print(chess[i][j]+" "); } System.out.println(); } return; } //创建一个临时的chess来保存数据 int[][] chessTemp=chess.clone(); /*向这一行 row(形参)的每一个位置都尝试放一次皇后 * 然后检测状态,安全就继续摆放下一个皇后 */ for(int i=0;i<N;i++) { //清除之前的摆放记录 for(int j=0;j<N;j++){ chessTemp[row][j]=0; } chessTemp[row][i]=1; if(isSafe(chessTemp,row,i)) { putQueenAtRow(chessTemp,row+1); } } } private static boolean isSafe(int[][] chessTemp,int row,int col) { int step=1; //因为第一排,即最上面这一排没有更上一层 //所以不考虑其row-step(step=1)的时候 while(row-step>=0) { //考虑数值方向上的情况 if(chessTemp[row-step][col]==1) return false; //考虑从左上到右下的对角线情况 if(col-step>=0&&chessTemp[row-step][col-step]==1) return false; //考虑从左下到右上的对角线情况 if(col+step<N&&chessTemp[row-step][col+step]==1) return false; step++; } return true; } } 最后面留下大神的blog: http://www.cnblogs.com/newflydd/tag/8皇后/
写的非常好 膜拜
