バックトラックで互いに取り合わない n 個のクイーンの置き方を全部集める

def n_queens(n):
    out = []
    cols = []
    used = set()
    up = set()
    down = set()

    def place(r):
        if r == n:
            rows = board(cols)
            out.append(rows)
            return
        for c in range(n):
            u, d = r + c, r - c
            if c in used:
                continue
            if u in up:
                continue
            if d in down:
                continue
            used.add(c)
            up.add(u)
            down.add(d)
            cols.append(c)
            place(r + 1)
            cols.pop()
            used.remove(c)
            up.remove(u)
            down.remove(d)

    place(0)
    return out


def board(cols):
    n = len(cols)
    rows = []
    for c in cols:
        a = ["."] * n
        a[c] = "Q"
        rows.append("".join(a))
    return rows

function nQueens(n) {
  const out = [];
  const cols = [];
  const used = new Set();
  const up = new Set();
  const down = new Set();
  // 0 から n - 1 までの列
  const all = [
    ...Array(n).keys()];
  const place = (r) => {
    if (r === n) {
      out.push(board(cols));
      return;
    }
    for (const c of all) {
      if (used.has(c) ||
        up.has(r + c) ||
        down.has(r - c)) {
        continue;
      }
      used.add(c);
      up.add(r + c);
      down.add(r - c);
      cols.push(c);
      place(r + 1);
      cols.pop();
      used.delete(c);
      up.delete(r + c);
      down.delete(r - c);
    }
  };
  place(0);
  return out;
}

function board(cols) {
  const n = cols.length;
  return cols.map((c) =>
    ".".repeat(c) + "Q" +
    ".".repeat(n - 1 - c));
}

import "strings"

func nQueens(n int) [][]string {
	out := [][]string{}
	cols := []int{}
	used := make([]bool, n)
	up := make([]bool, 2*n)
	down := make([]bool, 2*n)
	var place func(r int)
	place = func(r int) {
		if r == n {
			out = append(out,
				board(cols))
			return
		}
		for c := 0; c < n; c++ {
			// r - c は負になるので
			// n を足して番号にする
			d := r - c + n
			if used[c] || up[r+c] ||
				down[d] {
				continue
			}
			used[c] = true
			up[r+c] = true
			down[d] = true
			cols = append(cols, c)
			place(r + 1)
			cols = cols[:r]
			used[c] = false
			up[r+c] = false
			down[d] = false
		}
	}
	place(0)
	return out
}

func board(
	cols []int,
) []string {
	n := len(cols)
	rows := []string{}
	for _, c := range cols {
		rows = append(rows,
			strings.Repeat(".", c)+
				"Q"+
				strings.Repeat(
					".", n-1-c))
	}
	return rows
}