En que consiste el algoritmo de Backtracking y como aplicarlo en C++

El algoritmo de backtracking es una técnica poderosa para resolver problemas combinatorios y de búsqueda exhaustiva. Se utiliza para explorar todas las posibles soluciones de un problema de manera sistemática, descartando aquellas que no cumplen ciertas condiciones. En este manual, te proporcionaremos una comprensión básica de en qué consiste el algoritmo de backtracking y cómo aplicarlo en C++ para resolver problemas complejos.

1. Conceptos Básicos de Backtracking

El backtracking es un enfoque recursivo que explora todas las opciones posibles para encontrar una solución a un problema. Funciona dividiendo el problema en subproblemas más pequeños, realizando pruebas y retrocediendo (backtracking) cuando se encuentra una solución inválida. Es especialmente útil para problemas donde es necesario probar muchas combinaciones diferentes para encontrar una solución óptima.

2. Pasos Fundamentales del Backtracking

El proceso de backtracking consta de varios pasos clave:

1. Elección: Se toma una decisión en el nivel actual de búsqueda, lo que determina cómo se ramificará el árbol de búsqueda.

2. Exploración: Se explora recursivamente las opciones disponibles a partir de la elección tomada.

3. Validación: Se verifica si la elección actual lleva a una solución válida. Si no es así, se realiza el retroceso (backtrack).

4. Retroceso (Backtrack): Si la elección actual no lleva a una solución válida, se revierte a un estado anterior y se realiza una nueva elección.

3. Aplicación en C++

Para aplicar el algoritmo de backtracking en C++, utilizaremos las clases Solucionador, Solución y Candidatos.

Clase Solucionador

La clase Solucionador contiene la lógica central del algoritmo de backtracking. Coordina la exploración de todas las posibles soluciones, realiza la validación y el retroceso cuando sea necesario.

Clase Solución

La clase Solución se encarga de almacenar el estado actual de la solución en cada paso del proceso de backtracking. Esto incluye las decisiones tomadas hasta el momento y la información relevante que define la solución en progreso.

Clase Candidatos

La clase Candidatos se utiliza para generar las opciones disponibles en cada paso de la búsqueda. Proporciona una interfaz para obtener las elecciones posibles en función del estado actual de la solución.

Ejemplo: Problema de las N Reinas

Un ejemplo clásico de aplicación de backtracking es el problema de las N Reinas, donde se deben colocar N reinas en un tablero de ajedrez de tal manera que no se ataquen entre sí en ninguna dirección. Aquí hay el código completo de cómo se vería la implementación en C++ utilizando las clases solucionador, solución y candidatos:

#include <iostream>
#include <vector>

using namespace std;

class Solucion {
public:
    Solucion(int N) : tablero(N, vector<int>(N, 0)), N(N) {}

    void imprimir() const {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                cout << (tablero[i][j] ? "Q" : ".");
            }
            cout << endl;
        }
    }

    vector<vector<int>> tablero;
    int N;
};

class Candidatos {
public:
    Candidatos(int N) : disponibles(N, true) {}

    vector<int> obtener() const {
        vector<int> candidatos;
        for (int i = 0; i < disponibles.size(); ++i) {
            if (disponibles[i]) {
                candidatos.push_back(i);
            }
        }
        return candidatos;
    }

    void marcar(int pos) {
        disponibles[pos] = false;
    }

    void desmarcar(int pos) {
        disponibles[pos] = true;
    }

private:
    vector<bool> disponibles;
};

class Solucionador {
public:
    Solucionador(int N) : N(N) {}

    bool resolverNReinas(Solucion& solucion, int fila) {
        if (fila == N) {
            return true;  // Todas las reinas están colocadas
        }

        Candidatos candidatos(N);
        vector<int> cands = candidatos.obtener();

        for (int columna : cands) {
            if (esSeguro(solucion, fila, columna)) {
                solucion.tablero[fila][columna] = 1;
                candidatos.marcar(columna);

                if (resolverNReinas(solucion, fila + 1)) {
                    return true;
                }

                candidatos.desmarcar(columna);
                solucion.tablero[fila][columna] = 0;  // Retroceder si no se encuentra solución
            }
        }

        return false;  // No se encontró una posición segura para colocar la reina en esta fila
    }

private:
    bool esSeguro(const Solucion& solucion, int fila, int columna) const {
        for (int i = 0; i < fila; ++i) {
            if (solucion.tablero[i][columna] == 1) {
                return false;
            }
        }

        for (int i = fila, j = columna; i >= 0 && j >= 0; --i, --j) {
            if (solucion.tablero[i][j] == 1) {
                return false;
            }
        }

        for (int i = fila, j = columna; i >= 0 && j < N; --i, ++j) {
            if (solucion.tablero[i][j] == 1) {
                return false;
            }
        }

        return true;
    }

    int N;
};

int main() {
    int N;
    cout << "Ingrese el tamaño del tablero (N): ";
    cin >> N;

    Solucion solucion(N);
    Solucionador solucionador(N);

    if (solucionador.resolverNReinas(solucion, 0)) {
        cout << "Solución encontrada:" << endl;
        solucion.imprimir();
    } else {
        cout << "No se encontró solución para N = " << N << endl;
    }

    return 0;
}

Si ejecutamos el programa indicando que el tablero es de 8X8 , debería salirnos que las reinas han sido colocadas de la siguiente forma: