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

L'algoritme de backtracking és una tècnica poderosa per resoldre problemes combinatoris i de recerca exhaustiva. S'utilitza per explorar totes les possibles solucions d'un problema de manera sistemàtica, descartant aquelles que no compleixen certes condicions. En aquest manual, et proporcionarem una comprensió bàsica de en què consisteix l'algoritme de backtracking i com aplicar-lo en 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, realitzant proves i retrocedint (backtracking) quan es troba una solució invàlida. És especialment útil per a problemes on és necessari 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 recerca, cosa que determina com es ramificarà l'arbre de recerca.

2. Exploració: S'exploren 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 realitza el retrocess (backtrack).

4. Retrocess (Backtrack): Si l'elecció actual no porta a una solució vàlida, es torna a un estat anterior i es realitza una nova elecció.

3. Aplicació en C++

Per aplicar l'algoritme de backtracking en 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 el retrocess quan sigui necessari.

Classe Solució

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

Classe Candidats

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

Exemple: Problema de les N Regines

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

#include <iostream>
#include <vector>

using namespace std;

class Solucio {
public:
    Solucio(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 Candidats {
public:
    Candidats(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(Solucio& solucion, int fila) {
        if (fila == N) {
            return true;  // Totes les regines estan col·locades
        }

        Candidats 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;  // Retrocedir si no es troba solució
            }
        }

        return false;  // No s'ha trobat una posició segura per col·locar la regina en aquesta fila
    }

private:
    bool esSeguro(const Solucio& 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 << "Introduïu la mida del taulell (N): ";
    cin >> N;

    Solucio solucion(N);
    Solucionador solucionador(N);

    if (solucionador.resolverNReinas(solucion, 0)) {
        cout << "Solució trobada:" << endl;
        solucion.imprimir();
    } else {
        cout << "No s'ha trobat solució per a N = " << N << endl;
    }

    return 0;
}

Si executem el programa indicant que el taulell és de 8X8, hauria de sortir que les regines han estat col·locades de la següent forma: