आठ रानियाँ: बैकट्रैकिंग से ८ बिना हमला रानियाँ (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ८.१२: ८×८ बोर्ड पर आठ रानियाँ रखो ताकि कोई पंक्ति, स्तंभ या विकर्ण साझा न हो। पंक्ति-दर-पंक्ति रखना, टकराव जाँच, और साफ जावा बैकट्रैकिंग।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

शतरंज की रानी अपनी पंक्ति, स्तंभ, या दोनों विकर्णों पर किसी भी दूरी तक मारती है। ८×८ बोर्ड पर आठ रानियाँ ऐसी रखो कि कोई किसी को न काट सके। यही क्लासिक आठ रानियाँ पहेली है, और इंटरव्यू में यह दिखाता है कि तुम बैकट्रैकिंग कर सकते हो: एक जगह आज़माओ, और गहराई में जाओ, फँसने पर वापस हटाओ।

यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। रिकर्शन इंटरव्यू सवालों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा।

---

१. रोज़मर्रा की उपमा

आठ मैनेजर सोचो जिन्हें कमरों के ग्रिड में आठ मेज़ों पर बैठना है। हर मैनेजर कहता है:

• मेरी मंज़िल (पंक्ति) पर और कोई नहीं,
• मेरे गलियारे (स्तंभ) में और कोई नहीं,
• मेरी मेज़ काटने वाले किसी विकर्ण गलियारे पर और कोई नहीं।

तुम पंक्ति दर पंक्ति चलते हो (स्तंभ दर स्तंभ भी वही आइडिया)। पंक्ति ० पर हर स्तंभ आज़माते हो। हर कोशिश पर पंक्ति १ जाते हो और हर खाली, गैर-हमला स्तंभ देखते हो। जब किसी पंक्ति में कोई कानूनी स्तंभ न बचे, एक पंक्ति पीछे हटते हो और पुराना चुनाव बदलते हो। आठ पंक्तियाँ भर जाएं तो एक पूरा प्लान मिलता है। सभी वैध प्लान सूचीबद्ध करने के लिए चलते रहते हो।

यह हटाओ-और-फिर-आज़माओ का रास्ता ही बैकट्रैकिंग है। पहले ८! स्तंभ क्रम बनाकर बाद में छानने की ज़रूरत नहीं अगर पहले ही काट सको।

---

२. सादा समस्या कथन

इनपुट: बोर्ड आकार n (क्लासिक केस: n = 8)।

आउटपुट: n × n बोर्ड पर n रानियाँ रखने के हर तरीके जहाँ कोई दो एक-दूसरे पर हमला न करें। हमला मतलब एक ही पंक्ति, स्तंभ, या विकर्ण।

कोड में क्या लौटाएं:

• समाधानों की सूची। हर समाधान पंक्ति अनुसार स्तंभ इंडेक्स का ऐरे हो सकता है, या बोर्ड स्ट्रिंग की सूची (लीटकोड शैली), या प्रिंटेड बोर्ड। एक चुनो और बोलो।
• गिनती फॉलो-अप के लिए अच्छी है (n = 8 पर ९२)।

महत्वपूर्ण नियम:

• रानियाँ पंक्ति, स्तंभ, दोनों विकर्णों पर किसी भी दूरी तक मारती हैं (बीच में रुकावट नहीं)।
• सामान्य ऑप्टिमाइज़ेशन से हर समाधान में हर पंक्ति और हर स्तंभ पर ठीक एक रानी (नीचे देखो)। एक ही पंक्ति में दो कभी नहीं चाहिए।
• n > 0 के लिए खाली बोर्ड समाधान नहीं। सारी n रानियाँ लगानी हैं।

छोटा उदाहरण (n = 4): ठीक २ समाधान (प्रिंट कैसे करो उस पर निर्भर)। एक:

. Q . .
. . . Q
Q . . .
. . Q .

कोई दो रानियाँ पंक्ति, स्तंभ या विकर्ण साझा नहीं करतीं। n = 8 पर ९२ अलग समाधान (बोर्ड सममिति छोड़ो तो १२)।

कोड से पहले साफ करो:

• स्थिर n = 8 या सामान्य n? सामान्य लिखो; डेमो ८ से।
• सारे बोर्ड या सिर्फ गिनती? क्लासिक माँग सारे बोर्ड।
• प्रतिनिधित्व? लॉजिक के लिए int[] columns जहाँ columns[row] = col काफी; सुंदर प्रिंट बाद में।
• पंक्ति-स्तंभ ० से? कोड में हाँ।

---

३. पहले सोचो

ब्रूट फोर्स बहुत बड़ा है

८ वर्ग चुनने के C(64, 8) तरीके, क्रम मायने रखे तो 64 P 8। ज्यादातर अवैध। संरचना चाहिए।

हर पंक्ति में एक रानी (और हर स्तंभ में)

दो रानियाँ एक पंक्ति साझा करें तो हमला। इसलिए समाधान पंक्तियों ० .. n-1 के लिए स्तंभों का क्रमपरिवर्तन है: पंक्ति r में ठीक एक रानी स्तंभ columns[r] पर, और सारे columns[r] अलग।

खोज अधिकतम n! क्रमपरिवर्तन तक गिरती है, विकर्ण फिर भी ज्यादातर काटते हैं।

पंक्ति दर पंक्ति या स्तंभ दर स्तंभ रख सकते हो। यही आइडिया। यह पोस्ट पंक्ति से रखता है: पंक्ति r के लिए हर स्तंभ c आज़माओ।

"हमले में" का मतलब

(row, col) पर रानी रखने पर, पहले की हर रानी (r2, c2) जहाँ r2 < row, हमला न करे:

१. एक स्तंभ: col == c2 २. एक विकर्ण: |col - c2| == |row - r2|
(नीचे और बगल की दूरी बराबर)

एक पंक्ति प्रति रानी रखने पर एक ही पंक्ति नहीं आती।

बैकट्रैकिंग कंकाल

place(row):
  if row == n:
    columns की कॉपी दर्ज करो
    return
  for col in 0 .. n-1:
    if isSafe(row, col):
      columns[row] = col
      place(row + 1)
      // अगली लिखत columns[row] ओवरराइट करे तो अलग अनडू ज़रूरी नहीं

isSafe सिर्फ पंक्तियाँ ० .. row-1 देखता है।

तेज़ सुरक्षा जाँच (वैकल्पिक)

पिछली रानियाँ स्कैन करना हर कोशिश पर O(n)। तीन बूलियन ऐरे से ओ(१) जाँच:

ऐरे	चिह्न	इंडेक्स आइडिया
usedCol[c]	स्तंभ भरा	c
usedDiag1[d]	एक विकर्ण परिवार	row - col + (n - 1)
usedDiag2[d]	दूसरा परिवार	row + col

रखते समय तीन फ्लैग सेट करो, बैकट्रैक पर साफ। वही समाधान; बेहतर कॉन्स्टेंट। इंटरव्यू में दोनों ठीक। सादे स्कैन से शुरू; तेज़ी पूछें तो ऐरे बताओ।

बैकट्रैकिंग क्यों, शुद्ध डीपी नहीं

हर वैध पूरा प्लेसमेंट चाहिए, एक अधिकतम स्कोर नहीं। स्टेट चुनाव पर शाखा बनाते हैं, अवैध आधे बोर्ड जल्दी मरते हैं। यह काट-छाँट वाली खोज है, क्लासिक टेबल डीपी नहीं।

n = 4 के लिए व्हाइटबोर्ड स्केच

१. पंक्ति ०, स्तंभ ० आज़माओ। रखो। २. पंक्ति १: स्तंभ ० बंद (स्तंभ)। स्तंभ १ बंद (विकर्ण)। स्तंभ २ आज़माओ। ३. पंक्ति २: बहुत से वर्ग बंद; शायद गतिरोध। ४. पंक्ति १ अनडू, स्तंभ ३ आज़माओ, आगे। ५. अंत में दोनों पूरे बोर्ड मिलते हैं। गिनती = २।

ज़ोर से यह कहना दिखाता है कि तुम काटो-और-फिर-आज़माओ समझते हो, सिर्फ "किसी तरह रिकर्शन" नहीं।

---

४. जावा समाधान

शिक्षण संस्करण: सामान्य n, हर पंक्ति एक रानी, पिछली रानियों से जाँच, स्तंभ मैप और वैकल्पिक स्ट्रिंग बोर्ड।

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * n-queens via backtracking.
 * columns[row] = column of the queen in that row.
 */
public class EightQueens {
    private final int n;
    private final List<int[]> placements = new ArrayList<>();

    public EightQueens(int n) {
        if (n < 1) {
            throw new IllegalArgumentException("n must be positive");
        }
        this.n = n;
    }

    /** All solutions as column arrays (length n). */
    public List<int[]> solvePlacements() {
        placements.clear();
        int[] columns = new int[n];
        Arrays.fill(columns, -1);
        place(0, columns);
        return new ArrayList<>(placements);
    }

    /** LeetCode-style boards: list of strings with 'Q' and '.'. */
    public List<List<String>> solveBoards() {
        List<List<String>> boards = new ArrayList<>();
        for (int[] cols : solvePlacements()) {
            boards.add(toBoard(cols));
        }
        return boards;
    }

    private void place(int row, int[] columns) {
        if (row == n) {
            placements.add(columns.clone());
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isSafe(columns, row, col)) {
                columns[row] = col;
                place(row + 1, columns);
                // columns[row] will be overwritten on the next try
            }
        }
    }

    /** True if (row, col) does not attack any queen in rows 0 .. row-1. */
    private boolean isSafe(int[] columns, int row, int col) {
        for (int r = 0; r < row; r++) {
            int c = columns[r];
            if (c == col) {
                return false; // same column
            }
            // same diagonal: equal row distance and column distance
            if (Math.abs(c - col) == row - r) {
                return false;
            }
        }
        return true;
    }

    private List<String> toBoard(int[] columns) {
        List<String> board = new ArrayList<>(n);
        for (int r = 0; r < n; r++) {
            char[] line = new char[n];
            Arrays.fill(line, '.');
            line[columns[r]] = 'Q';
            board.add(new String(line));
        }
        return board;
    }

    public static void main(String[] args) {
        EightQueens eq = new EightQueens(8);
        List<int[]> all = eq.solvePlacements();
        System.out.println("solutions for n=8: " + all.size()); // 92

        EightQueens four = new EightQueens(4);
        List<List<String>> boards = four.solveBoards();
        System.out.println("solutions for n=4: " + boards.size()); // 2
        for (List<String> b : boards) {
            for (String row : b) {
                System.out.println(row);
            }
            System.out.println();
        }
    }
}

