回溯法解决N皇后问题-java

参照LeetCode第51题的题干，N皇后是指将N个皇后放置在NXN的棋盘上，并且皇后之间不可以互相攻击，即其中任意两个皇后不能在同一行、同一列或者同一条斜线上。

四皇后的放置情况示例如下：

采用回溯法解决该问题时需要将搜索过程抽象成一颗树，只要搜索到达了树的叶子节点，则等于找到了所有皇后合理的放置位置。

其中三皇后问题的解决思路如下，注意三皇后是无解的：

将整个棋盘抽象为坐标轴，按照从上到下的顺序放置皇后，每一行放置一个后即可进行下一行的放置，过程如图：

 对应的Java代码如下：

    //输入棋盘边长n，返回所有合法的放置位置
    public List> solveNQueens(int n)
    {
        //题目要求使用二维字符串数组返回
        List> res = new ArrayList<>();
        linkedList> board = new linkedList<>();
        backtrack(res,board,0,n);
        return res;
    }

    //按照题目要求初始化每行
    public List initList(int n)
    {
        List temp = new ArrayList<>();
        for(int j=0;j convertBoard(linkedList> board)
    {
        List res = new ArrayList<>();
        for(int i=0;i> res,linkedList> board,int y,int n)
    {
        if(board.size()>=n||y>=n)
        {
            res.add(convertBoard(board));
            return;
        }
        for(int i=0;i yList = initList(n);
            yList.set(i,"Q");
            board.add(yList);
            //处理下一行
            backtrack(res,board,y+1,n);
            //取消选择
            board.removeLast();
        }
    }

    public boolean isValid(linkedList> board,int x,int y,int n)
    {
        //检查上方是否有冲突
        for(int i=0;i=0;i++,j--)
        {
            if(board.get(j).get(i).equals("Q"))
                return false;
        }
        //检查左上方是否有冲突
        for(int i=x-1,j=y-1;i>=0&&j>=0;i--,j--)
        {
            if(board.get(j).get(i).equals("Q"))
                return false;
        }
        return true;
    }