En què consisteix l'algoritme de Backtracking i com aplicar-lo a C++

L'algoritme de backtracking és una tècnica poderosa per resoldre problemes combinatoris i de cerca exhaustiva. S'utilitza per explorar totes les possibles solucions d'un problema de manera sistemàtica, descartant les que no compleixen certes condicions. En aquest manual, us proporcionarem una comprensió bàsica sobre en què consisteix l'algoritme de backtracking i com aplicar-lo a C++ per resoldre problemes complexos.

1. Conceptes Bàsics de Backtracking

El backtracking és un enfocament recursiu que explora totes les opcions possibles per trobar una solució a un problema. Funciona dividint el problema en subproblemes més petits, fent proves i retrocedint (backtracking) quan es troba una solució invàlida. És especialment útil per a problemes on cal provar moltes combinacions diferents per trobar una solució òptima.

2. Passos Fonamentals del Backtracking

El procés de backtracking consta de diversos passos clau:

1. Elecció: Es pren una decisió en el nivell actual de cerca, cosa que determina com es ramificarà l'arbre de cerca.

2. Exploració: S'explora recursivament les opcions disponibles a partir de l'elecció presa.

3. Validació: Es verifica si l'elecció actual porta a una solució vàlida. Si no és així, es fa el retrocés (backtrack).

4. Retrocés (Backtrack): Si l'elecció actual no porta a una solució vàlida, es reverteix a un estat anterior i es fa una nova elecció.

3.Aplicació a C++

Per aplicar l'algoritme de backtracking a C++, utilitzarem les classes Solucionador, Solució i Candidats.

Classe Solucionador

La classe Solucionador conté la lògica central de l'algoritme de backtracking. Coordina l'exploració de totes les possibles solucions, realitza la validació i la reculada quan sigui necessari.

Classe Solució

La classe Solució s'encarrega d'emmagatzemar l'estat actual de la solució a cada pas del procés de backtracking. Això inclou les decisions preses fins ara i la informació rellevant que defineix la solució en progrés.

Classe Candidats

La classe Candidats s'utilitza per generar les opcions disponibles a cada pas de la cerca. Proporciona una interfície per obtenir les possibles eleccions en funció de l'estat actual de la solució.

Exemple: Problema de les N Reines

Un exemple clàssic d'aplicació de backtracking és el problema de les N Reines, on s'han de col·locar N reines en un tauler d'escacs de manera que no s'ataquin entre ells en cap direcció. Aquí hi ha el codi complet de com es veuria la implementació a C++ utilitzant les classes solucionador, solució i candidats:

#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 executem el programa indicant que el tauler és de 8X8, hauria de sortir-nos que les reines han estat col·locades de la següent forma: