बैकट्रैकिंग का परिचय

बैकट्रैकिंग क्या है?

बैकट्रैकिंग एक एल्गोरिदमिक तकनीक है जो समस्या को चरण-दर-चरण हल करती है, आंशिक समाधान बनाती है और उन्हें बाधाओं (constraints) के विरुद्ध जांचती है। यदि कोई आंशिक समाधान मान्य समाधान की ओर नहीं ले जाता, तो यह वापस (backtrack) जाता है और अन्य विकल्प आजमाता है।

समस्या प्रकार

• निर्णय समस्या: एक व्यवहार्य समाधान खोजें
• अनुकूलन समस्या: सर्वोत्तम समाधान खोजें
• गणना समस्या: सभी व्यवहार्य समाधान खोजें

सामान्य एल्गोरिदम

Backtrack(state):
    if state is goal:
        return success
    if state is dead end:
        return failure
    
    for each choice from state:
        make choice
        if Backtrack(new_state) == success:
            return success
        undo choice  // बैकट्रैक
    
    return failure

उदाहरण: N-क्वीन समस्या

समस्या: N×N शतरंज बोर्ड पर N रानियां रखें ताकि कोई भी दो रानी एक-दूसरे पर हमला न कर सकें।

4-क्वीन समाधान:

{0, 1, 0, 0}
{0, 0, 0, 1}
{1, 0, 0, 0}
{0, 0, 1, 0}

N-क्वीन के लिए बैकट्रैकिंग एल्गोरिदम

1. पहली पंक्ति में पहली स्थिति से शुरू करें
2. पंक्ति में रानी रखें और जांचें
3. यदि सुरक्षित है: स्थिति को समाधान के भाग के रूप में चिह्नित करें, अगली पंक्ति के लिए रिकर्सिवली जांचें
4. यदि कोई समाधान नहीं मिलता: बैकट्रैक करें (रानी हटाएं), अगली स्थिति आजमाएं
5. यदि सभी पंक्तियां आजमा लीं और कोई समाधान नहीं: FALSE लौटाएं

उदाहरण: चूहे की भूलभुलैया (Rat in a Maze)

समस्या: N×N भूलभुलैया में [0][0] से [N-1][N-1] तक पथ खोजें। 1 = खुला पथ, 0 = अवरुद्ध।

भूलभुलैया:
1 0 0 0
1 1 0 1
0 1 0 0
1 1 1 1

हल पथ (1 = पथ):
1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1

बैकट्रैकिंग के क्लासिक उदाहरण

बैकट्रैकिंग बनाम ब्रूट फोर्स

• ब्रूट फोर्स: सभी संभावनाएं आजमाता है, कोई छंटाई नहीं
• बैकट्रैकिंग: बाधाओं का उपयोग करके अवैध पथों को जल्दी छांटता है
• दक्षता: बैकट्रैकिंग विशाल खोज स्थान को नाटकीय रूप से कम कर सकता है

C में टेम्पलेट

bool solve(int pos) {
    if (pos == N) return true;  // आधार मामला
    
    for (int choice = 0; choice < options; choice++) {
        if (is_valid(pos, choice)) {
            make_choice(pos, choice);
            if (solve(pos + 1)) return true;
            undo_choice(pos, choice);  // बैकट्रैक
        }
    }
    return false;
}