n = 4 का पहला समाधान स्तंभ क्रम पर निर्भर करता है, पर दोनों वैध बोर्ड आते हैं।

कदम	क्रिया	नोट
शुरू	place(0)	पंक्ति ० पर स्तंभ ०..३
रखो	columns[0] सेट, place(1)	गहरी पंक्ति
अस्वीकार	isSafe गलत	एक स्तंभ या विकर्ण
पूरा स्वीकार	row == n	columns क्लोन करके जोड़ो
जारी	वर्तमान पंक्ति में अगला col	अन्य शाखाएँ
खत्म	लूप खत्म	n=4 → २, n=8 → ९२

ओ(१) फ्लैग वाला वेरिएंट (सिर्फ स्केच):

// usedCol[c], diag1[row - col + n - 1], diag2[row + col]
private void placeFast(int row, int[] columns,
                       boolean[] usedCol, boolean[] d1, boolean[] d2) {
    if (row == n) {
        placements.add(columns.clone());
        return;
    }
    for (int col = 0; col < n; col++) {
        int i1 = row - col + n - 1;
        int i2 = row + col;
        if (usedCol[col] || d1[i1] || d2[i2]) {
            continue;
        }
        usedCol[col] = d1[i1] = d2[i2] = true;
        columns[row] = col;
        placeFast(row + 1, columns, usedCol, d1, d2);
        usedCol[col] = d1[i1] = d2[i2] = false; // backtrack
    }
}

