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

admin管理员组

文章数量:1530987

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

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

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

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

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

 对应的Java代码如下：

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

    //按照题目要求初始化每行
    public List<String> initList(int n)
    {
        List<String> temp = new ArrayList<>();
        for(int j=0;j<n;j++)
        {
            temp.add(".");
        }
        return temp;
    }

    //处理返回结果为题目要求的样式
    public List<String> convertBoard(LinkedList<List<String>> board)
    {
        List<String> res = new ArrayList<>();
        for(int i=0;i<board.size();++i)
        {
            String temp = String.join("",board.get(i));
            res.add(temp);
        }
        return res;
    }

    //回溯方法
    public void backtrack(List<List<String>> res,LinkedList<List<String>> board,int y,int n)
    {
        if(board.size()>=n||y>=n)
        {
            res.add(convertBoard(board));
            return;
        }
        for(int i=0;i<n;++i)
        {
            //假如当前位置不合法，剪枝
            if(!isValid(board,i,y,n))
                continue;
            //当前位置可以放置
            List<String> yList = initList(n);
            yList.set(i,"Q");
            board.add(yList);
            //处理下一行
            backtrack(res,board,y+1,n);
            //取消选择
            board.removeLast();
        }
    }

    public boolean isValid(LinkedList<List<String>> board,int x,int y,int n)
    {
        //检查上方是否有冲突
        for(int i=0;i<y;++i)
        {
            if(board.get(i).get(x).equals("Q"))
                return false;
        }
        //检查右上方是否有冲突
        for(int i=x+1,j=y-1;i<n&&j>=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;
    }

本文标签： 皇后Java