Tentando colocar rainhas em um tabuleiro 4x4:

  Coluna 0: rainha em (0,0)
    Coluna 1: (1,0)✗ (1,1)✗ (1,2)✓
      Coluna 2: todos conflitam ✗ → backtrack!
    Coluna 1: (1,3)✗ → backtrack!

  Coluna 0: rainha em (0,1)
    Coluna 1: (1,3)✓
      Coluna 2: (2,0)✓
        Coluna 3: (3,2)✓ → SOLUÇÃO!

  Solução:      .  Q  .  .
                .  .  .  Q
                Q  .  .  .
                .  .  Q  .

const std = @import("std");
const Allocator = std.mem.Allocator;

// ==================== N-Rainhas ====================

/// Resolve o problema das N-Rainhas.
/// Retorna todas as soluções possíveis.
pub fn nRainhas(allocator: Allocator, n: u8) ![][]u8 {
    var solucoes = std.ArrayList([]u8).init(allocator);
    var tabuleiro = try allocator.alloc(u8, n);
    defer allocator.free(tabuleiro);

    var colunas = try allocator.alloc(bool, n);
    defer allocator.free(colunas);
    @memset(colunas, false);

    var diag1 = try allocator.alloc(bool, 2 * @as(usize, n) - 1);
    defer allocator.free(diag1);
    @memset(diag1, false);

    var diag2 = try allocator.alloc(bool, 2 * @as(usize, n) - 1);
    defer allocator.free(diag2);
    @memset(diag2, false);

    try resolverRainhas(allocator, &solucoes, tabuleiro, colunas, diag1, diag2, 0, n);
    return try solucoes.toOwnedSlice();
}

fn resolverRainhas(
    allocator: Allocator,
    solucoes: *std.ArrayList([]u8),
    tabuleiro: []u8,
    colunas: []bool,
    diag1: []bool,
    diag2: []bool,
    linha: u8,
    n: u8,
) !void {
    if (linha == n) {
        // Solução encontrada — copia
        const copia = try allocator.dupe(u8, tabuleiro);
        try solucoes.append(copia);
        return;
    }

    for (0..n) |col| {
        const d1 = @as(usize, linha) + col;
        const d2 = @as(usize, linha) + n - 1 - col;

        if (!colunas[col] and !diag1[d1] and !diag2[d2]) {
            tabuleiro[linha] = @intCast(col);
            colunas[col] = true;
            diag1[d1] = true;
            diag2[d2] = true;

            try resolverRainhas(allocator, solucoes, tabuleiro, colunas, diag1, diag2, linha + 1, n);

            // Backtrack
            colunas[col] = false;
            diag1[d1] = false;
            diag2[d2] = false;
        }
    }
}

// ==================== Permutações ====================

/// Gera todas as permutações de um array.
pub fn permutacoes(allocator: Allocator, arr: []i32) ![][]i32 {
    var resultado = std.ArrayList([]i32).init(allocator);
    try gerarPermutacoes(allocator, arr, &resultado, 0);
    return try resultado.toOwnedSlice();
}

fn gerarPermutacoes(
    allocator: Allocator,
    arr: []i32,
    resultado: *std.ArrayList([]i32),
    inicio: usize,
) !void {
    if (inicio == arr.len) {
        try resultado.append(try allocator.dupe(i32, arr));
        return;
    }

    for (inicio..arr.len) |i| {
        std.mem.swap(i32, &arr[inicio], &arr[i]);
        try gerarPermutacoes(allocator, arr, resultado, inicio + 1);
        std.mem.swap(i32, &arr[inicio], &arr[i]); // backtrack
    }
}

// ==================== Subconjuntos ====================

/// Gera todos os subconjuntos de um array.
pub fn subconjuntos(allocator: Allocator, arr: []const i32) ![][]i32 {
    var resultado = std.ArrayList([]i32).init(allocator);
    var atual = std.ArrayList(i32).init(allocator);
    defer atual.deinit();

    try gerarSubconjuntos(allocator, arr, &resultado, &atual, 0);
    return try resultado.toOwnedSlice();
}

fn gerarSubconjuntos(
    allocator: Allocator,
    arr: []const i32,
    resultado: *std.ArrayList([]i32),
    atual: *std.ArrayList(i32),
    inicio: usize,
) !void {
    try resultado.append(try allocator.dupe(i32, atual.items));

    for (inicio..arr.len) |i| {
        try atual.append(arr[i]);
        try gerarSubconjuntos(allocator, arr, resultado, atual, i + 1);
        _ = atual.pop(); // backtrack
    }
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    // N-Rainhas
    try stdout.print("=== N-Rainhas (N=4) ===\n", .{});
    const solucoes = try nRainhas(allocator, 4);
    defer {
        for (solucoes) |s| allocator.free(s);
        allocator.free(solucoes);
    }

    try stdout.print("Total de soluções: {d}\n", .{solucoes.len});
    for (solucoes, 0..) |sol, idx| {
        try stdout.print("Solução {d}:\n", .{idx + 1});
        for (0..4) |linha| {
            for (0..4) |col| {
                if (sol[linha] == col) {
                    try stdout.print(" Q", .{});
                } else {
                    try stdout.print(" .", .{});
                }
            }
            try stdout.print("\n", .{});
        }
    }

    // Permutações
    try stdout.print("\n=== Permutações de [1, 2, 3] ===\n", .{});
    var nums = [_]i32{ 1, 2, 3 };
    const perms = try permutacoes(allocator, &nums);
    defer {
        for (perms) |p| allocator.free(p);
        allocator.free(perms);
    }
    for (perms) |p| {
        try stdout.print("[", .{});
        for (p, 0..) |x, i| {
            if (i > 0) try stdout.print(", ", .{});
            try stdout.print("{d}", .{x});
        }
        try stdout.print("]\n", .{});
    }

    // Subconjuntos
    try stdout.print("\n=== Subconjuntos de [1, 2, 3] ===\n", .{});
    const subs = try subconjuntos(allocator, &[_]i32{ 1, 2, 3 });
    defer {
        for (subs) |s| allocator.free(s);
        allocator.free(subs);
    }
    for (subs) |s| {
        try stdout.print("{{", .{});
        for (s, 0..) |x, i| {
            if (i > 0) try stdout.print(", ", .{});
            try stdout.print("{d}", .{x});
        }
        try stdout.print("}}\n", .{});
    }

    // Contagem de soluções N-Rainhas
    try stdout.print("\n=== Contagem N-Rainhas ===\n", .{});
    for ([_]u8{ 4, 5, 6, 7, 8 }) |n| {
        const sols = try nRainhas(allocator, n);
        defer {
            for (sols) |s| allocator.free(s);
            allocator.free(sols);
        }
        try stdout.print("N={d}: {d} soluções\n", .{ n, sols.len });
    }
}