019 — N-Queens¶

Problem link ও উৎস

Original source: Classic constraint backtracking exercise (place N non-attacking queens)
Platform: LeetCode — https://leetcode.com/problems/n-queens/
Topic: recursion / backtracking (constraint backtracking)
Difficulty: Hard
Pattern: constraint backtracking — প্রতি row-এ এক queen, 3টা blocked-line set দিয়ে safe-check
Basic idea inherited from: Permutations + তিনটা blocked-line set

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

একটা n × n দাবার বোর্ডে nটা queen বসাতে হবে এমনভাবে যেন কোনো দুটো queen একে অন্যকে আক্রমণ না করে। দাবায় queen একই row, একই column, আর দুই কোনাকুনি (diagonal) বরাবর আক্রমণ করে। তোমার কাজ: সব রকম বৈধ সাজানো বের করা, প্রতিটা বোর্ড string-এর list হিসেবে — 'Q' মানে queen, '.' মানে খালি।

উদাহরণ

n = 4 -> 2টা বৈধ সাজ:
.Q..        ..Q.
...Q        Q...
Q...        ...Q
..Q.        .Q..

Input ও output¶

উদাহরণ

Input : n=4 -> Output: 2টা বোর্ড (উপরে দেখানো)
Input : n=1 -> Output: [["Q"]]

Edge case 1 (অসম্ভব): n=2 -> Output: []   (কোনো সাজ নেই)
Edge case 2 (অসম্ভব): n=3 -> Output: []

চেনা উদাহরণে বোঝা¶

ভাবো একটা office-এ n জন প্রহরী রাখতে হবে, প্রতিজন একটা করিডোর (row) পাহারা দেয়; কিন্তু কারও line-of-sight (column বা কোনাকুনি) যেন অন্য প্রহরীর ওপর না পড়ে। একটা করিডোরে একজনকে এমন জায়গায় দাঁড় করাও যেখানে আগের কারও দৃষ্টিরেখায় সে পড়ে না; না মিললে পিছিয়ে এসে অন্য জায়গা দেখো। সব রকম সংঘাতহীন বিন্যাসই উত্তর।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

ভিত্তি হলো Permutations + তিনটা blocked-line set। প্রতিটা row-এ ঠিক একটা queen, আর প্রতিটা column-এ ঠিক একটা — মানে সমাধান আসলে column-এর একটা permutation (queens[r] = c)। Permutations-এর "প্রতিটা মান একবার" নিয়মই column-clash সামলায়; বাড়তি শুধু দুটো diagonal-শর্ত। তাই N-Queens = permutation generate করা, কিন্তু প্রতি placement-এর আগে diagonal গেট সহ — Generate Parentheses-এর early-validity ভাবেরই বোর্ড-রূপ।

ভেতরের যুক্তি¶

লুকানো logic হলো diagonal-গুলোকে সংখ্যায় ধরা: একই ↘ diagonal-এর সব cell-এ r - c সমান; একই ↙ (anti-diagonal)-এর সব cell-এ r + c সমান। তাই তিনটা শর্ত তিনটা set-এ নেমে আসে — cols (ব্যবহৃত column), diag (r-c মান), anti (r+c মান)। একটা cell (r, c) safe ঠিক তখনই, যখন c, r-c, r+c তিনটাই নিজ-নিজ set-এ নেই। এতে safe-check O(1)।

কী দিয়ে তথ্য রাখব¶

লাগে তিনটা set — cols, diag (r-c), anti (r+c); একটা list queens (queens[r] = c, বোর্ড পুনর্গঠনে); একটা list out (সব সমাধান জমাতে); আর recursion-এর জন্য call stack। row ধরে ধরে নামি, তাই row-clash আপনিই বাদ (প্রতি row-এ একবারই বসাই)।

এটি কেন উপযুক্ত¶

