رونمایی از پشت پرده: تسلط بر تکنیک های جستجوی و هرس اول

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);

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();

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();

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();