N-Queens via Backtracking — அடிப்படை

N-Queens — ஒரு வரிசை ஒரு ராணி; நெடுவரிசை/மூலை.

உண்மை உலகில் இது ஏன் முக்கியம்?

புதிர்; கட்டுப்பாட்டு தீர்வி; நேர்காணல் — நிலை, சுயமுறை, மீளமைப்பு.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

வரிசை வரிசையாக; முந்தைய வரிசைகளுக்கு எதிர் O(n) அல்லது bit.

Pythonில் முயற்சி செய்வோம்

def total_n_queens(n: int) -> int:
    cols: set[int] = set()
    diag1: set[int] = set()
    diag2: set[int] = set()

    def dfs(r: int) -> int:
        if r == n:
            return 1
        cnt = 0
        for c in range(n):
            if c in cols or (r + c) in diag1 or (r - c) in diag2:
                continue
            cols.add(c)
            diag1.add(r + c)
            diag2.add(r - c)
            cnt += dfs(r + 1)
            cols.remove(c)
            diag1.remove(r + c)
            diag2.remove(r - c)
        return cnt

    return dfs(0)


print(total_n_queens(4))

பொதுவான தவறுகள்

• மூலை குறியீடு.
• வெளியீடு வடிவம்.

முக்கிய பாடங்கள்

• set தெளிவு; பின் bit.
• ''.join வரிசை.