একটি n×n ম্যাট্রিক্স শतरঞ্জের বোর্ড রিপ্রেজেন্ট করে (১ = কুইন, ০ = খালি)। বোর্ডটি বৈধ N-কুইন সমাধান কিনা যাচাই করুন (কোনো দুটি কুইন একে অপরকে আক্রমণ করবে না)।
উদাহরণ: ৫x৫ ম্যাট্রিক্স → আউটপুট True।
সমাধানের ধাপগুলো:
- সারি, কলাম, ডায়াগোনাল (i-j) এবং রিভার্স ডায়াগোনাল (i+j) সেটে রাখুন।
- প্রতিটি কুইনের জন্য সেটে যোগ করুন।
- সব সেটের আকার n হলে বৈধ।
উদাহরণ
class Solution:
def solve(self, matrix):
n = len(matrix)
rows = set()
cols = set()
diags = set()
rev_diags = set()
for i in range(n):
for j in range(n):
if matrix[i][j]:
rows.add(i)
cols.add(j)
diags.add(i - j)
rev_diags.add(i + j)
return len(rows) == len(cols) == len(diags) == len(rev_diags) == n
ob = Solution()
matrix = [
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 1],
[0, 0, 1, 0, 0],
[1, 0, 0, 0, 0]
]
print(ob.solve(matrix))
ইনপুট
matrix = [
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 1],
[0, 0, 1, 0, 0],
[1, 0, 0, 0, 0]
]
আউটপুট
True
