सामान्य विचार
बैकट्रैकिंग हल को कदम-दर-कदम बनाती है। हर कदम पर एक विकल्प चुनो, नियम जाँचो, और आगे बढ़ो। नियम टूटे या आगे रास्ता न हो तो पिछला चुनाव वापस लो (undo) और दूसरा आज़माओ।
सारी कोशिशें एक पेड़ बनाती हैं: ऊपर खाली उत्तर, हर स्तर पर एक और चुनाव। बैकट्रैकिंग इस पेड़ में गहराई-पहले (depth first) चलती है। कटी हुई शाखा से बहुत काम बचता है। इसमें रिकर्शन लगता है: हर स्तर एक कॉल है।
solve(k): // खाना k भरो
for each option v:
if v is allowed at slot k:
x[k] = v
if k is the last slot: print x
else solve(k + 1)
// लूप आगे बढ़ना = लौटकर अगला v आज़माना
कार्तीय गुणनफल
समुच्चय A और B का कार्तीय गुणनफल हर जोड़ी (a, b) है। बैकट्रैकिंग: खाना 1 में A का हर मान, और हर के लिए खाना 2 में B का हर मान। हर विकल्प मान्य है, इसलिए कुछ कटता नहीं।
A = {1, 2} और B = {x, y, z} के लिए 2 × 3 = 6 जोड़ियाँ: (1,x) (1,y) (1,z) (2,x) (2,y) (2,z)।
क्रमचय (Permutations)
n वस्तुओं का क्रमचय सभी n वस्तुओं को एक-एक बार, हर संभव क्रम में रखता है। नियम: कोई मान तभी मान्य है जब वह पहले इस्तेमाल न हुआ हो। 3D में यही नियम लाल शाखाएँ काटता है।
कुल n! क्रमचय: 3 वस्तुओं के 3! = 6 (123, 132, 213, 231, 312, 321), 4 के 24।
विन्यास (Arrangements)
n वस्तुओं में से k को एक बार में लेकर विन्यास k अलग वस्तुओं की क्रमबद्ध सूची है। कोड क्रमचय जैसा ही, बस उत्तर n की जगह k खानों के बाद पूरा हो जाता है।
गिनती: A(n, k) = n! / (n − k)!। n = 5, k = 2 के लिए 5 × 4 = 20।
संचय (Combinations)
n वस्तुओं में से k का संचय k वस्तुओं का ऐसा समूह है जिसमें क्रम मायने नहीं रखता। दोहराव से बचने के लिए मान बढ़ते हुए रखो: x[k], x[k − 1] से बड़ा हो। इससे दोहराए क्रम कट जाते हैं।
गिनती: C(n, k) = n! / (k! (n − k)!)। n = 4, k = 2: (1,2) (1,3) (1,4) (2,3) (2,4) (3,4), यानी 6।
उपसमुच्चय (Subsets)
उपसमुच्चय समुच्चय की कोई भी वस्तुएँ चुनता है, शून्य भी हो सकती हैं। बैकट्रैकिंग: हर वस्तु के लिए "लो" या "छोड़ो" तय करो। हर वस्तु के 2 विकल्प हैं, इसलिए n वस्तुओं के 2ⁿ उपसमुच्चय होते हैं। {a, b, c} के 8।
करके देखो
तीन रंगीन पेंसिलें लो और कागज़ पर सारे क्रम लिखो। बैकट्रैकिंग से करो: पहली पेंसिल तय करो, बाकी के क्रम लिखो, फिर लौटकर पहली बदलो। 3D में "अगला कदम" दबाने से पहले अंदाज़ा लगाओ कि अगली चाल रखना है, मना होना है या पीछे लौटना।
मुख्य सूत्र और परिभाषाएँ
- n वस्तुओं के क्रमचय: n!
- विन्यास: A(n, k) = n! / (n − k)!
- संचय: C(n, k) = n! / (k! (n − k)!)
- n वस्तुओं के उपसमुच्चय: 2ⁿ
- आकार p और q के समुच्चयों का कार्तीय गुणनफल: p × q जोड़ियाँ
हल किए गए उदाहरण
1. {1, 2, 3} के सारे क्रमचय उसी क्रम में लिखो जिसमें बैकट्रैकिंग उन्हें पाती है।
1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1। कुल 3! = 6।
2. 4 अलग अंकों के कितने क्रमचय?
4! = 4 × 3 × 2 × 1 = 24।
3. 5 अक्षरों में से 2-2 लेकर कितने विन्यास?
A(5, 2) = 5 × 4 = 20।
4. {1, 2, 3, 4} के 2-2 के सारे संचय लिखो।
मान बढ़ते रखो: (1,2) (1,3) (1,4) (2,3) (2,4) (3,4)। कुल 6 = C(4, 2)।
5. {a, b, c} के सारे उपसमुच्चय लिखो।
हर वस्तु के लिए लो या छोड़ो: {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}। कुल 2³ = 8।
6. {1, 2, 3} के क्रमचय बनाते समय 3D में कुल कितनी बार "मना" होता है?
3D में "अगला कदम" दबाकर गिनो। जड़ से 1 चुनने पर नीचे 5 बार मना होता है (स्तर 2 पर 1 बार, फिर दोनों उप-शाखाओं में 2-2 बार)। तीनों शुरुआती अंकों के लिए 5 × 3 = 15 बार।
आम गलतियाँ
- पीछे लौटते समय चुनाव वापस लेना भूल जाना, जिससे पुराना अंक खाने में रह जाता है।
- गहरे जाने से पहले नियम न जाँचना, जिससे पेड़ बहुत बड़ा हो जाता है।
- विन्यास (क्रम मायने रखता है) और संचय (क्रम मायने नहीं रखता) में गड़बड़ करना।
- आधार स्थिति चूकना: उत्तर तभी छापो जब सारे खाने भर जाएँ।