Backtracking Unveiled: Mastering Depth-First Search and Pruning Techniques

Backtracking is a systematic way to iterate through all possible configurations of a problem. It is often used to solve problems where a sequence of decisions must be made, and each decision leads to a new set of possibilities. Backtracking uses depth-first search (DFS) to explore the state space, and it employs pruning functions to eliminate invalid or suboptimal paths early in the search process.

---

Components of Backtracking Problems

1. Initial State: The starting point of the problem.
2. Target/Goal State: The desired solution.
3. Intermediate States: States generated while moving from the initial state to the target state.
4. Path: The sequence of states from the initial state to the target state.
5. Operators: Rules or actions that transform one state into another.
6. Pruning Function: A heuristic to eliminate invalid or suboptimal states early.

---

Backtracking Algorithm

1. Start with the initial state.
2. Use DFS to explore all possible states.
3. If a state is invalid (based on the pruning function), backtrack and try another path.
4. If a state is the goal state, return the solution.
5. Repeat until all possible states are explored or a solution is found.

---

Example Problems Solved Using Backtracking

1. 3-Digit Lock Problem

• Initial State: "111"
• Target State: The correct combination (e.g., "352")
• Operators: Increment each digit by 1 (from 1 to 9).
• Pruning Function: If a digit is correct (e.g., produces a "click"), fix it and move to the next digit.

Implementation:

function findLockCombination(target) {
    function backtrack(combination, index) {
        if (combination === target) {
            console.log("Found combination:", combination);
            return true;
        }
        if (index >= 3) return false;

        for (let i = 1; i <= 9; i++) {
            const newCombination = combination.slice(0, index) + i + combination.slice(index + 1);
            if (newCombination[index] === target[index]) {
                console.log("Click at position", index + 1, "with digit", i);
                if (backtrack(newCombination, index + 1)) return true;
            }
        }
        return false;
    }

    backtrack("111", 0);
}

const targetCombination = "352";
findLockCombination(targetCombination);

---

2. Monks and Demons Problem

• Initial State: 3 monks, 3 demons, and the boat on the left shore.
• Target State: All monks and demons on the right shore.
• Operators: Move 1 or 2 people in the boat.
• Pruning Function: Ensure that monks are never outnumbered by demons on either shore.

Implementation:

function solveMonksAndDemons() {
    const initialState = { left: { monks: 3, demons: 3 }, right: { monks: 0, demons: 0 }, boat: "left" };
    const visited = new Set();

    function isSafe(state) {
        const { left, right } = state;
        return (
            (left.monks === 0 || left.monks >= left.demons) &&
            (right.monks === 0 || right.monks >= right.demons)
        );
    }

    function backtrack(state, path = []) {
        const key = JSON.stringify(state);
        if (visited.has(key)) return false;
        visited.add(key);

        if (state.left.monks === 0 && state.left.demons === 0) {
            console.log("Solution found:", path);
            return true;
        }

        const { left, right, boat } = state;
        const moves = [
            { monks: 1, demons: 0 },
            { monks: 2, demons: 0 },
            { monks: 0, demons: 1 },
            { monks: 0, demons: 2 },
            { monks: 1, demons: 1 },
        ];

        for (const move of moves) {
            if (
                (boat === "left" && left.monks >= move.monks && left.demons >= move.demons) ||
                (boat === "right" && right.monks >= move.monks && right.demons >= move.demons)
            ) {
                const newLeft = {
                    monks: left.monks - (boat === "left" ? move.monks : -move.monks),
                    demons: left.demons - (boat === "left" ? move.demons : -move.demons),
                };
                const newRight = {
                    monks: right.monks - (boat === "right" ? move.monks : -move.monks),
                    demons: right.demons - (boat === "right" ? move.demons : -move.demons),
                };
                const newState = {
                    left: newLeft,
                    right: newRight,
                    boat: boat === "left" ? "right" : "left",
                };

                if (isSafe(newState) && backtrack(newState, [...path, newState])) {
                    return true;
                }
            }
        }
        return false;
    }

    backtrack(initialState);
}

