Backtracking en Java: algoritmos de vuelta atrás con ejemplos

                    [Inicio: necesito leche]
                     /                    \
            [Tienda esquina]         [Supermercado]
                  |                    /          \
           [¡Cerrado! ✗]      [Refrigerador]   [Pasillo alimentación]
            ← BACKTRACK            |                    |
                            [No hay leche ✗]    [¡Leche encontrada! ✓]
                             ← BACKTRACK             SOLUCIÓN

Recorrido: Tienda → ✗ → Backtrack → Supermercado → Refrigerador → ✗ →
           Backtrack → Pasillo → ✓ ¡Solución!

/**
 * Plantilla genérica de backtracking.
 * @param solucion  la solución parcial que se está construyendo
 * @param paso      el nivel de decisión actual (profundidad en el árbol)
 */
public void backtrack(Solucion solucion, int paso) {

    // 1. ¿Es una solución completa?
    if (esCompleta(solucion)) {
        procesarSolucion(solucion);  // Imprimir, guardar, etc.
        return;
    }

    // 2. Generar candidatos para el paso actual
    List<Opcion> candidatos = generarCandidatos(solucion, paso);

    // 3. Probar cada candidato
    for (Opcion candidato : candidatos) {

        // 4. ¿El candidato es válido? (PODA)
        if (esValido(solucion, candidato)) {

            // 5. ELEGIR: añadir el candidato a la solución
            solucion.agregar(candidato);

            // 6. EXPLORAR: avanzar al siguiente paso
            backtrack(solucion, paso + 1);

            // 7. DESHACER (backtrack): quitar el candidato
            solucion.quitar(candidato);
        }
    }
}

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

public class Permutaciones {

    private final List<List<Integer>> resultados = new ArrayList<>();

    public List<List<Integer>> permutar(int[] nums) {
        List<Integer> actual = new ArrayList<>();
        boolean[] usado = new boolean[nums.length];
        backtrack(nums, actual, usado);
        return resultados;
    }

    private void backtrack(int[] nums, List<Integer> actual, boolean[] usado) {
        // Solución completa: tenemos N elementos
        if (actual.size() == nums.length) {
            resultados.add(new ArrayList<>(actual)); // Copiar (¡importante!)
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (usado[i]) continue; // Poda: ya está en la permutación actual

            // ELEGIR
            actual.add(nums[i]);
            usado[i] = true;

            // EXPLORAR
            backtrack(nums, actual, usado);

            // DESHACER
            actual.remove(actual.size() - 1);
            usado[i] = false;
        }
    }

    public static void main(String[] args) {
        Permutaciones p = new Permutaciones();
        List<List<Integer>> resultado = p.permutar(new int[]{1, 2, 3});
        System.out.println("Permutaciones de {1, 2, 3}:");
        for (List<Integer> perm : resultado) {
            System.out.println("  " + perm);
        }
        System.out.println("Total: " + resultado.size()); // 6 = 3!
    }
}

Permutaciones de {1, 2, 3}:
  [1, 2, 3]
  [1, 3, 2]
  [2, 1, 3]
  [2, 3, 1]
  [3, 1, 2]
  [3, 2, 1]
Total: 6

public class NReinas {

    private final int n;
    private final int[] columnas; // columnas[fila] = columna de la reina en esa fila
    private int soluciones = 0;

    public NReinas(int n) {
        this.n = n;
        this.columnas = new int[n];
    }

    public void resolver() {
        backtrack(0);
        System.out.println("Total de soluciones para " + n + " reinas: " + soluciones);
    }

    private void backtrack(int fila) {
        // Solución completa: todas las filas tienen reina
        if (fila == n) {
            soluciones++;
            imprimirTablero();
            return;
        }

        // Probar cada columna en esta fila
        for (int col = 0; col < n; col++) {
            if (esSeguro(fila, col)) {
                // ELEGIR: colocar reina
                columnas[fila] = col;

                // EXPLORAR: pasar a la siguiente fila
                backtrack(fila + 1);

                // DESHACER: implícito (se sobrescribe en el siguiente ciclo)
            }
        }
    }

    /**
     * Verifica que la posición (fila, col) no entre en conflicto
     * con ninguna reina ya colocada en filas anteriores.
     */
    private boolean esSeguro(int fila, int col) {
        for (int i = 0; i < fila; i++) {
            // Misma columna
            if (columnas[i] == col) return false;
            // Misma diagonal (la diferencia de filas == diferencia de columnas)
            if (Math.abs(columnas[i] - col) == Math.abs(i - fila)) return false;
        }
        return true;
    }

    private void imprimirTablero() {
        System.out.println("--- Solución " + soluciones + " ---");
        for (int fila = 0; fila < n; fila++) {
            StringBuilder sb = new StringBuilder();
            for (int col = 0; col < n; col++) {
                sb.append(columnas[fila] == col ? " ♛ " : " · ");
            }
            System.out.println(sb);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        new NReinas(8).resolver();
    }
}

--- Solución 1 ---
 ♛  ·  ·  ·  ·  ·  ·  · 
 ·  ·  ·  ·  ♛  ·  ·  · 
 ·  ·  ·  ·  ·  ·  ·  ♛ 
 ·  ·  ·  ·  ·  ♛  ·  · 
 ·  ·  ♛  ·  ·  ·  ·  · 
 ·  ·  ·  ·  ·  ·  ♛  · 
 ·  ♛  ·  ·  ·  ·  ·  · 
 ·  ·  ·  ♛  ·  ·  ·  · 

...
Total de soluciones para 8 reinas: 92

public class SudokuSolver {

