Giả sử chúng ta có một ma trận n x n biểu diễn một bàn cờ. Có một số số 1 và số 0, trong đó 1 đại diện cho quân hậu và 0 đại diện cho một ô trống. Chúng ta phải kiểm tra xem tấm ván có phải là lời giải hợp lệ cho câu đố N-Queen hay không. Như chúng ta biết, một bàn cờ là một giải pháp của giải pháp N-Queen hợp lệ, nơi không có hai quân hậu nào tấn công nhau.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là True
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:
- n:=số hàng của ma trận
- row:=a new set, cols:=a new set, Diags:=a new set, rev_diags:=a new set
- đối với tôi trong phạm vi từ 0 đến n, thực hiện
- đối với j trong phạm vi từ 0 đến n, thực hiện
- nếu ma trận [i, j] là 1, thì
- chèn i vào các hàng
- chèn j vào cols
- chèn (i - j) vào đường chéo
- chèn (i + j) vào rev_diags
- nếu ma trận [i, j] là 1, thì
- đối với j trong phạm vi từ 0 đến n, thực hiện
- trả về true khi kích thước của hàng, kích thước của cột, kích thước của đường chéo, kích thước của rev_diags giống với n, ngược lại là false
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:
Ví dụ
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))
Đầu vào
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] ]
Đầu ra
True