---
title: "Backtracking em Zig — Implementação e Explicação"
url: "https://ziglang.com.br/algoritmos/backtracking-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/"
markdown_url: "https://ziglang.com.br/algoritmos/backtracking-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD"
description: "Aprenda a técnica de Backtracking implementada em Zig. N-Rainhas, Sudoku, permutações e subconjuntos com código funcional."
date: "2026-02-21"
author: "Zig Brasil"
---

# Backtracking em Zig — Implementação e Explicação

Aprenda a técnica de Backtracking implementada em Zig. N-Rainhas, Sudoku, permutações e subconjuntos com código funcional.


# Backtracking em Zig — Implementação e Explicação

**Backtracking** é uma técnica algorítmica que explora soluções incrementalmente, abandonando candidatos ("backtracks") assim que determina que não podem levar a uma solução válida. É essencialmente uma busca em profundidade com poda.

## Como Funciona

1. **Escolha**: faça uma escolha entre as opções disponíveis
2. **Restrição**: verifique se a escolha é válida
3. **Objetivo**: verifique se chegou a uma solução completa
4. **Retrocesso**: se a escolha não leva a solução, desfaça e tente outra

### Visualização — N-Rainhas (N=4)

```
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  .
```

## Implementação em Zig

```zig
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 });
    }
}
```

## Análise de Complexidade

| Problema | Tempo | Espaço |
|----------|-------|--------|
| **N-Rainhas** | O(n!) | O(n) |
| **Permutações** | O(n!) | O(n!) |
| **Subconjuntos** | O(2^n) | O(2^n) |
| **Sudoku** | O(9^m) onde m = células vazias | O(m) |

## Quando Usar

- Problemas de **busca combinatória** (permutações, combinações)
- Problemas de **satisfação de restrições** (Sudoku, N-Rainhas)
- Quando é possível **podar** ramos da árvore de busca
- Quando a solução pode ser construída **incrementalmente**

## Recursos Relacionados

- [DFS — Busca em Profundidade](/algoritmos/dfs-busca-profundidade/) — Backtracking é baseado em DFS
- [BFS — Busca em Largura](/algoritmos/bfs-busca-largura/) — Alternativa para busca em grafos
- [Knapsack (Mochila)](/algoritmos/knapsack-mochila/) — Abordagem DP vs backtracking
- [Topological Sort](/algoritmos/topological-sort/) — Ordenação topológica com DFS