    private static final int VACIO = 0;

    public boolean resolver(int[][] tablero) {
        // Buscar la siguiente celda vacía
        for (int fila = 0; fila < 9; fila++) {
            for (int col = 0; col < 9; col++) {
                if (tablero[fila][col] == VACIO) {

                    // Probar dígitos del 1 al 9
                    for (int digito = 1; digito <= 9; digito++) {
                        if (esValido(tablero, fila, col, digito)) {

                            // ELEGIR
                            tablero[fila][col] = digito;

                            // EXPLORAR
                            if (resolver(tablero)) {
                                return true; // ¡Solución encontrada!
                            }

                            // DESHACER
                            tablero[fila][col] = VACIO;
                        }
                    }
                    return false; // Ningún dígito funciona → backtrack
                }
            }
        }
        return true; // No hay celdas vacías → resuelto
    }

    private boolean esValido(int[][] tablero, int fila, int col, int digito) {
        // Verificar fila
        for (int c = 0; c < 9; c++) {
            if (tablero[fila][c] == digito) return false;
        }
        // Verificar columna
        for (int f = 0; f < 9; f++) {
            if (tablero[f][col] == digito) return false;
        }
        // Verificar subcuadro 3x3
        int inicioFila = (fila / 3) * 3;
        int inicioCol  = (col / 3) * 3;
        for (int f = inicioFila; f < inicioFila + 3; f++) {
            for (int c = inicioCol; c < inicioCol + 3; c++) {
                if (tablero[f][c] == digito) return false;
            }
        }
        return true;
    }

    public void imprimir(int[][] tablero) {
        for (int f = 0; f < 9; f++) {
            if (f % 3 == 0 && f != 0) System.out.println("------+-------+------");
            for (int c = 0; c < 9; c++) {
                if (c % 3 == 0 && c != 0) System.out.print("| ");
                System.out.print(tablero[f][c] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] sudoku = {
            {5,3,0, 0,7,0, 0,0,0},
            {6,0,0, 1,9,5, 0,0,0},
            {0,9,8, 0,0,0, 0,6,0},

            {8,0,0, 0,6,0, 0,0,3},
            {4,0,0, 8,0,3, 0,0,1},
            {7,0,0, 0,2,0, 0,0,6},

            {0,6,0, 0,0,0, 2,8,0},
            {0,0,0, 4,1,9, 0,0,5},
            {0,0,0, 0,8,0, 0,7,9}
        };

        SudokuSolver solver = new SudokuSolver();
        System.out.println("Sudoku original:");
        solver.imprimir(sudoku);

        if (solver.resolver(sudoku)) {
            System.out.println("\nSudoku resuelto:");
            solver.imprimir(sudoku);
        } else {
            System.out.println("No tiene solución.");
        }
    }
}

public class Laberinto {

    // Movimientos: arriba, abajo, izquierda, derecha
    private static final int[][] MOVIMIENTOS = {{-1,0},{1,0},{0,-1},{0,1}};
    private static final String[] DIRS = {"↑", "↓", "←", "→"};

    private final int[][] mapa;
    private final int n;
    private final boolean[][] visitado;

    public Laberinto(int[][] mapa) {
        this.mapa = mapa;
        this.n = mapa.length;
        this.visitado = new boolean[n][n];
    }

    public boolean resolver() {
        return backtrack(0, 0);
    }

    private boolean backtrack(int fila, int col) {
        // ¿Hemos llegado a la meta?
        if (fila == n - 1 && col == n - 1) {
            visitado[fila][col] = true;
            return true;
        }

        // ¿Es válida esta posición?
        if (fila < 0 || fila >= n || col < 0 || col >= n) return false;
        if (mapa[fila][col] == 1) return false;  // Pared
        if (visitado[fila][col]) return false;    // Ya visitado

        // ELEGIR: marcar como visitado
        visitado[fila][col] = true;

        // EXPLORAR: probar los 4 movimientos
        for (int[] mov : MOVIMIENTOS) {
            if (backtrack(fila + mov[0], col + mov[1])) {
                return true; // Camino encontrado
            }
        }

        // DESHACER: desmarcar (no forma parte del camino)
        visitado[fila][col] = false;
        return false;
    }

    public void imprimirCamino() {
        for (int f = 0; f < n; f++) {
            for (int c = 0; c < n; c++) {
                if (visitado[f][c])      System.out.print(" ★ ");
                else if (mapa[f][c] == 1) System.out.print(" ▓ ");
                else                      System.out.print(" · ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] mapa = {
            {0, 1, 0, 0, 0},
            {0, 0, 0, 1, 0},
            {1, 1, 0, 1, 0},
            {0, 0, 0, 0, 1},
            {0, 1, 1, 0, 0}
        };

        Laberinto lab = new Laberinto(mapa);
        if (lab.resolver()) {
            System.out.println("¡Camino encontrado!");
            lab.imprimirCamino();
        } else {
            System.out.println("No hay camino posible.");
        }
    }
}

¡Camino encontrado!
 ★  ▓  ·  ·  · 
 ★  ★  ★  ▓  · 
 ▓  ▓  ★  ▓  · 
 ·  ·  ★  ★  ▓ 
 ·  ▓  ▓  ★  ★