package thinking;

/*
 * Question : 求解如何在一个N*N的棋盘上放置无冲突的N皇后，无冲突就是指每个皇后的前后左右以及斜向的45°都看不得其他皇后 ，假设N = 4
 * 
 * Thinking : 从第一行的第一个为根节点开始，往下一行放，不满足的就直接放弃，回到根节点，再找其他的子节点，继续，这样的只要不满足就回到相应的父节点继续往下找，知道找到满足的
 *              解就停止，这样的思想就是回溯思想
 * */

public class Queens_backdate {
    // 规定棋盘的大小
    private int chessboard[][]= new int[4][4];
    private int count = 0;
    
    public void initializeChessboard(){
        for(int i = 0; i<4; ++i){
            for(int j = 0; j<4; ++j){
                chessboard[i][j] = 0;
            }
        }
    }
    
    // 对皇后进行上下左右，斜向的判断 有冲突的时候就返回为true，否则就返回为false
    public boolean isConflict(int x,int y){ 
        //boolean flag = false;
        
        // 对皇后的那一列进行判断
        for(int i = 0; i<4; ++i){
            if(i!=x && chessboard[i][y] == 1){
                //System.out.println("第"+x+"行"+"第"+i+"列");
                return true;
                
            }
        }
        // 对皇后的那一行进行判断
        for(int i = 0; i<4; ++i){
            if(i!=y && chessboard[x][i] == 1){
            //System.out.println("第"+i+"行"+"第"+y+"列");
                return true;
            }
        }
        // 对皇后的左斜上45°进行判断
        for(int i = 1; i<4; ++i){
            if((x>=i && y>=i) && chessboard[x-i][y-i] == 1){
                return true;
            }
        }
        // 对皇后的右斜上45°进行判断
        for(int i=1; i<4; ++i){
            if((x-i>=0) && (y+i<4) && chessboard[x-i][y+i] == 1){
                return true;
            }
        }
        // 对皇后左斜下45°进行判断
        for(int i=1; i<4; ++i){
            if((x+i<4) && (y-i>=0) && chessboard[x+i][y-i] == 1){
                return true;
            }
        }
        // 对皇后右斜下45°进行判断
        for(int i=1; i<4; ++i){
            if((x+i<4) && (y+i<4) && chessboard[x+i][y+i] == 1){
                return true;
            }
        }
        return false;
    }
    
    // 是否可以放置皇后
    public void setQueens(int i){  // 用行来形成解树
        if(i == 4){ // 判断是否已经是走到全部可以有解的状态了，那就是找到一个解，可以return了
            for(int x = 0; x < 4; ++x){
                for(int y = 0; y<4; ++y){
                    System.out.print(chessboard[x][y]);
                }
                System.out.println();
            }
            count++;
            System.out.println();
            return;
        }
        
        for(int j=0; j<4; ++j){    
            if(isConflict(i, j) == false){ // 不冲突就是可以放置皇后
                chessboard[i][j] = 1;
                setQueens(i+1);  // 递归深度优先的遍历子解树
                chessboard[i][j] = 0; // 能走出来到这一步的都是上一步走完了，也就是说，上一步都没有可以满足条件的，那么就需要剪枝了
            }

        }
    }
    
    public static void main(String[] args) {
        Queens_backdate queens = new Queens_backdate();
        queens.initializeChessboard();
        queens.setQueens(0);
        System.out.println("count : "+queens.count);
    }
}