পাইথনে N কুইন সমাধান সম্ভব কিনা তা যাচাই করা

ধরুন, একটি বাইনারি ম্যাট্রিক্স দেওয়া আছে যেখানে ০ খালি কক্ষ এবং ১ কক্ষে শطরঞ্জের কুইন উপস্থিতি বোঝায়। আমাদের যাচাই করতে হবে এই বোর্ডটি পূরণ করে বৈধ n-কুইন সমাধান পাওয়া যায় কিনা। n-কুইন সমস্যায় n×n চেসবোর্ডে nটি কুইন এইভাবে রাখা হয় যাতে কোনো দুটি কুইন একে অপরকে আক্রমণ করতে না পারে।

ইনপুট ম্যাট্রিক্স:

আউটপুট হবে True, কারণ একটি সম্ভাব্য সমাধান নিচে দেওয়া হল:

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

• isSafe(board, i, j) ফাংশন সংজ্ঞায়িত করুন যা (i,j) কক্ষে কুইন রাখা নিরাপদ কিনা যাচাই করে
• সারি, কলাম এবং কর্ণদিকের সব কক্ষ যাচাই করুন
• মূল ফাংশনে r=0, c=0 এবং একটি স্ট্যাক ব্যবহার করে ব্যাকট্র্যাকিং Алгоритম প্রয়োগ করুন
• প্রতিটি সারিতে যদি আগে থেকে কুইন থাকে তবে পরবর্তী সারিতে যান
• অন্যথায় নিরাপদ কলাম খুঁজে কুইন রাখুন এবং স্ট্যাকে পুশ করুন
• যদি কোনো নিরাপদ অবস্থান না পাওয়া যায় তবে স্ট্যাকে থেকে পপ করে ব্যাকট্র্যাক করুন
• সফল হলে True, ব্যর্থ হলে False ফেরত দিন

উদাহরণ কোড

class Solution:
    def solve(self, board):
        def isSafe(board, i, j):
            for r in range(len(board)):
                if r != i and board[r][j] == 1:
                    return False
            r, c = i + 1, j + 1
            while r < len(board) and c < len(board[0]):
                if board[r][c] == 1:
                    return False
                r += 1; c += 1
            r, c = i + 1, j - 1
            while r < len(board) and c >= 0:
                if board[r][c] == 1:
                    return False
                r += 1; c -= 1
            r, c = i - 1, j + 1
            while r >= 0 and c < len(board[0]):
                if board[r][c] == 1:
                    return False
                r -= 1; c += 1
            r, c = i - 1, j - 1
            while r >= 0 and c >= 0:
                if board[r][c] == 1:
                    return False
                r -= 1; c -= 1
            return True
        r = c = 0
        stack = []
        while r < len(board):
            if 1 in board[r]:
                r += 1
                continue
            else:
                found = False
                while c < len(board[0]):
                    if isSafe(board, r, c):
                        board[r][c] = 1
                        stack.append([r, c])
                        found = True
                        break
                    c += 1
                if found:
                    c = 0; r += 1
                else:
                    if not stack:
                        return False
                    m = stack.pop()
                    r, c = m[0], m[1] + 1
                    board[r][c - 1] = 0
        return True

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

ইনপুট

[[1,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1],[0,0,0,0,0],[0,0,0,1,0]]

আউটপুট

True