Backtracking & Maximum Flow Networks

function BACKTRACK(state):
    if IS_SOLUTION(state):
        PROCESS_SOLUTION(state)
        return

    for each choice in GET_CHOICES(state):
        if IS_PROMISING(state, choice):
            MAKE_CHOICE(state, choice)
            BACKTRACK(state)        // Recurse
            UNDO_CHOICE(state, choice)  // Backtrack

function IS_PROMISING(k, col[], j):
    for i = 1 to k-1:
        // Check column conflict
        if col[i] == j:
            return false

        // Check diagonal conflict
        // |row difference| == |column difference| means same diagonal
        if |i - k| == |col[i] - j|:
            return false

    return true

function N_QUEENS(k, n, col[]):
    // k = current row, n = board size, col[i] = column of queen in row i

    if k > n:
        // All queens placed successfully
        PRINT_SOLUTION(col)
        return

    for j = 1 to n:
        if IS_PROMISING(k, col, j):
            col[k] = j          // Place queen in row k, column j
            N_QUEENS(k+1, n, col)  // Try to place in next row
            // Backtracking happens automatically on return

function SUM_OF_SUBSETS(i, weight, total):
    // i = current index, weight = current sum, total = sum of remaining elements
    // Global: W[] = weights, n = size, M = target sum, x[] = solution vector

    if IS_PROMISING(i, weight, total):
        if weight == M:
            PRINT_SOLUTION(x)
        else:
            // Include W[i+1]
            x[i+1] = 1
            SUM_OF_SUBSETS(i+1, weight + W[i+1], total - W[i+1])

            // Exclude W[i+1]
            x[i+1] = 0
            SUM_OF_SUBSETS(i+1, weight, total - W[i+1])

function IS_PROMISING(i, weight, total):
    return (weight + total >= M) AND
           (weight == M OR weight + W[i+1] <= M)

function M_COLORING(k, color[], n, m, graph):
    // k = current vertex, m = number of colors available
    // color[i] = color assigned to vertex i

    if k > n:
        PRINT_SOLUTION(color)
        return true

    for c = 1 to m:
        if IS_SAFE(k, c, color, graph):
            color[k] = c
            if M_COLORING(k+1, color, n, m, graph):
                return true
            color[k] = 0  // Backtrack

    return false

function IS_SAFE(k, c, color[], graph):
    for each neighbor v of k:
        if color[v] == c:
            return false
    return true

function HAMILTONIAN_CYCLE(k, path[], visited[], n, graph):
    if k == n:
        // Check if last vertex connects back to first
        if graph[path[k-1]][path[0]] == 1:
            PRINT_CYCLE(path)
            return true
        return false

    for v = 1 to n:
        if IS_SAFE(v, k, path, visited, graph):
            path[k] = v
            visited[v] = true

            if HAMILTONIAN_CYCLE(k+1, path, visited, n, graph):
                return true

            // Backtrack
            visited[v] = false

    return false

function IS_SAFE(v, k, path[], visited[], graph):
    // Check if v is adjacent to previous vertex
    if graph[path[k-1]][v] == 0:
        return false

    // Check if v is already visited
    if visited[v]:
        return false

    return true

function FORD_FULKERSON(G, s, t):
    Initialize flow f to 0 for all edges
    max_flow = 0

    while EXISTS_PATH(s, t) in residual network Gf:
        // Find augmenting path using BFS/DFS
        path = FIND_AUGMENTING_PATH(Gf, s, t)

        // Find bottleneck (minimum residual capacity on path)
        bottleneck = MIN(cf(u,v) for all (u,v) in path)

        // Augment flow along path
        for each edge (u,v) in path:
            if (u,v) is forward edge:
                f(u,v) += bottleneck
            else:  // backward edge
                f(v,u) -= bottleneck

        max_flow += bottleneck

    return max_flow