वही निर्णय वृक्ष। फ्लैग से "यह वर्ग खाली है?" नियत समय में।

---

५. जटिलता तालिका

हिस्सा	समय	अतिरिक्त स्थान	नोट
पूरा खोज वृक्ष	ऊपरी सीमा ओ(एन!)	ओ(एन) रिकर्शन + ओ(एन) स्तंभ ऐरे	काट-छाँट ज्यादातर शाखाएँ हटाती है
isSafe स्कैन संस्करण	हर उम्मीदवार पर ओ(एन)	स्तंभ ऐरे के अलावा ओ(१)	कोड और समझ आसान
फ्लैग ऐरे संस्करण	हर उम्मीदवार पर ओ(१)	तीन बूलियन ऐरे पर ओ(एन)	वही बाहरी खोज
आउटपुट आकार	कॉपी पर Θ(एस · एन)	Θ(एस · एन)	एस = समाधान संख्या (n = 8 पर ९२)
व्यवहार में n = 8	छोटा	छोटा	लैपटॉप पर तुरंत खत्म

इंटरव्यूअर देखता है कि तुमने हर पंक्ति एक रानी मजबूर की, स्तंभ और विकर्ण जाँचे, और समाधान दर्ज करते समय बोर्ड क्लोन किया (जीवित म्यूटेबल ऐरे न सहेजा)।

