Introducció al Backtracking

El backtracking és una tècnica de disseny d'algorismes que es basa en la recursivitat per resoldre problemes de cerca i optimització. Aquesta tècnica explora totes les possibles solucions d'un problema de manera sistemàtica, retrocedint (backtracking) quan es troba amb una solució invàlida o no òptima.

Conceptes Clau

Recursivitat: El backtracking utilitza funcions recursives per explorar les possibles solucions.
Exploració de l'Espai de Solucions: Es tracta d'explorar totes les possibles solucions del problema.
Retrocedir: Quan es troba una solució invàlida, l'algorisme retrocedeix per explorar altres opcions.

Exemples de Problemes Resolts amb Backtracking

Problema de les N reines
Problema del Sudoku
Problema del cavall de l'escacs
Generació de combinacions i permutacions

Funcionament del Backtracking

El backtracking es pot visualitzar com un arbre de decisions on cada node representa una decisió parcial cap a una solució completa. L'algorisme segueix aquests passos:

Explorar: Provar una possible solució.
Validar: Comprovar si la solució parcial és vàlida.
Recursió: Si és vàlida, continuar explorant més en profunditat.
Retrocedir: Si no és vàlida, retrocedir i provar una altra opció.

Pseudocodi del Backtracking

funció backtrack(solució):
    si solució és completa:
        processar(solució)
        retornar
    per a cada opció en opcions disponibles:
        si opció és vàlida:
            afegir opció a solució
            backtrack(solució)
            eliminar opció de solució

Exemple Pràctic: Problema de les N Reines

El problema de les N reines consisteix a col·locar N reines en un tauler de NxN de manera que cap reina pugui atacar una altra.

Implementació en Python

def es_valid(board, row, col):
    # Comprovar la columna
    for i in range(row):
        if board[i][col] == 1:
            return False

    # Comprovar la diagonal superior esquerra
    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
        if board[i][j] == 1:
            return False

    # Comprovar la diagonal superior dreta
    for i, j in zip(range(row, -1, -1), range(col, len(board))):
        if board[i][j] == 1:
            return False

    return True

def col·locar_reines(board, row):
    if row >= len(board):
        return True

    for col in range(len(board)):
        if es_valid(board, row, col):
            board[row][col] = 1
            if col·locar_reines(board, row + 1):
                return True
            board[row][col] = 0

    return False

def imprimir_tauler(board):
    for row in board:
        print(" ".join(str(x) for x in row))

def problema_n_reines(n):
    board = [[0 for _ in range(n)] for _ in range(n)]
    if col·locar_reines(board, 0):
        imprimir_tauler(board)
    else:
        print("No hi ha solució")

# Exemple d'ús
problema_n_reines(4)

Explicació del Codi

Funció es_valid: Comprova si és segur col·locar una reina en una posició determinada.
Funció col·locar_reines: Utilitza la recursivitat per col·locar les reines al tauler.
Funció imprimir_tauler: Imprimeix el tauler amb les reines col·locades.
Funció problema_n_reines: Inicialitza el tauler i crida la funció recursiva per col·locar les reines.

Exercici Pràctic

Problema del Sudoku

Implementa un algorisme de backtracking per resoldre un Sudoku. El Sudoku és un trencaclosques de 9x9 on l'objectiu és omplir la graella de manera que cada fila, cada columna i cada subgraella de 3x3 continguin tots els dígits del 1 al 9.

Pautes

Funció es_valid_sudoku: Comprova si és segur col·locar un número en una posició determinada.
Funció resoldre_sudoku: Utilitza la recursivitat per resoldre el Sudoku.
Funció imprimir_sudoku: Imprimeix el Sudoku resolt.

Solució

def es_valid_sudoku(board, row, col, num):
    # Comprovar la fila
    for i in range(9):
        if board[row][i] == num:
            return False

    # Comprovar la columna
    for i in range(9):
        if board[i][col] == num:
            return False

    # Comprovar la subgraella de 3x3
    start_row, start_col = 3 * (row // 3), 3 * (col // 3)
    for i in range(3):
        for j in range(3):
            if board[start_row + i][start_col + j] == num:
                return False

    return True

def resoldre_sudoku(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1, 10):
                    if es_valid_sudoku(board, row, col, num):
                        board[row][col] = num
                        if resoldre_sudoku(board):
                            return True
                        board[row][col] = 0
                return False
    return True

def imprimir_sudoku(board):
    for row in board:
        print(" ".join(str(x) for x in row))

# Exemple de Sudoku a resoldre
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]
]

if resoldre_sudoku(sudoku):
    imprimir_sudoku(sudoku)
else:
    print("No hi ha solució")

Explicació del Codi

Funció es_valid_sudoku: Comprova si és segur col·locar un número en una posició determinada del Sudoku.
Funció resoldre_sudoku: Utilitza la recursivitat per resoldre el Sudoku.
Funció imprimir_sudoku: Imprimeix el Sudoku resolt.

Resum

El backtracking és una tècnica poderosa per resoldre problemes de cerca i optimització. Mitjançant la recursivitat i la validació de solucions parcials, aquesta tècnica permet explorar totes les possibles solucions d'un problema de manera eficient. Els exemples pràctics com el problema de les N reines i el Sudoku demostren la seva aplicabilitat en una àmplia varietat de problemes.

Backtracking

Introducció al Backtracking

Conceptes Clau

Exemples de Problemes Resolts amb Backtracking

Funcionament del Backtracking

Pseudocodi del Backtracking

Exemple Pràctic: Problema de les N Reines

Implementació en Python

Explicació del Codi

Exercici Pràctic

Problema del Sudoku

Pautes

Solució

Explicació del Codi

Resum

Curs d'Anàlisi i Disseny d'Algorismes

Mòdul 1: Introducció als Algorismes

Mòdul 2: Anàlisi d'Algorismes

Mòdul 3: Estratègies de Disseny d'Algorismes

Mòdul 4: Algorismes Clàssics

Mòdul 5: Optimització d'Algorismes

Mòdul 6: Pràctiques i Exercicis