কেস স্টাডি: বিখ্যাত আনডিসাইডেবল ও NP-কমপ্লিট প্রবলেম

# সংশ্লেষিত রেফারেন্স টেবিল -- বিখ্যাত আনডিসাইডেবল ও NP-কমপ্লিট প্রবলেম

problems = {
    "হল্টিং প্রবলেম": {
        "module_lesson": "M9/L39",
        "domain": "প্রোগ্রাম অ্যানালাইসিস, কম্পাইলার ওয়ার্নিং",
        "status": "আনডিসাইডেবল",
    },
    "রাইসের থিওরেম -- এরর-মেসেজ প্রশ্ন": {
        "module_lesson": "M9/L41",
        "domain": "স্ট্যাটিক অ্যানালাইসিস, লিন্টার, ম্যালওয়্যার ডিটেকশন",
        "status": "আনডিসাইডেবল",
    },
    "পোস্ট করেসপন্ডেন্স প্রবলেম": {
        "module_lesson": "M9/L42",
        "domain": "কম্পাইলার তত্ত্ব, স্ট্রিং-রিরাইটিং সিস্টেম",
        "status": "আনডিসাইডেবল",
    },
    "SAT / 3-SAT": {
        "module_lesson": "M10/L44, L46, L47",
        "domain": "সার্কিট ডিজাইন, শিডিউল ভেরিফিকেশন, AI প্ল্যানিং",
        "status": "NP-কমপ্লিট",
    },
    "ট্র্যাভেলিং সেলসম্যান প্রবলেম": {
        "module_lesson": "M10/L47",
        "domain": "লজিস্টিক্স, ডেলিভারি রাউটিং, সার্কিট-বোর্ড ড্রিলিং",
        "status": "NP-কমপ্লিট",
    },
    "গ্রাফ কালারিং": {
        "module_lesson": "M10/L47",
        "domain": "এক্সাম/মিটিং শিডিউলিং, রেজিস্টার অ্যালোকেশন",
        "status": "NP-কমপ্লিট",
    },
}

print(f"{'সমস্যা':>32} | {'মডিউল/পাঠ':>16} | {'স্ট্যাটাস':>14}")
print("-" * 72)
for name, info in problems.items():
    print(f"{name:>32} | {info['module_lesson']:>16} | {info['status']:>14}")
    print(f"{'':>32} | বাস্তব ডোমেইন: {info['domain']}")

# exam scheduling as graph coloring -- ছোট আকারে brute-force-feasible backtracking সলভার

def graph_coloring(vertices, edges, num_colors):
    adjacency = {v: set() for v in vertices}
    for a, b in edges:
        adjacency[a].add(b)
        adjacency[b].add(a)

    assignment = {}

    def backtrack(index):
        if index == len(vertices):
            return True
        v = vertices[index]
        for color in range(num_colors):
            if all(assignment.get(nb) != color for nb in adjacency[v]):
                assignment[v] = color
                if backtrack(index + 1):
                    return True
                del assignment[v]
        return False

    return dict(assignment) if backtrack(0) else None

# পরীক্ষা নোড; এজ = দুই পরীক্ষায় কমন শিক্ষার্থী আছে, তাই একই স্লটে রাখা যাবে না
exams = ["Math", "Physics", "Chemistry", "Biology", "History", "Art"]
conflicts = [
    ("Math", "Physics"),
    ("Math", "Chemistry"),
    ("Math", "Biology"),      # Math-Physics-Biology একটি ট্রায়াঙ্গেল গঠন করে -> কমপক্ষে ৩ রং লাগবে
    ("Physics", "Biology"),
    ("Chemistry", "Biology"),
    ("Chemistry", "History"),
    ("Biology", "Art"),
    ("History", "Art"),
]

for k in range(1, len(exams) + 1):
    result = graph_coloring(exams, conflicts, k)
    if result is not None:
        print(f"সর্বনিম্ন প্রয়োজনীয় টাইম-স্লট: {k}")
        break

schedule = graph_coloring(exams, conflicts, k)
print(f"{'পরীক্ষা':>10} : টাইম-স্লট")
for e in exams:
    print(f"{e:>10} : {schedule[e]}")

# ভেরিফাই: কোনো দুই সংঘর্ষপূর্ণ (adjacent) পরীক্ষা একই স্লট শেয়ার করছে না
violations = [(a, b) for a, b in conflicts if schedule[a] == schedule[b]]
assert not violations, f"সংঘর্ষ পাওয়া গেছে: {violations}"
print("ভেরিফাইড: কোনো দুই সংঘর্ষপূর্ণ পরীক্ষা একই টাইম-স্লট শেয়ার করছে না")