তিনটা set diagonal/column-clash check ও mark/unmark O(1)-তে করে — পুরো বোর্ড scan করে threat খোঁজার দরকার নেই। row-by-row নামায় row-constraint কোডে আলাদা করে রাখতেই হয় না। queens list শুধু leaf-এ একবার string-বোর্ডে রূপান্তরিত হয়, তাই মাঝপথে memory হালকা। mark করে recurse, ফিরে unmark — choose/un-choose-এর নিখুঁত প্রয়োগ, কোনো clash-state leak হয় না।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: n²টা cell থেকে যেকোনো nটা cell বেছে queen বসানোর সব combination গড়ো, তারপর প্রতিটা বিন্যাসে কোনো দুটো queen পরস্পরকে আক্রমণ করে কিনা যাচাই করো।

উদাহরণ

for each way to choose n cells out of n*n:      # C(n*n, n)
    if no two chosen cells share row/col/diagonal:
        record the board

কোথায় বেশি কাজ হচ্ছে¶

C(n², n) সংখ্যাটা বিশাল — n=8-এ C(64, 8) ≈ 4.4 বিলিয়ন বিন্যাস, যার সিংহভাগে দুটো queen একই row বা column-এ। backtracking দুটো কাজে এটা ছাঁটে: (a) row ধরে নামায় প্রতি row-এ একটাই queen, তাই row/column-clash অধিকাংশই বাদ; (b) প্রতি placement-এর আগে diagonal safe-check করে — একটা partial বোর্ড অবৈধ হলে তার নিচের পুরো subtree-তে নামেই না। ফলে কেবল promising branch-ই খোলা হয়।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: সমাধান = column-এর permutation + diagonal গেট। "n²টা cell থেকে কোনগুলো?" না ভেবে ভাবো "row r-এ queen-টা কোন column-এ বসবে?" — প্রতি row-এ ঠিক একটা সিদ্ধান্ত। আর তিনটা clash-শর্ত তিনটা সংখ্যায় (c, r-c, r+c) নেমে আসে, তাই safe-check O(1)। validity branch খোলার গেট, শেষের যাচাই নয়।

আরও কম কাজে সমাধান¶

go(r): base case r == n হলে queens থেকে string-বোর্ড বানিয়ে record। নাহলে প্রতিটা c (0→n-1): c/r-c/r+c কোনো set-এ থাকলে skip; নাহলে তিন set-এ add + queens.append(c) (choose), go(r+1) (explore), তারপর pop + তিন set থেকে discard (un-choose)। row-by-row নামা + diagonal গেট = early-validity constraint backtracking।

ভাবনার পরিবর্তন¶

মোচড়: পুরো বোর্ড একসাথে ভেবো না; এক row-এ একটা queen-এর সিদ্ধান্তে নেমে এসো। আর "এই দুটো queen কি কোনাকুনি?" — geometry না করে দুটো সংখ্যা মেলাও: r-c সমান হলে একই ↘, r+c সমান হলে একই ↙। জ্যামিতিক শর্তকে set-membership-এ বদলে দিলে check তাৎক্ষণিক।

ছবিতে বোঝা¶

n=4-এর সব বৈধ partial placement নিচে আছে। Label-এর list-এ row অনুযায়ী column থাকে; যেমন [1,3,0] মানে row 0→col 1, row 1→col 3, row 2→col 0। Attack করে এমন column recursive call হওয়ার আগেই বাদ যায়।

graph TD
  q0["[]; search"]
  q1["[0]; search"]
  q2["[0, 2]; dead end"]
  q1 -->|"row 1, col 2"| q2
  q3["[0, 3]; search"]
  q4["[0, 3, 1]; dead end"]
  q3 -->|"row 2, col 1"| q4
  q1 -->|"row 1, col 3"| q3
  q0 -->|"row 0, col 0"| q1
  q5["[1]; search"]
  q6["[1, 3]; search"]
  q7["[1, 3, 0]; search"]
  q8["[1, 3, 0, 2]; record"]
  q7 -->|"row 3, col 2"| q8
  q6 -->|"row 2, col 0"| q7
  q5 -->|"row 1, col 3"| q6
  q0 -->|"row 0, col 1"| q5
  q9["[2]; search"]
  q10["[2, 0]; search"]
  q11["[2, 0, 3]; search"]
  q12["[2, 0, 3, 1]; record"]
  q11 -->|"row 3, col 1"| q12
  q10 -->|"row 2, col 3"| q11
  q9 -->|"row 1, col 0"| q10
  q0 -->|"row 0, col 2"| q9
  q13["[3]; search"]
  q14["[3, 0]; search"]
  q15["[3, 0, 2]; dead end"]
  q14 -->|"row 2, col 2"| q15
  q13 -->|"row 1, col 0"| q14
  q16["[3, 1]; dead end"]
  q13 -->|"row 1, col 1"| q16
  q0 -->|"row 0, col 3"| q13