solveMonksAndDemons();

---

3. Farmer, Goat, Cabbage, and Wolf Problem

• Initial State: Farmer, goat, cabbage, and wolf on the left shore.
• Target State: All on the right shore.
• Operators: Farmer can take one item (goat, cabbage, or wolf) in the boat.
• Pruning Function: Ensure the goat is not left alone with the cabbage, and the wolf is not left alone with the goat.

Implementation:

function solveFarmerProblem() {
  const initialState = {
    left: ["farmer", "goat", "cabbage", "wolf"],
    right: [],
    boat: "left",
  };
  const visited = new Set();

  function isSafe(state) {
    const unsafe = (side) =>
      (side.includes("goat") &&
        side.includes("cabbage") &&
        !side.includes("farmer")) ||
      (side.includes("wolf") &&
        side.includes("goat") &&
        !side.includes("farmer"));

    return !(unsafe(state.left) || unsafe(state.right));
  }

  function stateKey(state) {
    return JSON.stringify(state);
  }

  function backtrack(state, path = []) {
    if (state.left.length === 0) {
      console.log("Solution found:", path);
      return true;
    }

    const key = stateKey(state);
    if (visited.has(key)) return false;
    visited.add(key);

    const { left, right, boat } = state;
    const fromShore = boat === "left" ? left : right;

    // Possible moves: Farmer alone or Farmer + one item
    for (const item of [...fromShore, null]) {
      if (item === null || item !== "farmer") {
        let newLeft = [...left];
        let newRight = [...right];

        if (boat === "left") {
          newLeft = newLeft.filter((x) => x !== "farmer" && x !== item);
          newRight = [...newRight, "farmer"];
          if (item) newRight.push(item);
        } else {
          newRight = newRight.filter((x) => x !== "farmer" && x !== item);
          newLeft = [...newLeft, "farmer"];
          if (item) newLeft.push(item);
        }

        const newState = {
          left: newLeft,
          right: newRight,
          boat: boat === "left" ? "right" : "left",
        };

        if (isSafe(newState) && backtrack(newState, [...path, newState])) {
          return true;
        }
      }
    }

    return false;
  }

  backtrack(initialState);
}

solveFarmerProblem();

---

4. Water Jug Problem

• Initial State: Both jugs are empty.
• Target State: 2 gallons in the 4-gallon jug.
• Operators: Fill, empty, or pour water between jugs.
• Pruning Function: Avoid revisiting states.

Implementation:

function solveWaterJug() {
    const initialState = { jug4: 0, jug3: 0 };
    const target = 2;
    const visited = new Set();

    function backtrack(state, path = []) {
        const key = `${state.jug4},${state.jug3}`;
        if (visited.has(key)) return false;
        visited.add(key);

        if (state.jug4 === target) {
            console.log("Solution found:", path);
            return true;
        }

        const { jug4, jug3 } = state;
        const moves = [
            { jug4: 4, jug3 }, // Fill jug4
            { jug4, jug3: 3 }, // Fill jug3
            { jug4: 0, jug3 }, // Empty jug4
            { jug4, jug3: 0 }, // Empty jug3
            { jug4: Math.max(0, jug4 - (3 - jug3)), jug3: Math.min(3, jug3 + jug4) }, // Pour jug4 to jug3
            { jug4: Math.min(4, jug4 + jug3), jug3: Math.max(0, jug3 - (4 - jug4)) }, // Pour jug3 to jug4
        ];

        for (const move of moves) {
            if (backtrack(move, [...path, move])) {
                return true;
            }
        }
        return false;
    }

    backtrack(initialState);
}

solveWaterJug();

---

Key Points:

1. Backtracking is a systematic way to explore all possible solutions.
2. It uses depth-first search and pruning functions to eliminate invalid paths.
3. It is useful for solving NP-hard problems like puzzles, constraint satisfaction problems, and combinatorial optimization.