N-Queens

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> out;
        vector<int> placement(n, 0);
        function<void(int,int,int,int)> dfs = [&](int row, int cols, int diag, int anti) {
            if (row == n) {
                vector<string> board(n, string(n, '.'));
                for (int r = 0; r < n; ++r) board[r][placement[r]] = 'Q';
                out.push_back(board);
                return;
            }
            int avail = ~(cols | diag | anti) & ((1 << n) - 1);
            while (avail) {
                int bit = avail & -avail;
                avail ^= bit;
                placement[row] = __builtin_ctz(bit);
                dfs(row + 1, cols | bit, (diag | bit) << 1, (anti | bit) >> 1);
            }
        };
        dfs(0, 0, 0, 0);
        return out;
    }
};

import "math/bits"

func solveNQueens(n int) [][]string {
    var out [][]string
    placement := make([]int, n)
    var dfs func(row, cols, diag, anti int)
    dfs = func(row, cols, diag, anti int) {
        if row == n {
            board := make([]string, n)
            for r := 0; r < n; r++ {
                row := make([]byte, n)
                for c := range row {
                    row[c] = '.'
                }
                row[placement[r]] = 'Q'
                board[r] = string(row)
            }
            out = append(out, board)
            return
        }
        avail := ^(cols | diag | anti) & ((1 << n) - 1)
        for avail != 0 {
            bit := avail & -avail
            avail ^= bit
            placement[row] = bits.TrailingZeros(uint(bit))
            dfs(row+1, cols|bit, (diag|bit)<<1, (anti|bit)>>1)
        }
    }
    dfs(0, 0, 0, 0)
    return out
}

from typing import List

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        out: List[List[str]] = []
        placement = [0] * n
        full = (1 << n) - 1

        def dfs(row: int, cols: int, diag: int, anti: int) -> None:
            if row == n:
                board = []
                for r in range(n):
                    line = ['.'] * n
                    line[placement[r]] = 'Q'
                    board.append("".join(line))
                out.append(board)
                return
            avail = ~(cols | diag | anti) & full
            while avail:
                bit = avail & -avail
                avail ^= bit
                placement[row] = (bit).bit_length() - 1
                dfs(row + 1, cols | bit, ((diag | bit) << 1) & full, (anti | bit) >> 1)

        dfs(0, 0, 0, 0)
        return out

function solveNQueens(n) {
    const out = [];
    const placement = new Array(n).fill(0);
    const full = (1 << n) - 1;
    const dfs = (row, cols, diag, anti) => {
        if (row === n) {
            const board = [];
            for (let r = 0; r < n; r++) {
                const line = new Array(n).fill('.');
                line[placement[r]] = 'Q';
                board.push(line.join(''));
            }
            out.push(board);
            return;
        }
        let avail = ~(cols | diag | anti) & full;
        while (avail) {
            const bit = avail & -avail;
            avail ^= bit;
            placement[row] = 31 - Math.clz32(bit);
            dfs(row + 1, cols | bit, ((diag | bit) << 1) & full, (anti | bit) >> 1);
        }
    };
    dfs(0, 0, 0, 0);
    return out;
}

class Solution {
    private List<List<String>> out;
    private int[] placement;
    private int n;
    private int full;

    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        this.full = (1 << n) - 1;
        this.out = new ArrayList<>();
        this.placement = new int[n];
        dfs(0, 0, 0, 0);
        return out;
    }

    private void dfs(int row, int cols, int diag, int anti) {
        if (row == n) {
            List<String> board = new ArrayList<>(n);
            for (int r = 0; r < n; r++) {
                char[] line = new char[n];
                Arrays.fill(line, '.');
                line[placement[r]] = 'Q';
                board.add(new String(line));
            }
            out.add(board);
            return;
        }
        int avail = ~(cols | diag | anti) & full;
        while (avail != 0) {
            int bit = avail & -avail;
            avail ^= bit;
            placement[row] = Integer.numberOfTrailingZeros(bit);
            dfs(row + 1, cols | bit, ((diag | bit) << 1) & full, (anti | bit) >> 1);
        }
    }
}

function solveNQueens(n: number): string[][] {
    const out: string[][] = [];
    const placement: number[] = new Array(n).fill(0);
    const full = (1 << n) - 1;
    const dfs = (row: number, cols: number, diag: number, anti: number): void => {
        if (row === n) {
            const board: string[] = [];
            for (let r = 0; r < n; r++) {
                const line = new Array<string>(n).fill('.');
                line[placement[r]] = 'Q';
                board.push(line.join(''));
            }
            out.push(board);
            return;
        }
        let avail = ~(cols | diag | anti) & full;
        while (avail) {
            const bit = avail & -avail;
            avail ^= bit;
            placement[row] = 31 - Math.clz32(bit);
            dfs(row + 1, cols | bit, ((diag | bit) << 1) & full, (anti | bit) >> 1);
        }
    };
    dfs(0, 0, 0, 0);
    return out;
}