দুটি leaf record হয়: [1,3,0,2] ও [2,0,3,1]। অন্য leaf-গুলো dead end; সেখান থেকে undo করে parent-এর পরের column চেষ্টা করতে হয়।

ছোট input-এ ধাপে ধাপে¶

solve_n_queens(4), go(r) (একটা সফল শাখা):

go(0): c=1 safe → cols={1}, diag={-1}, anti={1}, queens=[1]; go(1)।
go(1): c=0,1,2 কোনো-না-কোনো set-এ আটকায়; c=3 safe → queens=[1,3]; go(2)।
go(2): c=0 safe → queens=[1,3,0]; go(3)।
go(3): c=2 safe → queens=[1,3,0,2]; go(4): r==n → record .Q.. / ...Q / Q... / ..Q.।
backtrack করে দ্বিতীয় mirror-সমাধানও বেরোয়; out-এ 2টা বোর্ড।

কোড ও ব্যাখ্যা¶

Python¶

Python

def solve_n_queens(n):
    out = []
    cols = set()
    diag = set()     # r - c (↘ diagonal)
    anti = set()     # r + c (↙ anti-diagonal)
    queens = []      # queens[r] = c

    def go(r):
        if r == n:                       # base case: সব row-এ queen বসানো
            board = ["." * c + "Q" + "." * (n - c - 1) for c in queens]
            out.append(board)            # এক সম্পূর্ণ সাজ record
            return
        for c in range(n):
            if c in cols or (r - c) in diag or (r + c) in anti:
                continue                 # unsafe: এই column বা কোনো diagonal blocked
            cols.add(c); diag.add(r - c); anti.add(r + c)   # CHOOSE
            queens.append(c)
            go(r + 1)                    # EXPLORE: পরের row
            queens.pop()                 # UN-CHOOSE
            cols.discard(c); diag.discard(r - c); anti.discard(r + c)

    go(0)
    return out

# ---- order-independent তুলনার helper (বোর্ডের ভেতরের row-ক্রম অটুট) ----
def norm(boards):
    return sorted(boards)                # প্রতিটা বোর্ড row-string-এর list

# ---- tests ----
assert solve_n_queens(1) == [["Q"]]
assert solve_n_queens(2) == []                    # অসম্ভব
assert solve_n_queens(3) == []                    # অসম্ভব
assert len(solve_n_queens(4)) == 2
assert norm(solve_n_queens(4)) == norm([
    [".Q..", "...Q", "Q...", "..Q."],
    ["..Q.", "Q...", "...Q", ".Q.."]])
assert len(solve_n_queens(5)) == 10
assert len(solve_n_queens(6)) == 4
print("সব test pass!")

কোডের প্রতিটি অংশ¶

cols/diag/anti = set() — তিনটা blocked-line: column, r-c diagonal, r+c anti-diagonal।
if r == n: — base case: প্রতি row-এ queen বসে গেছে, একটা পূর্ণ সমাধান।
["." * c + "Q" + "." * (n-c-1) for c in queens] — column-index থেকে 'Q'-যুক্ত string-বোর্ড।
if c in cols or (r-c) in diag or (r+c) in anti: continue — তিন set-এ safe-check; unsafe হলে branch খোলোই না (গেট)।
cols.add(c); diag.add(r-c); anti.add(r+c); queens.append(c) — CHOOSE: queen বসিয়ে তিনটা line block।
go(r + 1) — EXPLORE: পরের row-এ নামো।
queens.pop(); ...discard(...) — UN-CHOOSE: queen তুলে তিনটা line আবার খালি করো।

