אלגוריתמי נסיגה - חיפוש שיטתי של כל האפשרויות

Backtracking היא טכניקה לחיפוש שיטתי של כל הפתרונות האפשריים על ידי בניית פתרון מדורגת. כשמגיעים למבוי סתום (מגלים שהנתיב הנוכחי לא יכול להוביל לפתרון), חוזרים אחורה ומנסים אפשרות אחרת.

הרעיון המרכזי - עץ חיפוש

ניתן לדמיין את Backtracking כ-DFS על 'עץ ההחלטות': כל צומת מייצג מצב חלקי, כל ענף מייצג בחירה, ועלים הם פתרונות מלאים (או מבויי-סתום). Backtracking גוזם ענפים שאינם יכולים להוביל לפתרון (Pruning).

תבנית קוד כללית

function backtrack(state, choices) {
  if (isSolution(state)) {
    saveSolution(state);
    return;
  }
  for (const choice of choices) {
    if (isValid(state, choice)) {
      makeChoice(state, choice);      // בחר
      backtrack(state, nextChoices(state));  // חקור
      undoChoice(state, choice);     // בטל (backtrack)
    }
  }
}

דוגמה - בעיית N-Queens

בעיית N-Queens דורשת להניח N מלכות על לוח N×N כך שאף מלכה לא תוקפת אחרת. Backtracking מניח מלכה בכל שורה, בודק אם יש התנגשות, ואם כן - חוזר ומנסה עמודה אחרת.

function solveNQueens(n) {
  const result = [];
  const cols = new Set(), diag1 = new Set(), diag2 = new Set();

  function place(row, board) {
    if (row === n) { result.push([...board]); return; }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
      cols.add(col); diag1.add(row - col); diag2.add(row + col);
      board.push(col);
      place(row + 1, board);           // חקור
      board.pop();                      // בטל
      cols.delete(col); diag1.delete(row - col); diag2.delete(row + col);
    }
  }
  place(0, []);
  return result;
}

Pruning - הגזם שחוסך זמן

הכוח של Backtracking בא מה-Pruning: אם אנחנו יכולים לדעת מוקדם שענף לא יכול להוביל לפתרון, אנחנו גוזמים אותו לחלוטין ולא בודקים את כל צאצאיו. זה ההבדל בין Backtracking נאיבי לבין מימוש יעיל.

דוגמאות קלאסיות

• N-Queens - הנחת מלכות על לוח שחמט
• Sudoku Solver - מילוי לוח סודוקו
• Subset Sum - מציאת תת-קבוצה עם סכום נתון
• Permutations / Combinations - יצירת כל התמורות/צירופים
• Graph Coloring - צביעת גרף במינימום צבעים
• Maze Solving - מציאת מסלול במבוך