---

६. किनारे के केस और आम गलतियाँ

इंटरव्यूअर ये छूते हैं:

• n = 1: एक समाधान, एक रानी। बिना पूछे अलग केस मत बनाओ।
• n = 2 और n = 3: शून्य समाधान। खाली सूची सही।
• n = 4: ठीक २। अच्छा स्मोक टेस्ट।
• n = 8: ९२ समाधान। और संख्या आए तो विकर्ण जाँच गलत होगी।
• जीवित columns ऐरे बिना clone() परिणाम सूची में। हर एंट्री आखिरी क्रमपरिवर्तन बन जाती है।
• विकर्ण पर निरपेक्ष मान भूलना या सिर्फ एक विकर्ण दिशा देखना।
• एक स्तंभ में दो रानियाँ क्योंकि सिर्फ विकर्ण जाँचे।
• row - col + n - 1 पर ऑफ-बाय-वन (गैर-ऋणात्मक रहना चाहिए)।
• खोज के बाद परिणाम घुमाते हुए बोर्ड बदलना।

आम गलतियाँ:

१. ६४ वर्गों पर मुक्त रखना बिना एक-प्रति-पंक्ति। कोड फूलता है, इंटरव्यूअर उलझता है। २. सिर्फ पड़ोसी वर्ग जाँचना। रानियाँ किसी भी दूरी पर मारती हैं। ३. हर समाधान के लिए वही लिस्ट/ऐरे संदर्भ। ४. फ्लैग ऐरे पर बैकट्रैक न करना। इस्तेमाल-चिह्नित स्तंभ कभी खाली नहीं होता। ५. सममिति गिनती को मुख्य जवाब मानना जब अलग-अलग बोर्ड माँगे हों (९२, १२ नहीं)। ६. सिर्फ सुंदर बोर्ड लौटाना और n = 8 की गिनती साबित न करना।

न्यूनतम स्मोक आइडिया:

assert new EightQueens(1).solvePlacements().size() == 1;
assert new EightQueens(2).solvePlacements().size() == 0;
assert new EightQueens(3).solvePlacements().size() == 0;
assert new EightQueens(4).solvePlacements().size() == 2;
assert new EightQueens(8).solvePlacements().size() == 92;

---

७. दोस्त को समझाने वाला सार

आठ रानियाँ पूछती हैं: शतरंज बोर्ड पर आठ रानियाँ रखो जो एक-दूसरे पर हमला न करें।

१. हर पंक्ति में एक रानी। चुनाव है कौन सा स्तंभ। २. सारे स्तंभ अलग होने चाहिए। विकर्ण एक रेखा पर न आएं (|Δcol| == |Δrow|)। ३. बैकट्रैक: एक स्तंभ आज़माओ, अगली पंक्ति पर रिकर्शन, फँसने या पूरा बोर्ड दर्ज करने के बाद हटाकर अगला आज़माओ। ४. हर पूरे प्लेसमेंट की कॉपी रखो। n = 8 पर ९२ तरीके मिलने चाहिए। ५. वैकल्पिक तेज़ी: भरे स्तंभ और दोनों विकर्ण परिवारों के लिए बूलियन ऐरे, हर कोशिश ओ(१) में जाँच।

n = 4 स्केच कर सको, एक असफल आधा प्लेसमेंट दिखा सको, और समाधान ऐरे क्लोन क्यों ज़रूरी बता सको, तो समस्या ८.१२ तुम्हारी है। यहाँ रिकर्शन "जादुई मेमोइज़ेशन" नहीं। अनुशासित खोज है, अनडू के साथ।

---

सीरीज़

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: सिक्के
• अगला: बक्सों का ढेर