Output মিলিয়ে দেখা¶

solve_n_queens(4): row 0-এ column 1 ও 2 থেকে দুটো mirror-শাখা বৈধ হয়ে নামে, বাকি column-গুলো নিচের কোনো row-এ আটকে যায় — ফল ঠিক 2টা বোর্ড। প্রতিটা বোর্ড row-string-এর একটা ক্রমিক list (row 0 আগে), তাই norm-এ শুধু বাইরের list sort করি (ভেতরের ক্রম অটুট) — assert stable অথচ সঠিক। n=2,3-এ কোনো safe বিন্যাস নেই → []; n=5,6-এ 10 ও 4। সব মিলে print: সব test pass!।

খরচ ও সাধারণ ভুল¶

সময়¶

worst case O(n!)-এর কাছাকাছি — row 0-এ n option, row 1-এ ≤ n-1, ... ফলে উপরের সীমা n!, তবে diagonal pruning বাস্তবে এর অনেক নিচে নামিয়ে আনে। বোর্ড record করতে প্রতিটা সমাধানে O(n²) (string গড়া)।

অতিরিক্ত জায়গা¶

Output বাদ দিলে O(n) — তিনটা set-এ সর্বোচ্চ n করে entry, queens list n, call stack গভীরতা n। Output ধরলে সব সমাধান-বোর্ডের মোট আকার।

যে ভুলগুলো এড়াতে হবে¶

diagonal-কে r-c/r+c-তে না নামিয়ে প্রতিবার পুরো বোর্ড scan করা — safe-check ধীর; দুটো diagonal-set ব্যবহার করো।
backtrack-এ তিনটা set থেকে discard বা queens.pop() ভুলে যাওয়া — পরের branch-এ পুরোনো queen-এর block leak করে।
r-c ঋণাত্মক হতে পারে — set-এ সমস্যা নেই (negative key চলে), কিন্তু array দিয়ে করলে offset (r-c+n) লাগে; এখানে set বলে নিরাপদ।
n=2,3-এ [] না দিয়ে crash — base case ও empty-result ঠিকভাবে handle করো।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি: Permutations (#9)-এর "প্রতি মান একবার" (column permutation) + Generate Parentheses (#15)-এর early-validity গেট, এখানে তিনটা blocked-line set রূপে। ../patterns.md-এর constraint-backtracking pattern দেখো। এটা tracker-এর চারটা canonical interview shape-এর একটা — এখানে সবচেয়ে বেশি সময় দাও।

পরের অনুশীলন¶

N-Queens II (শুধু গোনা) — https://leetcode.com/problems/n-queens-ii/ (এই tracker-এর #20)
Sudoku Solver (প্রতি cell-এ 3টা unit-set) — https://leetcode.com/problems/sudoku-solver/ (#22)
Chessboard and Queens (blocked cell সহ, CSES) — https://cses.fi/problemset/task/1624/ (#21)

কৌশলটি মনে রাখুন¶

Constraint backtracking with line-sets: একটা মাত্রা (row) ধরে নামো, অন্য মাত্রার clash-শর্ত (column, দুই diagonal) কয়েকটা set-এ O(1) check/mark করো, আর প্রতি placement-এর আগে safe-check করো; geometry-কে সংখ্যায় (r-c, r+c) নামিয়ে আনাই মূল কৌশল।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: "N-Queens = row ধরে নামো; প্রতি row-এ safe column বসাও — cols, r-c diag, r+c anti তিন set দিয়ে check/mark; base case r==n।" যখনই 'একটা grid-এ কয়েকটা জিনিস non-attacking/non-conflicting বসাও' শুনবে — এই line-set constraint backtracking skeleton মনে করবে; conflict-শর্তকে set-membership-এ বদলে দাও।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।