Menene backtracking?

Question

Accepted Answer

**Backtracking** yana gina sharuruwan da suka kamata kwata-kwata kuma **yan jiya** (sun koma baya) daga wani sharuruwan da ba zai iya haifar da magani mai inganci ba. Yana nazarin sararin mafita a yarda da tsarin DFS, kuma yana sare rassan da suka mutu.

## Tunanin

Zaba -> leekitawa -> bada jiya. Gwada zabin daya, maimaita; idan ya gajiya, bada jiya kuma gwada na gida.

## Misali: dukan permutations

```python
def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:              # complete solution
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])              # choose
            backtrack(path, remaining[:i] + remaining[i+1:])  # explore
            path.pop()                             # un-choose (backtrack)
    backtrack([], nums)
    return result

permutations([1, 2, 3])   # -> 6 permutations
```

## Matsaloli na gida

- **N-queens**, Sudoku, tafiyar na knight.
- **Subsets / haɗa / permutations.**
- **Binciken kalma**, warware maze.

## Haddi

Yawancin lokaci exponential (misali, O(n!) ga permutations), amma **sare** yana karewa binciken aiki sama da yawa.

## Lokacin amfani / mugugunatawa

Ami don matsaloli na imple-satisfy kuma "nemo dukan keɓe masu inganci" matsaloli. Asali babbar nasara ita ce **sare da zarai** — baje rassan da suka karya ƙuduri. Manyan bugi shine mantuwa bada jiya jilar **gora-dabari (bada jiya).

## Why it matters

Backtracking shine waya guda ta nazarin sararin haɗi ba tare da ɗi ko maimaita tayin ba.

Sare masu kyau ya bagi wata aiki ta gargajiya zuwa wani abu da aka gama a lokaci.

Yana ba da karfi wa masu warwarebi da matsaloli na tsarancin kura da ƙuduri a gida ma waje duka.