โปรแกรมตรวจสอบว่าโต๊ะหมากรุกเป็นคำตอบ N-Queens ที่ถูกต้องหรือไม่ใน Python

มีเมทริกซ์ n×n แทนกระดานหมากรุก 1=ควีน 0=ว่าง ตรวจสอบว่าเป็นคำตอบ N-Queens ที่ถูกต้อง (ไม่มีควีนโจมตีกัน)

เช่น เมทริกซ์ 5x5 ที่มีควีนวางถูกต้อง ให้ True

ขั้นตอนการแก้ปัญหา

• ใช้เซต rows, cols, diags, rev_diags เก็บตำแหน่งควีน
• วนทุกเซลล์: ถ้าเป็น 1 เพิ่ม i ใน rows, j ใน cols, i-j ใน diags, i+j ใน rev_diags
• ถ้าขนาดเซตทั้ง 4 เท่ากับ n (มีควีน n ตัวไม่ชนกัน) คืน True

ตัวอย่างโค้ด

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