ব্যাকট্র্যাকিং অ্যালগরিদম

Backtracking কী?

Backtracking হলো এমন পদ্ধতি যেখানে সম্ভাব্য সমাধান ধাপে ধাপে তৈরি করা হয় এবং কোনো ধাপে ভুল হলে পিছিয়ে (backtrack) গিয়ে অন্য পথ চেষ্টা করা হয়।

বাস্তব উদাহরণ

• গোলকধাঁধা (Maze) — একটি রাস্তায় যাও, দেয়ালে আটকালে ফিরে এসে অন্য রাস্তা চেষ্টা করো
• Sudoku — একটি ঘরে সংখ্যা বসাও, নিয়ম ভঙ্গ হলে মুছে অন্য সংখ্যা চেষ্টা করো

N-Queens সমস্যা

N×N চেসবোর্ডে N টি রানি এমনভাবে বসাতে হবে যাতে কেউ কাউকে আক্রমণ করতে না পারে।

def solve_queens(n):
    board = [-1] * n
    solutions = []

    def is_safe(row, col):
        for r in range(row):
            if board[r] == col or \
               abs(board[r]-col) == abs(r-row):
                return False
        return True

    def place(row):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if is_safe(row, col):
                board[row] = col
                place(row + 1)
                board[row] = -1  # backtrack

    place(0)
    return len(solutions)

print(solve_queens(8))  # 92 solutions!