回溯——51. N皇后

这一题在我刚开始拿到的时候，是一点思路都没有的，只能先分析题目的要求，即queen之间的规则：

不能同行
不能同列
不能同斜线
- 不能同左斜
- 不能同右斜

同时发现，在寻找所有可能结果的穷举过程中，传入的参数并不需要以整个“棋盘”的形式，只需要传入之前确定的所有queen的位置即可。

这样就可以先写下，在遍历每个潜在的位置合法性的判断函数，同时确定回溯时使用的重要的数据格式：

        //coordinateXY[i]：第i个点的横纵坐标

        //coordinateXY[i][0]——横坐标

        //coordinateXY[i][1]——纵坐标

        int[][] coordinateXY = new int[n][2];

    //x1 y1 是需要判断的是否合法的坐标

    private boolean validXY(int x1, int y1, int[][] coordinateXY) {

        int x2 = -1, y2 = -1;

        for (int i = 0; i < n && coordinateXY[i][1] != -1; ++i) {

            x2 = coordinateXY[i][0];

            y2 = coordinateXY[i][1];

            //        同列 ||            同左斜 || 同右斜

            if ((y1 == y2) || (x1+y1 == x2+y2) || (x1-x2 == y1-y2)) {

                return false;

            }

        }

        return true;

    }

回溯时记录结果的数据格式coordinateXY确定了，自然可以确定最终结果集的构造：

    List<List<String>> result = new ArrayList<>();

    //构造返回值

    private List<String> print(int[][] coordinateXY) {

        List<String> ans = new ArrayList<>();

        StringBuilder sb = null;

        int y = -1;

        for (int[] xy : coordinateXY) {

            sb = new StringBuilder();

            y = xy[1];

            for (int i = 0; i < n; ++i) {

                //三元表达式代替if-else

                sb.append((i == y) ? "Q" : ".");

            }

            ans.add(sb.toString());

        }

        return ans;

    }

最后根据回溯三部曲，确定下回溯函数：

    //x：当前的第x个queen，也是这个queen所在的横坐标的值

    private void function(int x, int[][] coordinateXY) {

        //如果x==n，证明0~n-1个queen都已经确定了坐标，即可记录下此结果

        if (x == n) {

            result.add(print(coordinateXY));

            return ;

        }

        //对于当前这个第x个queen，横坐标coordinateXY[x][0] == x

        //只要从0 ~ n-1寻找合法的y即可

        for (int y = 0; y < n; ++y) {

            if (validXY(x, y, coordinateXY)) {

                //记录下合法的坐标

                coordinateXY[x][1] = y;

                //将第x个queen的纵坐标加入path(coordinateXY)，递归的寻找第x+1个queen的所有合法的纵坐标

                function(x+1, (int[][]) coordinateXY.clone());

                //删除本次记录，继续寻找下一个可能的y

                coordinateXY[x][1] = -1;

            }

        }

    }

这题的关键点主要在：

确定记录结果的数据结构
确定validXY函数
根据queen不能在同一行，确定下回溯是按照行向下遍历的逻辑

巴特西

回溯——51. N皇后

最新文章

热门文章