回朔法--解决N后问题

引言：下午复习算法时，越看越没有信心，尤其是在看到比较抽象的舍伍德算法。感觉看了半天都还没有弄明白该算法的意义在哪？更别谈怎么用，都准备放弃了，想象放弃等于今天下午又什么事都没有做，于是将舍伍德算法先放下，继续后面的复习，看到拉斯维加斯和回朔法一起求解N后问题；开始提及该算法时，真的是挺恐惧的，但真正自己讲代码敲下来之后，瞬间思路清晰了许多；下面将具体的求解过程做如下笔记，方便以后复习：
一：问题描述：

二：解决办法：
直接上代码：

package Nquene;

/**
 * 使用回朔法求解N后问题
 * @author 陈鹏
 *
 */
public class huishuo {
    private static int[][] cheese;
    private static final int N = 8;
    public static int count = 0;
    /**
     * 初始化棋盘
     */
    public huishuo(){
        cheese = new int[N][N];
        for(int i =0 ;i<N;i++){
            for(int j = 0;j<N;j++){
                cheese[i][j] = 0;
            }
        }
    }
    public static void putQueenAtRow(int row,int[][] cheese){
        /**
         * 递归终止条件
         * 如果N等于8
         * 表示已经找到了合适的棋盘位置 
         */
        if(N==row){
            count++;
            System.out.println("找到"+count+"合适的解了");
            
            for(int i =0 ;i<N;i++){
                for(int j = 0;j<N;j++){
                    System.out.print(cheese[i][j]+"  ");
                }
                System.out.println();
            }
            return;
        }
        //临时数组:clone只是在克隆引用；
        int[][] temp = cheese.clone();
        for(int i=0;i<N;i++){
            //安全起见：每次放置第N行数据之前先将该行数据清空；
            for(int j=0;j<N;j++){
                temp[row][j] = 0;
            }
            temp[row][i] = 1;
            if(isSafety(temp,row,i)){
                putQueenAtRow(row+1,temp);
            }
        }
        
    }
    /**
     * 判断我们将要放置皇后的位置是否安全；
     * @param arr 临时棋盘
     * @param row 行数
     * @param col 列数
     * @return
     */
    public static boolean isSafety(int[][] arr,int row,int col){
        //初始步伐为1；
        int step = 1;
        //终止条件为判断到第一行时
        while(row-step>=0){
            //判断直上方
            if(arr[row-step][col]==1){
                return false;
            }
            //判断左上方:注意等号：=表示相邻
            if(col-step>=0 && arr[row-step][col-step]==1){
                return false;
            }
            //判断右上方：注意不要等号；
            if(col+step<N && arr[row-step][col+step]==1){
                return false;
            }
            step++;
        }
        
        return true;
    }
    public static void main(String[] args) {
        huishuo temp = new huishuo();
        huishuo.putQueenAtRow(0,cheese);
    }
}