接上一篇博客：

《》

是使用递归方法实现回溯算法的，在第一次使用二维矩阵的情况下，又做了一次改一维的优化

但是算法效率仍然差强人意，因为使用递归函数的缘故

下面提供另一种回溯算法的实现，使用数据结构”栈“来模拟，递归函数的手工实现，因为我们知道计算机在处理递归时的本质就是栈

时间复杂度是一样的，空间复杂度因为自定义了class，有所上升

经过测试其性能甚至低于上篇博客的递归实现

权当是使用数据结构”栈“，解决15皇后的代码如下：

 

package com.newflypig.eightqueen;import java.util.Date;import java.util.Stack;/** * 使用数据结构“栈”，模拟递归函数 * 实现非递归方案的回溯算法 * @author newflydd@189.cn * Time: 2015年12月31日 下午6:13:05 */public class EightQueen3 {    private static final short N=15;        public static void main(String[] args){        Date begin =new Date();                long count=0;        /**         *  初始化栈和棋盘，并向栈中压入第一张初始化的棋盘         */        Stack
     
       stack=new Stack
      
       ();        short[] chessData=new short[N];        for(short i=1;i
       
        N寻找第一个合法解，如果row达到边界count+1，否则push进栈                 */                Chess chessTemp=chess.clone();                if(chessTemp.moveRow()){                    while(chessTemp.moveCol()){                        if( isSafety(chessTemp) ){                            if( chessTemp.currentRow==N-1 ){                                count++;                                continue;                            }else{                                stack.push(chessTemp);                                continue EMPTY;                            }                        }                    }                }                            }        }        Date end =new Date();        System.out.println("解决 " +N+ "皇后问题，用时：" +String.valueOf(end.getTime()-begin.getTime())+ "毫秒，计算结果："+count);    }    private static boolean isSafety(Chess chess) {        // 判断中上、左上、右上是否安全        short step = 1;        for (short i =  (short) (chess.currentRow - 1); i >= 0; i--) {            if (chess.chess[i] == chess.currentCol) // 中上                return false;            if (chess.chess[i] == chess.currentCol - step) // 左上                return false;            if (chess.chess[i] == chess.currentCol + step) // 右上                return false;            step++;        }        return true;    }}class Chess implements Cloneable{    public short[] chess;        //棋盘数据    public short currentRow=0;    //当前行    public short currentCol=0;        //当前列    public boolean visited=false;    //是否访问过    public Chess(short[] chess){        this.chess=chess;    }    public boolean moveCol(){        this.currentCol++;        if(this.currentCol>=chess.length)            return false;        else{            this.chess[currentRow]=currentCol;            return true;        }    }    public boolean moveRow(){        this.currentRow++;        if(this.currentRow>=chess.length)            return false;        else            return true;    }    public Chess clone() {        short[] chessData=this.chess.clone();        Chess chess=new Chess(chessData);        chess.currentCol=-1;        chess.currentRow=this.currentRow;        chess.visited=false;        return chess;    }}
       
      
     

 

执行结果：

 

 

博主会继续思考其他算法优化方案，直至100秒跑16皇后，OK？