পাইথনে ক্লাসিক্যাল সডোকু সমস্যা সমাধান প্রোগ্রাম

ধরা যাক একটি n×n ম্যাট্রিক্স আছে যাতে 0 থেকে n পর্যন্ত মান আছে। 0 মানে খালি কক্ষ। আমাদের খালি কক্ষগুলো পূরণ করতে হবে যাতে প্রতিটি সারি এবং কলামে 1 থেকে n পর্যন্ত প্রতিটি সংখ্যা ঠিক একবার করে থাকে।

উদাহরণ: ইনপুট ম্যাট্রিক্স হলে আউটপুট True, কারণ সেটা সমাধান করা যায়।

সমাধানের ধাপসমূহ

• find_empty_cell() ফাংশন: প্রথম খালি কক্ষ (0) খুঁজে বের করুন।
• is_feasible() ফাংশন: কোনো কক্ষে x মান রাখা যাবে কিনা যাচাই করুন (সারি ও কলামে ডুপ্লিকেট নেই)।
• is_complete() ফাংশন: পুরো ম্যাট্রিক্স বৈধ কিনা যাচাই করুন।
• মূল মেথড: ব্যাকট্র্যাকিং ব্যবহার করে খালি কক্ষ পূরণ করুন।

উদাহরণ কোড

class Solution:
    def solve(self, matrix):
        n = len(matrix)
        def find_empty_cell(matrix, n):
            for i in range(n):
                for j in range(n):
                    if matrix[i][j] == 0:
                        return (i, j)
            return (-1, -1)
        def is_feasible(matrix, i, j, x):
            if x in matrix[i]:
                return False
            if x in [row[j] for row in matrix]:
                return False
            return True
        def is_complete(matrix, n):
            for row in matrix:
                if set(row) != set(range(1, n + 1)):
                    return False
            for col in range(n):
                if set(row[col] for row in matrix) != set(range(1, n + 1)):
                    return False
            return True
        (i, j) = find_empty_cell(matrix, n)
        if (i, j) == (-1, -1):
            if is_complete(matrix, n):
                return True
            else:
                return False
        for x in range(1, n + 1):
            if is_feasible(matrix, i, j, x):
                matrix[i][j] = x
                if self.solve(matrix):
                    return True
                matrix[i][j] = 0
        return False

ob = Solution()
matrix = [
    [0, 0, 2],
    [2, 0, 1],
    [1, 2, 3]
]
print(ob.solve(matrix))

ইনপুট

matrix = [ [0, 0, 2], [2, 0, 1], [1, 2, 3] ]

আউটপুট

True