51. N 皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

import java.util.ArrayList;
import java.util.List;

class Solution {

    private static void solve(int LIMIT, List ret, int[] path, int index, int leftLimit, int rightLimit, int rowLimit) {
        if (index == path.length) {
            if (rowLimit == LIMIT) {
                int[] item = new int[path.length];
                System.arraycopy(path, 0, item, 0, path.length);
                ret.add(item);
            }
            return;
        }

        int leave = LIMIT & ~(leftLimit | rightLimit | rowLimit);

        while (leave > 0) {
            int lowbit = leave & -leave;
            path[index] = log2(lowbit);
            solve(LIMIT, ret, path, index + 1, (leftLimit | lowbit) << 1, (rightLimit | lowbit) >> 1, rowLimit | lowbit);

            leave -= lowbit;
        }

    }

    private static int log2(int x) {
        int ret = 0;
        while (x > 1) {
            x >>= 1;
            ret++;
        }
        return ret;
    }

    public static List> solveNQueens(int n) {
        List queens = new ArrayList<>();
        int[] path = new int[n];
        solve((1 << n) - 1, queens, path, 0, 0, 0, 0);
        List> ret = new ArrayList<>();

        for (int[] queen : queens) {
            List item = new ArrayList<>();
            for (int i = 0; i < n; ++i) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < queen[i]; ++j) {
                    sb.append(".");
                }
                sb.append("Q");
                for (int j = queen[i] + 1; j < n; ++j) {
                    sb.append(".");
                }
                item.add(sb.toString());
            }
            ret.add(item);
        }

        return ret;
    }
}